 # Deletion in Linked List | Linked List Operations

30 min read

Deletion in a linked list can happen at various places in a list. A few cases are:

• At the beginning of the linked list.
• At the end of the linked list.
• At a given position in the linked list.

Now, let us look at a program for each of these cases.

### Deletion at the beginning of the linked list • To delete the first node (head node), copy the head node in a temporary node.
• Make the second node as the head node.
• Now, delete the temporary node.

Program to delete a node at the beginning of the Linked List

`#include <stdio.h>#include <stdlib.h>// Creating node with data and a pointerstruct node { int data; struct node *next;}*head;void createList(int n);void deletion_beginning();void displayList();int main(){ int n, data, pos; printf("\nEnter the total number of nodes: "); scanf("%d", &n); if(n == 0) { printf("Empty List\n"); exit(0); } else { createList(n); }printf("\nThe List is \n"); displayList(); deletion_beginning(); printf("\n\nAfter Deleting the first node, the List is\n"); displayList(); return 0;}void createList(int n){ struct node *newNode, *temp; int data, i;head = (struct node *)malloc(sizeof(struct node)); // When the list is empty if(head == NULL) { printf("Unable to allocate memory."); } else { printf("\nEnter the data of node 1: "); scanf("%d", &data); head->data = data; head->next = NULL; temp = head; for(i=2; i<=n; i++) { newNode = (struct node *)malloc(sizeof(struct node)); if(newNode == NULL) { printf("Unable to allocate memory."); break; } else { printf("\nEnter the data of node %d: ", i); scanf("%d", &data); newNode->data = data; newNode->next = NULL; temp->next = newNode; temp = temp->next; } } }}/* Function to delete the first node */void deletion_beginning(){  // Empty List if(head == NULL)  printf("\n The list is Empty\n");  struct node *temp; temp = head; //Make temp as head node head = head -> next; // Shift the head node free(temp); // Delete the temporary node}void displayList(){ struct node *temp; if(head == NULL) { printf("List is empty."); } else { temp = head;// Print the list while(temp != NULL) { printf("%d\t", temp->data); temp = temp->next; } printf("\n"); }}`

OUTPUT ### Deletion at the end of the linked list • To delete the last node, start traversing the list from the head node and continue traversing until the address part of the node is NULL.
• Keep track of the second last node in some temporary variable say prev_node.
• Once the address part of the node is NULL, set the address part of the prev_node as NULL and then delete the last node.

Program to delete a node at the end of the Linked List

`#include <stdio.h>#include <stdlib.h>// Creating node with data and a pointerstruct node {int data;struct node *next;}*head;void createList(int n);void deletion_end();void displayList();int main(){int n, data, pos;printf("\nEnter the total number of nodes: ");scanf("%d", &n);createList(n);printf("\nThe List is \n");displayList();deletion_end();printf("\n\nAfter Deleting the last node, the List is\n");displayList();return 0;}void createList(int n){struct node *newNode, *temp;int data, i;head = (struct node *)malloc(sizeof(struct node));// When the list is emptyif(head == NULL){printf("Unable to allocate memory.");}else{printf("\nEnter the data of node 1: ");scanf("%d", &data);head->data = data;head->next = NULL;temp = head;for(i=2; i<=n; i++){newNode = (struct node *)malloc(sizeof(struct node));if(newNode == NULL){printf("Unable to allocate memory.");break;}else{printf("\nEnter the data of node %d: ", i);scanf("%d", &data);newNode->data = data;newNode->next = NULL;temp->next = newNode;temp = temp->next;}}}}/* Function to delete the last node */void deletion_end(){// Empty Listif(head -> next == NULL){free(head); //Delete headhead = NULL; // make the reference to NULL}struct node *temp = head,*prev_node;while(temp -> next != NULL){prev_node = temp;temp = temp -> next; //Traverse to to the last node}free(temp); //Delete the last nodeprev_node -> next = NULL;}void displayList(){struct node *temp;if(head == NULL){printf("List is empty.");}else{temp = head;// Print the listwhile(temp != NULL){printf("%d\t", temp->data);temp = temp->next;}printf("\n");}}`

OUTPUT ### Deletion at a given position in the linked list • Now let us assume that the node at position 2 has to be deleted.
• Start traversing the list from the head node and move up to that position.
• While traversing, keep track of the previous node to the node to be deleted.
• In this case, since we want to delete the second node, you need to traverse till node 2, storing node 1 in some temporary variable.
• Now, the address part of node 2 is assigned to the address part of node 1 and then node 2 is deleted.

Program to delete a node at a given position in the Linked List

`#include <stdio.h>#include <stdlib.h>// Creating node with data and a pointerstruct node {int data;struct node *next;}*head;void createList(int n);void deletion_given_pos(int pos);void displayList();int main(){int n, data, pos;printf("\nEnter the total number of nodes: ");scanf("%d", &n);createList(n);printf("\nThe List is \n");displayList();printf("\nEnter the position : "); //position of the node to be deletedscanf("%d",&pos);deletion_given_pos(pos);printf("\n\nAfter Deleting the node at given position, the List is\n");displayList();return 0;}void createList(int n){struct node *newNode, *temp;int data, i;head = (struct node *)malloc(sizeof(struct node));// When the list is emptyif(head == NULL){printf("Unable to allocate memory.");}else{printf("\nEnter the data of node 1: ");scanf("%d", &data);head->data = data;head->next = NULL;temp = head;for(i=2; i<=n; i++){newNode = (struct node *)malloc(sizeof(struct node));if(newNode == NULL){printf("Unable to allocate memory.");break;}else{printf("\nEnter the data of node %d: ", i);scanf("%d", &data);newNode->data = data;newNode->next = NULL;temp->next = newNode;temp = temp->next;}}}}/* Function to delete the node at given position */void deletion_given_pos(int pos){// Empty Listif(head == NULL){free(head); //Delete headhead = NULL; // make the reference to NULL}struct node *temp = head,*prev_node;int count = 0;while(temp -> next != NULL && pos != count){prev_node = temp;  // Tracking the (position - 1 )nodetemp = temp -> next; count = count + 1;}if(pos == count){prev_node -> next = temp -> next;  // Assigning the address of the node to be deleted to its previous nodefree(temp); // Delete the node}}void displayList(){struct node *temp;if(head == NULL){printf("List is empty.");}else{temp = head;// Print the listwhile(temp != NULL){printf("%d\t", temp->data);temp = temp->next;}printf("\n");}}`

OUTPUT POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Your Output (stdout)

Expected Output

Compiler Message

Input (stdin)

`2    3`

Your Output (stdout)

`5`

Expected Output

`5`

Compiler Message

`5`