Delete a Linked List node

Delete a Linked List node

In my previous article, I have discussed the introduction of linked list and linked list insertion. In this article, we will see how to delete a node from the existing linked list.

Delete a Node:

There are three ways to delete a node from the linked list. It depends on the user requirements.

  1. Delete a node from the beginning.
  2. Delete a node from the middle.
  3. Delete a node from the end.

Note: in the previous article I have already discussed, how to create a linked list so please if you are not aware of the linked list then please see my previous article.

Generic steps to delete a node

Here I am discussing some generic steps to delete a node from the linked list.These steps depend on user implementation.

  • Find the previous node of a node which you want to delete.
  • Remove that node.
  • Reconnect the linked list.
  • Free the allocated memory of the removed node.
  • Update the link to the beginning (if necessary).

Note: The order in which we perform these steps will depend on how we implement the deletion operation.

Delete a node from the beginning

When deleting the node at the beginning of the linked list then there is no need of relinking of nodes, because there is no node available in the back of the first node.
For example, removing a node from the beginning:

www.aticleworld.com

Example source code:

// A simple C program to delete node from the beginning
#include<stdio.h>
#include<stdlib.h>
 
 
// Creating Node
 struct Node 
{
  int iData;
  struct Node *pNextNode;
};
 
 
// Define the new type Node type and Node pointer
typedef  struct Node  NodeType, * NodePointer;


/*Delete node from the beginning.
Paas the reference of the head pointer of a list.
*/
int DeleteFromBeginning(NodePointer  *pHead)
{
	int iRetValue = -1;
	NodePointer pTmpNode = NULL;
	
	//If there is no node then perform no operation
	if((*pHead) !=  NULL)
	{
		pTmpNode = (*pHead)->pNextNode;
		
		//Free the first node
		free((*pHead));
		//Assign the address of second node to head pointer
		(*pHead) = pTmpNode;
		iRetValue =0;
	}
	
	return iRetValue;
	
}


/* Paas the reference of the head pointer of a list and 
   an integer data. This function use to add the node at the End*/
int InsertNodeAtEnd(NodePointer * pHead, int iUserData) 
{
	int iRetValue = -1;
	
	NodePointer pLastNode = NULL;
	NodePointer pNewNode = NULL;
	
	//Give the Address of first Node
	pLastNode  = *pHead;
	
	// Call malloc to allocate memory in heap for the new node
	pNewNode = malloc(sizeof(NodeType));
	
	if( pNewNode != NULL) //Check allocated memory
	{
		pNewNode->iData = iUserData; //put the desire Data
		
		pNewNode->pNextNode  = NULL; //Give the Address of first Node
		
		iRetValue = 0; // Update the return value
		
	}
	// If there is no node in beginning
	if(pLastNode == NULL)
	{
		*pHead = pNewNode;
	}
	else 
	{
		// Find the address of last node
		while( pLastNode ->pNextNode != NULL)
		{
			pLastNode  = pLastNode ->pNextNode;
		}
	
	   // Assign last node address
	    pLastNode ->pNextNode = pNewNode;

	}
	
	return iRetValue;
}

/* Paas the reference of the head pointer of a list. This function use
to free the all allocated memory*/
void FreeAllocatedMemory(NodePointer  *pHead)
{
   NodePointer   pTmpNode = NULL;
   NodePointer   pFirstNode = NULL;
   //Assign  the Address of first node
   pFirstNode  = *pHead;
   
/*check if pFirstNode is NULL, then now list is empty,
so assign NULL to head and return.*/
   while (pFirstNode  != NULL)
    {
	 /*Save the pFirstNode in a pTmpNode node pointer*/ 

       pTmpNode = pFirstNode  ;
       
       /*Assign the address of next on your list*/	
       pFirstNode  = pFirstNode->pNextNode;
       
       //Free the allocated memory
       free(pTmpNode );
    }
	//Assign NULL to the head pointer
	*pHead = NULL;

}

 
// This function use to prints the data of the list from the begning
//to the given list.
 
void PrintTheList(NodePointer pNode)
{
	//Clear the screen
  
  printf("\nDisplay Linked List: \n\n");
  while (pNode != NULL)
  {
     printf("\n %d\n",pNode->iData);
     pNode = pNode->pNextNode;
  }
  	
  	printf("\n\n");
  
}


int CreateLinkedList(NodePointer *pHead, int iNumberofNode)
{
	int iData = 0;
	int iRetValue = -1;
	int iCount = 0;
	NodePointer pNewNode = NULL;
	
	for(iCount =0; iCount < iNumberofNode; iCount++)
	{
		/*Enter desire data*/
		printf("\n\nEnter the Data = ");
		scanf("%d",&iData);
		
		if((*pHead) == NULL)
		{
			 // Call malloc to allocate memory in heap for the first node
	          pNewNode = malloc(sizeof(NodeType));
	          if( pNewNode != NULL) //Check allocated memory
			  {
				  pNewNode->iData = iData; //put the desire Data
				  
				  pNewNode->pNextNode  = NULL; //Give the Address of first Node
				  
				  *pHead = pNewNode; /*Assign the address of 
				                      first node to the head pointer*/
				  
				  iRetValue = 0; // Update the return value
		
	}
		}
		else
		{
			//Add the Node at the End
			iRetValue = InsertNodeAtEnd(pHead,iData);
			
		}
	}
	
	return iRetValue;
}


/* Driver program to test above functions*/
int main(void)
{
   int iNumberNode =0;
   int iData = 0;
   int iPosition =0;
	
   /*Start with the empty list */
   NodePointer head = NULL;
   
   
   printf("\n\nEnter the number of nodes = ");
   scanf("%d",&iNumberNode);
   
   //Create a linked list of three node
   CreateLinkedList(&head,iNumberNode);
		
	/*
	pHead
	|
	|
	|
	v
	---------     ---------     ---------
	| 10 | --+--->| 20 |  --+--->| 30 | 0|
	---------     ---------     ---------
	
	*/
	

   //Print the created node
   PrintTheList(head);
   
   printf("\nDelete a Node from the beginning\n\n");
   // Delete the beginning node
   DeleteFromBeginning(&head);
	/*  
	
	pHead
	|
	|
	+---------------+
				    |
				    v
	---------     ---------     ---------
	| 10 | --+--->| 20 | --+--->| 30 | 0|
	---------     ---------     ---------
	
	*/
   
    //Print the created node
   PrintTheList(head);
   		   
   FreeAllocatedMemory(&head);
  return 0;
}
   

OutPut:

 

If you want to learn more about the c language, here 10 Free days (up to 200 minutes) C video course for you.

Your free trial is waiting

 

Delete a node from a certain position

First, find the preceding node of a node which you want to remove after that just skip over the node which being removed.
For example, removing the 2nd node of the linked list.

Example source code:

// A simple C program to delete node from any position
#include<stdio.h>
#include<stdlib.h>
 
 
// Creating Node
 struct Node 
{
  int iData;
  struct Node *pNextNode;
};
 
 
// Define the new type Node type and Node pointer
typedef  struct Node  NodeType, * NodePointer;


/* Paas the reference of the head pointer of a list and 
   an integer data*/
void DeleteNodeFromPosition(NodePointer * pHead,unsigned int iPosition)
{
	NodePointer pTmpNode = NULL;
	NodePointer pPreviousTmpNode = NULL;
	unsigned int iCount = 0;
	
    //Give the Address of first Node
	pTmpNode  = *pHead;
 
    for( iCount = 1; ((iCount < iPosition) && (pTmpNode!= NULL)) ; iCount++)
    {
		pPreviousTmpNode = pTmpNode;
    	pTmpNode  = pTmpNode ->pNextNode;
	}
	

      pPreviousTmpNode->pNextNode = pTmpNode->pNextNode;
	  free(pTmpNode);
	  pTmpNode = NULL;
	  
  return;
}


/* Paas the reference of the head pointer of a list and 
   an integer data. This function use to add the node at the End*/
int InsertNodeAtEnd(NodePointer * pHead, int iUserData) 
{
	int iRetValue = -1;
	
	NodePointer pLastNode = NULL;
	NodePointer pNewNode = NULL;
	
	//Give the Address of first Node
	pLastNode  = *pHead;
	
	// Call malloc to allocate memory in heap for the new node
	pNewNode = malloc(sizeof(NodeType));
	
	if( pNewNode != NULL) //Check allocated memory
	{
		pNewNode->iData = iUserData; //put the desire Data
		
		pNewNode->pNextNode  = NULL; //Give the Address of first Node
		
		iRetValue = 0; // Update the return value
		
	}
	// If there is no node in beginning
	if(pLastNode == NULL)
	{
		*pHead = pNewNode;
	}
	else 
	{
		// Find the address of last node
		while( pLastNode ->pNextNode != NULL)
		{
			pLastNode  = pLastNode ->pNextNode;
		}
	
	   // Assign last node address
	    pLastNode ->pNextNode = pNewNode;

	}
	
	return iRetValue;
}

/* Paas the reference of the head pointer of a list. This function use
to free the all allocated memory*/
void FreeAllocatedMemory(NodePointer  *pHead)
{
   NodePointer   pTmpNode = NULL;
   NodePointer   pFirstNode = NULL;
   //Assign  the Address of first node
   pFirstNode  = *pHead;
   
/*check if pFirstNode is NULL, then now list is empty,
so assign NULL to head and return.*/
   while (pFirstNode  != NULL)
    {
	 /*Save the pFirstNode in a pTmpNode node pointer*/ 

       pTmpNode = pFirstNode  ;
       
       /*Assign the address of next on your list*/	
       pFirstNode  = pFirstNode->pNextNode;
       
       //Free the allocated memory
       free(pTmpNode );
    }
	//Assign NULL to the head pointer
	*pHead = NULL;

}

 
// This function use to prints the data of the list from the begning
//to the given list.
 
void PrintTheList(NodePointer pNode)
{
	//Clear the screen
  
  printf("\nDisplay Linked List: \n\n");
  while (pNode != NULL)
  {
     printf("\n %d\n",pNode->iData);
     pNode = pNode->pNextNode;
  }
  	
  	printf("\n\n");
  
}


int CreateLinkedList(NodePointer *pHead, int iNumberofNode)
{
	int iData = 0;
	int iRetValue = -1;
	int iCount = 0;
	NodePointer pNewNode = NULL;
	
	for(iCount =0; iCount < iNumberofNode; iCount++)
	{
		/*Enter desire data*/
		printf("\n\nEnter the Data = ");
		scanf("%d",&iData);
		
		if((*pHead) == NULL)
		{
			 // Call malloc to allocate memory in heap for the first node
	          pNewNode = malloc(sizeof(NodeType));
	          if( pNewNode != NULL) //Check allocated memory
			  {
				  pNewNode->iData = iData; //put the desire Data
				  
				  pNewNode->pNextNode  = NULL; //Give the Address of first Node
				  
				  *pHead = pNewNode; /*Assign the address of 
				                      first node to the head pointer*/
				  
				  iRetValue = 0; // Update the return value
		
	}
		}
		else
		{
			//Add the Node at the End
			iRetValue = InsertNodeAtEnd(pHead,iData);
			
		}
	}
	
	return iRetValue;
}


/* Driver program to test above functions*/
int main(void)
{
   int iNumberNode =0;
   int iData = 0;
   int iPosition =0;
	
   /*Start with the empty list */
   NodePointer head = NULL;
   
   
   printf("\n\nEnter the number of nodes = ");
   scanf("%d",&iNumberNode);
   
   //Create a linked list of three node
   CreateLinkedList(&head,iNumberNode);
		
	/*
	pHead
	|
	|
	|
	v
	---------     ---------     ---------
	| 10 | --+--->| 20 |  --+--->| 30 | 0|
	---------     ---------     ---------
	
	*/
	

   //Print the created node
   PrintTheList(head);
   
   printf("\n\nEnter the Position of removing Node = ");
   scanf("%d",&iPosition);
   // Delete the beginning node
   DeleteNodeFromPosition(&head,iPosition);
	/*  
	
    pHead
     |
     v
    ---------     ---------     ---------
    | 10 | --+--+ | 20 | --+--->| 30 | 0 |
    ---------  |  ---------     ---------
               |                ^
               +----------------+
    	
	*/
   
    //Print the created node
   PrintTheList(head);
   		   
   FreeAllocatedMemory(&head);
   
  return 0;
}
   

OutPut:

Delete a node from the end.

In which we will delete the last node of the list. The preceding node of the last node becomes the new last node of the linked list.
For example, removing the last node.

Example source code:

// A simple C program to delete node from the end
#include<stdio.h>
#include<stdlib.h>
 
 
// Creating Node
 struct Node 
{
  int iData;
  struct Node *pNextNode;
};
 
 
// Define the new type Node type and Node pointer
typedef  struct Node  NodeType, * NodePointer;


/* Paas the reference of the head pointer of the list*/
int DeleteLastNode(NodePointer  *pHead)
{
  int iRetValue = -1;	
  NodePointer pNextTmpNode = *pHead;
  NodePointer pPreviousTmpNode =NULL;
  
  if((*pHead) !=  NULL) //if only one nodein list
  {
	  if((*pHead)->pNextNode == NULL)
	  {
		  free((*pHead));
		  (*pHead) = NULL;
	  }
	  else  //find preceding nodeof last node
	  {
		  while(pNextTmpNode->pNextNode != NULL)
		  {
			  pPreviousTmpNode = pNextTmpNode;
			  pNextTmpNode = pNextTmpNode->pNextNode;
		  }
		  //Free the memory of last node
		  free(pPreviousTmpNode->pNextNode);
		  pPreviousTmpNode->pNextNode = NULL;
	  }    
  }
  
  return iRetValue;
}


/* Paas the reference of the head pointer of a list and 
   an integer data. This function use to add the node at the End*/
int InsertNodeAtEnd(NodePointer * pHead, int iUserData) 
{
	int iRetValue = -1;
	
	NodePointer pLastNode = NULL;
	NodePointer pNewNode = NULL;
	
	//Give the Address of first Node
	pLastNode  = *pHead;
	
	// Call malloc to allocate memory in heap for the new node
	pNewNode = malloc(sizeof(NodeType));
	
	if( pNewNode != NULL) //Check allocated memory
	{
		pNewNode->iData = iUserData; //put the desire Data
		
		pNewNode->pNextNode  = NULL; //Give the Address of first Node
		
		iRetValue = 0; // Update the return value
		
	}
	// If there is no node in beginning
	if(pLastNode == NULL)
	{
		*pHead = pNewNode;
	}
	else 
	{
		// Find the address of last node
		while( pLastNode ->pNextNode != NULL)
		{
			pLastNode  = pLastNode ->pNextNode;
		}
	
	   // Assign last node address
	    pLastNode ->pNextNode = pNewNode;

	}
	
	return iRetValue;
}

/* Paas the reference of the head pointer of a list. This function use
to free the all allocated memory*/
void FreeAllocatedMemory(NodePointer  *pHead)
{
   NodePointer   pTmpNode = NULL;
   NodePointer   pFirstNode = NULL;
   //Assign  the Address of first node
   pFirstNode  = *pHead;
   
/*check if pFirstNode is NULL, then now list is empty,
so assign NULL to head and return.*/
   while (pFirstNode  != NULL)
    {
	 /*Save the pFirstNode in a pTmpNode node pointer*/ 

       pTmpNode = pFirstNode  ;
       
       /*Assign the address of next on your list*/	
       pFirstNode  = pFirstNode->pNextNode;
       
       //Free the allocated memory
       free(pTmpNode );
    }
	//Assign NULL to the head pointer
	*pHead = NULL;

}

 
// This function use to prints the data of the list from the begning
//to the given list.
 
void PrintTheList(NodePointer pNode)
{
	//Clear the screen
  
  printf("\nDisplay Linked List: \n\n");
  while (pNode != NULL)
  {
     printf("\n %d\n",pNode->iData);
     pNode = pNode->pNextNode;
  }
  	
  	printf("\n\n");
  
}


int CreateLinkedList(NodePointer *pHead, int iNumberofNode)
{
	int iData = 0;
	int iRetValue = -1;
	int iCount = 0;
	NodePointer pNewNode = NULL;
	
	for(iCount =0; iCount < iNumberofNode; iCount++)
	{
		/*Enter desire data*/
		printf("\n\nEnter the Data = ");
		scanf("%d",&iData);
		
		if((*pHead) == NULL)
		{
			 // Call malloc to allocate memory in heap for the first node
	          pNewNode = malloc(sizeof(NodeType));
	          if( pNewNode != NULL) //Check allocated memory
			  {
				  pNewNode->iData = iData; //put the desire Data
				  
				  pNewNode->pNextNode  = NULL; //Give the Address of first Node
				  
				  *pHead = pNewNode; /*Assign the address of 
				                      first node to the head pointer*/
				  
				  iRetValue = 0; // Update the return value
		
	}
		}
		else
		{
			//Add the Node at the End
			iRetValue = InsertNodeAtEnd(pHead,iData);
			
		}
	}
	
	return iRetValue;
}


/* Driver program to test above functions*/
int main(void)
{
   int iNumberNode =0;
   int iData = 0;
 
	
   /*Start with the empty list */
   NodePointer head = NULL;
   
   
   printf("\n\nEnter the number of nodes = ");
   scanf("%d",&iNumberNode);
   
   //Create a linked list of three node
   CreateLinkedList(&head,iNumberNode);
		
	/*
	pHead
	|
	|
	|
	v
	---------     ---------     ---------
	| 10 | --+--->| 20 |  --+--->| 30 | 0|
	---------     ---------     ---------
	
	*/
	

   //Print the created node
   PrintTheList(head);
   
   // Delete the last node
   DeleteLastNode(&head);
	/*  
	
   pHead		   
    |
    v
   ---------     ---------     ---------
   | 10 | --+---> | 20 | 0 |     | 30 | 0 |
   ---------     ---------     ---------
       	
	*/
   printf("Print the List after removing of last node\n\n");
    //Print the linked list
   PrintTheList(head);
   		   
   FreeAllocatedMemory(&head);
   
  return 0;
}
   

OutPut: