Lab Assignment - IV Date:- 4 & 8 Sept' 2023
Subject - DataStructre Lab
Stream - CSE Semester - 3rd Batch - 2
_____________________________________________________________________________________
Lab Experiment: Introduction to Linked Lists
Aim: To understand the concept and implementation of linked lists in C programming.
Experiment Tasks:
Task 1: Linked List Creation
I. Define a structure named `Node` to represent a node in a singly linked list. The structure
should have two fields: `data` to store an integer value, and `next` to store a pointer to the
next node.
II. Implement a function to create a new node with a given value and return a pointer to it.
III. Create a function to initialize an empty linked list by setting the head pointer to NULL.
Task 2: Insertion at the Beginning
I. Implement a function to insert a new node at the beginning of the linked list.
II. Print the linked list to verify that the insertion is successful.
Task 3: Insertion at the End
I. Implement a function to insert a new node at the end of the linked list.
II. Print the linked list to verify that the insertion is successful.
Task 4: Deletion of a Node
I. Implement a function to delete a node with a given value from the linked list.
II. Print the linked list to verify that the deletion is successful.
Task 5: Searching for a Node
I. Create a function to search for a node with a given value in the linked list.
II. Print whether the node with the given value is found or not.
Task 6: Displaying the Linked List
I. Implement a function to display the linked list from the beginning to the end.
II. Print the entire linked list.
Task 7: Freeing Memory
I. Implement a function to free the memory occupied by the linked list nodes when the
experiment is complete.
Solution:
#include <stdio.h>
#include <stdlib.h>
struct Node { // Define the structure for a node
int data;
struct Node* next;
};
struct Node* createNode(int value) { // Function to create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}
struct Node* initLinkedList() {
return NULL;
}
// Function to insert a new node at the beginning
struct Node* insertAtBeginning(struct Node* head, int value) {
struct Node* newNode = createNode(value);
newNode->next = head;
head = newNode;
return head;
}
struct Node* insertAtEnd(struct Node* head, int value) { // Function to insert a new node at the end
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
return head;
}
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
return head;
}
struct Node* deleteNode(struct Node* head, int value) { // Function to delete a node with a given value
struct Node* current = head;
struct Node* previous = NULL;
while (current != NULL) {
if (current->data == value) {
if (previous == NULL) {
head = current->next;
} else {
previous->next = current->next;
}
free(current);
return head;
}
previous = current;
current = current->next;
}
return head;
}
int searchNode(struct Node* head, int value) { // Function to search for a node with a given value
struct Node* current = head;
while (current != NULL) {
if (current->data == value) {
return 1; // Found
}
current = current->next;
}
return 0; // Not found
}
void displayLinkedList(struct Node* head) { // Function to display the linked list
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
void freeLinkedList(struct Node* head) { // Function to free memory used by the linked list
struct Node* current = head;
while (current != NULL) {
struct Node* temp = current;
current = current->next;
free(temp);
}
}
int main() {
struct Node* head = initLinkedList();
int deleteValue, searchValue;
// Insertion at the beginning
head = insertAtBeginning(head, 42);
head = insertAtBeginning(head, 28);
// Insertion at the end
head = insertAtEnd(head, 17);
head = insertAtEnd(head, 55);
// Display the linked list
printf("Linked List: ");
displayLinkedList(head);
// Search for a node
searchValue = 17;
if (searchNode(head, searchValue)) {
printf("%d is found in the linked list.\n", searchValue);
} else {
printf("%d is not found in the linked list.\n", searchValue);
}
// Delete a node
deleteValue = 28;
head = deleteNode(head, deleteValue);
// Display the updated linked list
printf("Updated Linked List: ");
displayLinkedList(head);
// Free memory
freeLinkedList(head);
return 0;
}