In my previous article, I have discussed the basic concept of the linked list and discuss its advantage and disadvantage. In this article, I will discuss how to insert a new node in an existing linked list.
Previously I have described an example where I have created a linked list of four nodes. This is a very good example to create a linked list, but this example is not the generic one.
So here I will create a generic function to create a new node and insert this node in the existing linked list as per the user’s requirement.
There are three ways to insert the new node in an existing linked list
1. At the beginning of the linked list.
2. After a node in the linked list
3. At the end of the linked list.
Insert a node at the beginning of the linked list
Here I am describing the few steps to insert a new node at the beginning of the linked list.
1. Allocate the memory in heap for the new node using the calling of malloc().
NodePointer pNewNode = malloc(sizeof(NodeType));
2. After getting the memory successfully stored the data in the data field as per the requirement.
if(pNewNode != NULL)
{
pNewNode->iData = Value;
}
3. For the linking, assign the address of the first node to the next pointer of the created new node.
pNewNode ->pNextNode = head;
4. At the last assign the address of created new to the head pointer.
Head = pNewNode;
See the below sample code when the user calls the function ( InsertNodeAtBeginning() ) then it adds the new node at the beginning of the linked list.
/* Paas the reference of the head pointer of a list and
an integer data*/
int InsertNodeAtBeginning(NodePointer * pHead, int iUserData)
{
int iRetValue = -1;
// Call malloc to allocate memory in heap for the new node
NodePointer pNewNode = malloc(sizeof(NodeType));
if( pNewNode != NULL) //Check allocated memory
{
pNewNode->iData = iUserData; //put the desire Data
pNewNode->pNextNode = *pHead; //Give the Address of first Node
*pHead = pNewNode; // Assign the Address of New Node to Head
iRetValue = 0; // Update the return value
}
return iRetValue;
}
If you want to learn more about the data structure, here 10 Free days online video course for you.
Click Here to Get the Course
Insert a new node after a node
In linked list data are not stored in the contiguous format, so every time we have to start data tracing from the head pointer. Below I am describing the steps to how you can insert a new node after a given node.
1. Take a node pointer and assigned the address of the first node which is stored by the head pointer.
NodePointer pTmpNode = head;
2. Get the address of the specified node where you want to insert a new node in the linked list.
for( iPosition = 1 ; iPosition < specified_Position ; iPosition++) pTmpNode = pTmpNode ->pNextNode;
3. If the pTmpNode is not NULL for the specified location then allocate the memory in heap for the new node using the calling of malloc().
NodePointer pNewNode = malloc(sizeof(NodeType));
4. After getting the memory successfully stored the data in the data field as per the requirement.
if(pNewNode != NULL)
{
pNewNode->iData = Value;
}
5. For the linking, assign the address of the node which is next to the tmp node to the newly created node.
pNewNode->pNextNode = pTmpNode->pNextNode;
6. Assign the address of the new node to the tmp node.
pTmpNode->pNextNode = pNewNode;
/* Paas the reference of the tempnode pointer of a list and
an integer data*/
int InsertNodeAfterNode(NodePointer * pHead, int iUserData,unsigned int iPosition)
{
int iRetValue = -1;
NodePointer pTmpNode = NULL;
unsigned int iCount = 0;
//Give the Address of first Node
pTmpNode = *pHead;
for( iCount = 1; ((iCount < iPosition) && (pTmpNode!= NULL)) ; iCount++)
{
pTmpNode = pTmpNode ->pNextNode;
}
/* check the pTmpNode*/
if (pTmpNode == NULL)
{
printf("Enter Position is Invalid\n");
return iRetValue;
}
else
{
/* allocate memory for the new node */
NodePointer pNewNode = malloc(sizeof(NodeType));
if( pNewNode != NULL)
{
//put in the data
pNewNode->iData = iUserData;
//Assign the address of next node to the new node
pNewNode->pNextNode = pTmpNode->pNextNode;
// Assign the address of new node to the previous node
pTmpNode->pNextNode = pNewNode;
iRetValue = 0;
}
}
return iRetValue;
}
Insert a node at the end of the linked list
In the linked list, we can easily append the newly created node. Below I have mention steps to append the newly created node in the linked list.
1. Create a node pointer and assigned the address of the first node which is stored by the head pointer.
NodePointer pTmpNode = head;
2. Increment the address of temporary node pointer till not get the address of the last node.
While( pTmpNode ->pNextNode != NULL)
{
pTmpNode = pTmpNode ->pNextNode;
}
3. Allocate the memory in the heap for the new node.
NodePointer pNewNode = malloc(sizeof(NodeType));
4. After getting the memory successfully stored the data in the data field as per the requirement.
if(pNewNode != NULL)
{
pNewNode->iData = Value;
}
5. For the linking, assign the address of the newly created node to the tmp node.
pTmpNode->pNextNode = pNewNode;
6. In the last assigned the NULL to the newly created node as mark the end of the linked list.
pNewNode->pNextNode = NULL;
Note: Don’t forget to free the allocated memory.
Free the Allocated memory
/* 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;
}
In below program, I am creating a linked list where I am adding the node at the beginning, end and at any position of the linked list.
// A simple C program to introduce a linked list
#include<stdio.h>
#include<stdlib.h>
// Creating Node
struct Node
{
/*Data field*/
int iData;
/*Node Pointer*/
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. This function use to add the node at the beginning*/
int InsertNodeAtBeginning(NodePointer * pHead, int iUserData)
{
int iRetValue = -1;
// Call malloc to allocate memory in heap for the new node
NodePointer pNewNode = malloc(sizeof(NodeType));
if( pNewNode != NULL) //Check allocated memory
{
pNewNode->iData = iUserData; //put the desire Data
pNewNode->pNextNode = *pHead; //Give the Address of first Node
*pHead = pNewNode; // Assign the Address of New Node to Head
iRetValue = 0; // Update the return value
}
return iRetValue;
}
/* Paas the reference of the tempnode pointer of a list and
an integer data*/
int InsertNodeAfterNode(NodePointer * pHead, int iUserData,unsigned int iPosition)
{
int iRetValue = -1;
NodePointer pTmpNode = NULL;
unsigned int iCount = 0;
//Give the Address of first Node
pTmpNode = *pHead;
for( iCount = 1; ((iCount < iPosition) && (pTmpNode!= NULL)) ; iCount++)
{
pTmpNode = pTmpNode ->pNextNode;
}
/* check the pTmpNode*/
if (pTmpNode == NULL)
{
printf("Enter Position is Invalid\n");
return iRetValue;
}
else
{
/* allocate memory for the new node */
NodePointer pNewNode = malloc(sizeof(NodeType));
if( pNewNode != NULL)
{
//put in the data
pNewNode->iData = iUserData;
//Assign the address of next node to the new node
pNewNode->pNextNode = pTmpNode->pNextNode;
// Assign the address of new node to the previous node
pTmpNode->pNextNode = pNewNode;
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("\nLinked List is: \n\n");
while (pNode != NULL)
{
printf("\n %d\n\n",pNode->iData);
pNode = pNode->pNextNode;
}
system("pause");
}
//Create a linked list of certain number of nodes
int CreateLinkedList(NodePointer *pHead, int iNumberofNode)
{
int iData = 0;
int iRetValue = -1;
int iCount = 0;
for(iCount =0; iCount < iNumberofNode; iCount++)
{
/*Enter desire data*/
printf("\n\nEnter the Data = ");
scanf("%d",&iData);
if((*pHead) == NULL)
{
//Create First Node
iRetValue = InsertNodeAtBeginning(pHead,iData);
}
else
{
//Add the Node at the End
iRetValue = InsertNodeAtEnd(pHead,iData);
}
}
return iRetValue;
}
/* Driver program to test above functions*/
int main(void)
{
int iChoice = 0;
int iNumberNode =0;
int iData = 0;
int iPosition =0;
/*Start with the empty list */
NodePointer head = NULL;
while(1)
{
//Select the Choice as per the requirements
printf("\n\n\
1: Create the Linked List\n\
2: Display The Linked List\n\
3: Insert Node at the begninig of Linked list\n\
4: Insert Node at the End of Linked List \n\
5: insert Node After a Node \n\
6: terminatethe process \n\n\n");
printf("\n\nenter your choice = ");
scanf("%d",&iChoice);
switch(iChoice)
{
case 1:
printf("\n\nEnter the number of nodes = ");
scanf("%d",&iNumberNode);
CreateLinkedList(&head,iNumberNode);
break;
case 2:
PrintTheList(head);
break;
case 3:
printf("\n\nEnter the desired data = ");
scanf("%d",&iData);
InsertNodeAtBeginning(&head,iData);
break;
case 4:
printf("\n\nEnter the desired data = ");
scanf("%d",&iData);
InsertNodeAtEnd(&head,iData);
break;
case 5:
printf("\n\nEnter the Position = ");
scanf("%d",&iPosition);
printf("\nEnter the desired data = ");
scanf("%d",&iData);
InsertNodeAfterNode(&head,iData,iPosition);
break;
case 6:
printf("\n\nFree the all Allocated memory\n");
FreeAllocatedMemory(&head);
printf("\n\nprocess is terminated\n ");
exit(1);
break;
}
}
return 0;
}
OutPut:
1. Create a linked-list using two nodes.
