There are three possibilities of inserting a node in a linked list :
- Insert at beginning.
- Insert at end.
- Insert after a given position.
To understand the process of inserting a node in a linked list, you must have the knowledge of creating and displaying the linked list. To know the implementation of linked list click here.
Lets assume that the linked list is already created as shown in fig below,
Fig.1 Linked list
1. Inserting node at beginning :
To insert a node at beginning, first you need to create a one node using dynamic memory allocation function
malloc.mallocassigns 8-bytes of locations whose starting address is stored into pointernewnodeof typestruct node.Enter the data into that newly created node by accessing the structure member
datausing pointernewnode.Now to insert this new node at the beginning, copy the pointer
headinto the address part of newly created node and copy the pointernewnodeinto pointerhead.Display the newly created linked list.
void insertAtBeg(struct node **head)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter the data into new node : ");
scanf("%d", &newnode->data);
newnode->next = *head;
*head = newnode;
}
2. Inserting node at end :
To insert a node at end, first you need to create a node using dynamic memory allocation function
malloc.mallocassigns 8-bytes of locations whose starting address is stored into pointernewnodeof typestruct node.Enter the data into that newly created node by accessing the structure member
datausing pointernewnode.To add this new node at the end of linked list, initialize the address part of newly created node to
NULLand copy the pointerheadinto pointertemp.Now pointer
tempis pointing to the first node so move this pointertempfrom first node to the last node usingwhile loop. Once thetemppoints the last node, copy the pointernewnodeinto the address part of last node by accessing the structure membernextusing pointertemp.Display the newly created linked list.
void insertAtEnd(struct node *head, struct node *temp)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter the data into new node : ");
scanf("%d", &newnode->data);
newnode->next = NULL;
temp = head;
while(temp->next != 0)
{
temp = temp->next;
}
temp->next = newnode;
}
3. Inserting node after a given position :
Enter the position after which a node is to be inserted in the list and store that position value into any variable of type
int
Here, position variable is taken aspos.If
pos(entered position) is greater than the number of nodes in the linked list, then printinvalid position.If
pos(entered position) is less than the number of nodes in the linked list, then create a new node usingmalloc.Enter the data into that newly created node by accessing the structure member
datausing pointernewnode.Initialize the address part of the newly created node to
NULLand copy the pointerheadinto pointertempso thattemppoints to the first node in the list.Initialize an integer variable
ito1. Now, simultaneously keep incrementing the variableiand moving the pointertempfrom first node until variableiis less than the entered positionposvalue usingwhile loop.Copy the address part of a node to which pointer
tempis pointing into the address part of a new node to which pointernewnodeis pointing by accessing structure membernext.Copy the
newnodeinto the address part of a node to whichtempis pointing by accessing a structure membernext.Display the newly created linked list.
void insertAfterPos(struct node **head, struct node *temp, int count)
{
int pos, i=1;
printf("\nEnter the position after which the node is to be inserted : ");
scanf("%d", &pos);
if(pos>count)
{
printf("Invalid position.");
exit(0);
}
else
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter the data into new node : ");
scanf("%d", &newnode->data);
newnode->next = NULL;
temp = * head;
while(i<pos)
{
temp = temp->next;
i++;
}
newnode->next = temp->next;
temp->next = newnode;
}
}
C code that demonstrates the insertion in linked list :
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
int displayLL(struct node *head)
{
int num = 0;
struct node *temp;
temp = head;
temp=head;
while(temp!=0)
{
printf("%d ",temp->data);
temp = temp->next;
num++;
}
return num;
}
void insertAfterPos(struct node **head, struct node *temp, int count)
{
int pos, i=1;
printf("\nEnter the position after which the node is to be inserted : ");
scanf("%d", &pos);
if(pos>count)
{
printf("Invalid position.");
exit(0);
}
else
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter the data into new node : ");
scanf("%d", &newnode->data);
newnode->next = NULL;
temp = * head;
while(i<pos)
{
temp = temp->next;
i++;
}
newnode->next = temp->next;
temp->next = newnode;
}
}
void insertAtBeg(struct node **head)
{
struct node * newnode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter the data into new node : ");
scanf("%d", &newnode->data);
newnode->next = *head;
*head = newnode;
}
void insertAtEnd(struct node *head, struct node *temp)
{
struct node * newnode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter the data into new node : ");
scanf("%d", &newnode->data);
newnode->next = NULL;
temp = head;
while(temp->next != 0)
{
temp = temp->next;
}
temp->next = newnode;
}
int main()
{
struct node *head = 0, *newnode, *temp;
int n, choice, newdata;
// Create Linked List //
printf("Enter the number of nodes in the list : ");
scanf("%d", &n);
for(int i = 1; i<=n; i++)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data%d : ", i);
scanf("%d", &newnode->data);
newnode->next = 0;
if(head == 0)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
}
printf("--------------------------------\n");
printf("Linked list : ");
int count = displayLL(head);
printf("\nCount = %d", count);
printf("\nEnter '1' for inserting node at beginning.\nEnter '2' for inserting node at end.\nEnter '3' for inserting after given position.\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
{
insertAtBeg(&head);
printf("\nLinked list after inserting a node at beginning : ");
int count = displayLL(head);
break;
}
case 2:
{
insertAtEnd(head, temp);
printf("\nLinked list after inserting a node at end : ");
int count = displayLL(head);
break;
}
case 3:
{
insertAfterPos(&head, temp, count);
printf("\nLinked list after inserting node after specified pos : ");
int count = displayLL(head);
break;
}
}
}
I own a website www.coderlogs.com where in I write similar blogs so do visit this for more such blog posts.
Top comments (0)