Home » Data Structure

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:

1. Deleting the first node
2. Deleting the last node
3. 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.

1. Create a temporary node, say temp which points to the head node (first node) of the list.
2. 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:

1. 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.
2. 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.
3. 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.

1. 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.
2. Set the next pointer of the prev node to the next pointer of curr node.
3. 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