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.
- Delete a node from the beginning.
- Delete a node from the middle.
- 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:
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.
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:
