Insertion in singly linked list after specific Node

  • At first, we need to move the pointer at the position after which the node will be inserted, by skipping the desired number of elements in the list, for inserting an element after the specified number of nodes into the linked list. For this, we can use the below statements.
    customer=head;  
       for(i=0; inext;  
          if(temp == NULL)  
           {  
            return;  
           }  
         }  
    
  • We can then use the below statements to allocate the space for the new node and add the item to the data part of it.
    ptr = (struct node *) malloc (sizeof(struct node));  
    ptr->data = item;  
    
  • Only a few more link adjustments are required now. Currently, at the end of the loop, the loop pointer temp would be pointing to the node after which the new node will be inserted. Therefore, by using the below statements, we can add the address of the next part of the temp to the next part of the new node ptr. This is because the ptr will be in between temp and the next of the temp.
    ptr→ next = temp → next 
    
  • Finally, we will insert the new node ptr, at the specified position, by making the next part of the temp, point to the new node ptr.
    temp ->next = ptr; 
    

Algorithm:

  • STEP 1:
    IF PTR = NULL
    WRITE OVERFLOW
    GOTO STEP 12
    END OF IF
  • STEP 2: SET NEW_NODE = PTR
  • STEP 3: NEW_NODE → DATA = VAL
  • STEP 4: SET TEMP = HEAD
  • STEP 5: SET I = 0
  • STEP 6: REPEAT STEP 5 AND 6 UNTIL I
  • STEP 7: TEMP = TEMP → NEXT
  • STEP 8:IF TEMP = NULL
    WRITE “DESIRED NODE NOT PRESENT”
    GOTO STEP 12
    END OF IF
    END OF LOOP
  • STEP 9: PTR → NEXT = TEMP → NEXT
  • STEP 10: TEMP → NEXT = PTR
  • STEP 11: SET PTR = NEW_NODE
  • STEP 12: EXIT
  • Example in C:

    #include<stdio.h>  
    #include<stdlib.h>  
    void insertNode(int);  
    void createNode(int);  
    struct node  
    {  
        int data;  
        struct node *next;  
    };  
    struct node *head;  
    void main ()  
    {  
        int choice,item,loc;  
        do   
        {  
            printf("\nEnter the element to insert:\n");  
            scanf("%d",&item);  
            if(head == NULL)  
            {  
                createNode(item);  
            }  
            else  
            {  
                insertNode(item);  
            }  
            printf("\nPress 0 to insert more.\n");  
            scanf("%d",&choice);  
        }while(choice == 0);  
    }  
    void createNode(int item)  
    {  
     
            struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
            if(ptr == NULL)  
            {  
                printf("\nOVERFLOW\n");  
            }  
            else  
            {  
                ptr->data = item;  
                ptr->next = head;  
                head = ptr;  
                printf("\nNode inserted successfully!!\n");  
            }  
    }  
    void insertNode(int item)  
        {  
            struct node *ptr = (struct node *) malloc (sizeof(struct node));  
            struct node *temp;  
            int i,loc;  
            if(ptr == NULL)  
            {  
                printf("\nOVERFLOW");  
            }  
            else  
            {  
     
                printf("\nEnter the location:\n");  
                scanf("%d",&loc);             
                ptr->data = item;  
                temp=head;  
                for(i=0;i<loc;i++)  
                {  
                    temp = temp->next;  
                    if(temp == NULL)  
                    {  
                        printf("\nElement can't be inserted.\n");  
                        return;  
                    }  
     
                }  
                ptr ->next = temp ->next;   
                temp ->next = ptr;   
                printf("\nNode inserted successfully!!");  
            }  
     
        }

    Output

    Enter the element to insert:
    2
    
    Node inserted successfully!!
    
    Press 0 to insert more.
    0
    
    Enter the element to insert:
    4
    
    Enter the location:
    0
    
    Node inserted successfully!!
    Press 0 to insert more.
    0
    
    Enter the element to insert:
    3
    
    Enter the location:
    
    1
    
    Node inserted successfully!!
    Press 0 to insert more.
    0
    
    Enter the element to insert:
    1
    
    Enter the location:
    3
    
    Element can't be inserted.
    
    Press 0 to insert more.