Design, Develop and Implement a menu driven Program in C for the following operations on Singly Linked List (SLL)
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.
- A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
- The last node of the list contains pointer to the null.
The simplest kind of linked list is a singly liked list (SLL) which has one link per node. It has two parts, one part contains data and other contains address of next node. In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.The structure of a node in a SLL is given as in C:
struct node { int data; struct node *next; }; |
---|
Insertion of node at front
- allocate node
- put in the data
- Make next of new node as head
- move the head to point to the new node
void insert(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } |
---|
Insertion at end
- allocate node
- put in the data
- This new node is going to be the last node, so make next of it as NULL
- If the Linked List is empty, then make the new node as head
- Else traverse till the last node
- Change the next of last node
void end(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); struct Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } |
---|
Insertion after a node
void insertAfter(struct Node* prev_node, int new_data) { // check if the given prev_node is NULL if (prev_node == NULL) { printf("the given previous node cannot be NULL"); return; } // allocate new node struct Node* new_node =(struct Node*) malloc(sizeof(struct Node)); //put in the data new_node->data = new_data; //Make next of new node as next of prev_node new_node->next = prev_node->next; //move the next of prev_node as new_node prev_node->next = new_node; } |
---|
Deletion of node
To delete a node from linked list, we need to do following steps.
1) Find previous node of the node to be deleted.
2) Change the next of previous node.
3) Free memory for the node to be deleted.
void deleteNode(struct Node **head_ref, int key) { // Store head node struct Node* temp = *head_ref, *prev; // If head node itself holds the key to be deleted if (temp != NULL && temp->data == key) { *head_ref = temp->next; // Changed head free(temp); // free old head return; } // Search for the key to be deleted, keep track of the // previous node as we need to change 'prev->next' while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } // If key was not present in linked list if (temp == NULL) return; // Unlink the node from linked list prev->next = temp->next; free(temp); // Free memory } |
---|
For more Visvesvaraya Technological University(VTU) CSE-III Sem Data Structure Lab Experiments Click Here