Deletion from Linked List – Explanation, Types and Implementation
|In our previous post we have discussed about Linked lists and how to insert a node in a linked list(at the front, at the end and somewhere in between) and in this post we will discuss about the deletion of an element from linked list, what are the possibilities and its implementation. In singly linked list deletion can be done in three ways:
- Deleting a node at the front of linked list
- Deleting a node at the end of linked list
- Deletion of specified node of linked list
Read more – Introduction to Linked List – Explanation and Implementation
Say we have a linked list containing the elements 10, 20 and 30.
1. Deleting a node at the front of linked list
This refers to deleting the first node i.e. element 10. Head will now point to next node. After deleting that node must be freed.
Implementation in C
#include<stdio.h> #include<stdlib.h> //DECLARATION struct node { int data; struct node *next; }; // This function delete the node at the front of linked list struct node* deleteToFront(struct node *head) { struct node *temp = (struct node*)malloc(sizeof(struct node)); temp = head; head = head->next; free(temp); return head; } void printLinkedList(struct node *list) { while (list) { printf(" %d ", list->data); list = list->next; // accessing and assigning the next element of list } } // Main method to initialize the program int main() { //INITIALIZATION //Declare and allocate 3 nodes in the heap struct node* head; struct node* first = (struct node*)malloc(sizeof(struct node)); struct node* second = (struct node*)malloc(sizeof(struct node)); struct node* third = (struct node*)malloc(sizeof(struct node)); //ASSIGNINMENT first->data = 10; //assign data in first node first->next = second; // Link first node with second second->data = 20; //assign data to second node second->next = third; third->data = 30; //assign data to third node third->next = NULL; head = first; //head pointing to the linked list head = deleteToFront(head); printLinkedList(head); return 0; }
Output:-
20 30
2. Deleting a node at the end of linked list
This refers to deleting the last node i.e. element 30. Node previous to last will now point to NULL.
Implementation in C
#include<stdio.h> #include<stdlib.h> //DECLARATION struct node { int data; struct node *next; }; // This function delete the node at the end of linked list void deleteToEnd(struct node *list) { struct node *temp = (struct node*)malloc(sizeof(struct node)); while(list->next->next){ list = list->next; } temp = list->next; list->next = NULL; free(temp); } void printLinkedList(struct node *list) { while (list) { printf(" %d ", list->data); list = list->next; // accessing and assigning the next element of list } } // Main method to initialize the program int main() { //INITIALIZATION //Declare and allocate 3 nodes in the heap struct node* head; struct node* first = (struct node*)malloc(sizeof(struct node)); struct node* second = (struct node*)malloc(sizeof(struct node)); struct node* third = (struct node*)malloc(sizeof(struct node)); //ASSIGNINMENT first->data = 10; //assign data in first node first->next = second; // Link first node with second second->data = 20; //assign data to second node second->next = third; third->data = 30; //assign data to third node third->next = NULL; head = first; //head pointing to the linked list deleteToEnd(head); printLinkedList(head); return 0; }
Output:-
10 20
3. Deletion of specified node of linked list
Say want to delete the node containing element 20. Searching operation will be performed and once the desired node is found, its previous node will be made to link to next to next i.e. Leaving the current node.
Implementation in C
#include<stdio.h> #include<stdlib.h> //DECLARATION struct node { int data; struct node *next; }; // This function delete node containing 20 void deleteSpecified(struct node *list, int data) { struct node *temp = (struct node*)malloc(sizeof(struct node)); temp->data = data; while(list->next->data != 20){ list = list->next; } temp = list->next; list->next = list->next->next; free(temp); } void printLinkedList(struct node *list) { while (list) { printf(" %d ", list->data); list = list->next; // accessing and assigning the next element of list } } // Main method to initialize the program int main() { //INITIALIZATION //Declare and allocate 3 nodes in the heap struct node* head; struct node* first = (struct node*)malloc(sizeof(struct node)); struct node* second = (struct node*)malloc(sizeof(struct node)); struct node* third = (struct node*)malloc(sizeof(struct node)); //ASSIGNINMENT first->data = 10; //assign data in first node first->next = second; // Link first node with second second->data = 20; //assign data to second node second->next = third; third->data = 30; //assign data to third node third->next = NULL; head = first; //head pointing to the linked list //Insert after 20 deleteSpecified(head, 20); printLinkedList(head); return 0; }
Output:-
10 30
Note:-
There is one more variant of deletion of a node at specified location in which instead of value, a location is given where we have to delete the node. For ex – deleting a node at 3rd position from the beginning, delete element as the second last element of the list etc. Here element is not mentioned rather position is provided. In such scenarios instead of checking condition on the values, we keep a track on the number of nodes processed and then delete the node at the specified location.
Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂