Insertion in Linked List

#linkedlist #arrays

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.
malloc assigns 8-bytes of locations whose starting address is stored into pointer newnode of type struct node.
Enter the data into that newly created node by accessing the structure member data using pointer newnode.
Now to insert this new node at the beginning, copy the pointer head into the address part of newly created node and copy the pointer newnode into pointer head.
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.
malloc assigns 8-bytes of locations whose starting address is stored into pointer newnode of type struct node.
Enter the data into that newly created node by accessing the structure member data using pointer newnode.
To add this new node at the end of linked list, initialize the address part of newly created node to NULL and copy the pointer head into pointer temp.
Now pointer temp is pointing to the first node so move this pointer temp from first node to the last node using while loop. Once the temp points the last node, copy the pointer newnode into the address part of last node by accessing the structure member next using pointer temp.
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 as pos.
If pos (entered position) is greater than the number of nodes in the linked list, then print invalid position.
If pos (entered position) is less than the number of nodes in the linked list, then create a new node using malloc.
Enter the data into that newly created node by accessing the structure member data using pointer newnode.
Initialize the address part of the newly created node to NULL and copy the pointer head into pointer temp so that temp points to the first node in the list.
Initialize an integer variable i to 1. Now, simultaneously keep incrementing the variable i and moving the pointer temp from first node until variable i is less than the entered position pos value using while loop.
Copy the address part of a node to which pointer temp is pointing into the address part of a new node to which pointer newnode is pointing by accessing structure member next.
Copy the newnode into the address part of a node to which temp is pointing by accessing a structure member next.
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.