# Single linked list deletion

In this article, we are going to learn **how to delete a node in single linked list using C program in Data Structure**?

Submitted by Radib Kar, on October 24, 2018

Deletion can be at various positions like:

- Deleting the first node
- Deleting the last node
- Deleting the intermediate node

### Deleting the first node in single linked list

In such case, the head node is to be removed and the next node needs to be assigned as updated head node.

- Create a temporary node, say temp which points to the head node (first node) of the list.
- Move head node pointer to the immediate next node and delete (dispose) the temp node.

### Deleting the last node in the single linked list

In such case the last node is to be removed from list. The steps are following:

- We need to keep track of the previous node of last node. That's why while traversing to the last node we need to set a prev node also which will point to the previous node of the tail node( last node) after traversal.
- So, we have two pointer, one tail node pointing to the last node and another is prev node pointing to the previous node of the last node.
- Set the next pointer of the prev node to NULL and delete the tail node. (last node)

### Deleting an intermediate node in the single linked list

In such case an intermediate node is to be deleted. The approach is quite similar to the previous.

- Similar to the previous case, a curr node and a prev node is to be maintained. Curr node will point to the node to be deleted and prev node will point to the previous node.
- Set the next pointer of the prev node to the next pointer of curr node.
- Delete the curr node.

## C implementation of deletion in a linked list

#include <stdio.h> #include <stdlib.h> struct node{ int data; // data field struct node *next; }; void traverse(struct node* head){ struct node* current=head; // current node set to head int count=0; // to count total no of nodes printf("\n traversing the list\n"); while(current!=NULL){ //traverse until current node isn't NULL count++; //increase node count printf("%d ",current->data); current=current->next; // go to next node } printf("\ntotal no of nodes : %d\n",count); } struct node* creatnode(int d){ struct node* temp=malloc(sizeof(struct node)); temp->data=d; temp->next=NULL; return temp; } int main(){ printf("creating the linked list by inserting new nodes at the begining\n"); printf("enter 0 to stop building the list, else enter any integer\n"); int k,count=1,x; struct node* curr,*temp,*prev; scanf("%d",&k); struct node* head=creatnode(k); //buliding list, first node scanf("%d",&k); ///////////////////inserting at begining////////////////////// while(k){ curr=creatnode(k); curr->next=head; //inserting each new node at the begining head=curr; scanf("%d",&k); } traverse(head); // displaying the list ////////////////deleting the first node//////////////////// printf("\ndeleting the first node.............\n"); temp=head; // first node assigned to temp head=head->next; // head node is updated free(temp); // deleting the first node traverse(head); // displaying the list printf("\nfirst node deleted...............\n"); /////////////////deleting the last node//////////////// printf("\ndeleting the last node.............\n"); temp=head->next; prev=head; while(temp->next!=NULL){ temp=temp->next; prev=prev->next; } // after traversal temp points to the last //node and prev to the previous node of the last node prev->next=NULL; free(temp); traverse(head); printf("\last node deleted................\n"); ///////////////deleting any intermediate node in the list//////////////// printf("\n enter the position of the node you want to delete\n"); scanf("%d",&x); temp=head->next; prev=head; while(count!=x-1){ temp=temp->next; prev=prev->next; count++; } // temp pointing to the node to be deleted and prev to the previous node prev->next=temp->next; free(temp); traverse(head); return 0; }

**Output**

creating the linked list by inserting new nodes at the begining enter 0 to stop building the list, else enter any integer 1 2 3 4 5 6 7 8 9 0 traversing the list 9 8 7 6 5 4 3 2 1 total no of nodes : 9 deleting the first node............. traversing the list 8 7 6 5 4 3 2 1 total no of nodes : 8 first node deleted............... deleting the last node............. traversing the list 8 7 6 5 4 3 2 total no of nodes : 7 last node deleted................ enter the position of the node you want to delete 5 traversing the list 8 7 6 5 3 2 total no of nodes : 6

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions