Insertion in doubly linked list at the end

by

We need to ensure if the list is empty or it contains any element, before inserting a node in the doubly linked list at the end. To insert the node in the doubly linked list at the end, we can follow the below steps:

  • Use the below statement to allocate the memory for the new node, in which we are making the pointer ptr point to the new node being inserted. 
    ptr = (struct node *) malloc(sizeof(struct node));
  • The next step is to check if the list is empty or not. In case, the condition head == NULL holds, then the list is empty. This means that the node should be inserted as the only node of the list. The prev and the next pointer of the node will thus point to NULL. The head pointer, however, will point to this node. 
    ptr->next = NULL;  
ptr->prev=NULL;  
ptr->data=item;  
head=ptr;
  • Now, again if the condition head == NULL becomes false, we will insert the new node as the last node of the list. It means that, in this case, we need to traverse the whole list to reach the last node of the list. Use the below statement, to initialize the pointer temp to head and traverse the list by using this pointer. 
    temp = head;   
while (temp != NULL)  
{  
temp = temp → next;   
}
  • Only a few pointer adjustments are now required, to insert the new node ptr to the list. Currently, the pointer temp is pointing to the last node at the end of this while loop. Use the below statement, to make the next pointer of temp point to the new node being inserted, ptr. 
    temp→next =ptr;
  • Use the below statement, to make the previous pointer of the node ptr point to the existing last node of the list, temp. 
    ptr → prev = temp;
  • At last, use the below statement, to make the next pointer of the node, ptr, point to the null which is the new last node of the list. 
    ptr → next = NULL

Algorithm:

  • Step 1:IF PTR = NULL
    Write OVERFLOW
    Go to Step 11
    [END OF IF]
  • Step 2: SET NEW_NODE = PTR
  • Step 3: SET PTR = PTR -> NEXT
  • Step 4: SET NEW_NODE -> DATA = VAL
  • Step 5: SET NEW_NODE -> NEXT = NULL
  • Step 6: SET TEMP = START
  • Step 7: Repeat Step 8 while TEMP -> NEXT != NULL
  • Step 8:SET TEMP = TEMP -> NEXT
    [END OF LOOP]
  • Step 9: SET TEMP -> NEXT = NEW_NODE
  • Step 10: SET NEW_NODE -> PREV = TEMP
  • Step 11: EXIT

Example in C:

#include<stdio.h>  
#include<stdlib.h>  
void insertAtLast(int);  
struct node  
{  
    int data;  
    struct node *next;  
    struct node *prev;  
};  
struct node *head;  
void main ()  
{  
    int choice,item;  
    do   
    {  
        printf("\nEnter the element to insert:\n");  
        scanf("%d",&item);  
        insertAtLast(item);  
        printf("\nPress 0 to insert more elements.\n");  
        scanf("%d",&choice);  
    }while(choice == 0);  
}  
void insertAtLast(int item)  
{  
 
   struct node *ptr = (struct node *) malloc(sizeof(struct node));  
   struct node *temp;  
   if(ptr == NULL)  
   {  
       printf("\nOVERFLOW");  
 
   }  
   else  
   {  
 
        ptr->data=item;  
       if(head == NULL)  
       {  
           ptr->next = NULL;  
           ptr->prev = NULL;  
           head = ptr;  
       }  
       else  
       {  
          temp = head;  
          while(temp->next!=NULL)  
          {  
              temp = temp->next;  
          }  
          temp->next = ptr;  
          ptr ->prev=temp;  
          ptr->next = NULL;  
       }  
printf("\nNode Inserted Successfully!!\n");  
 
   }  
}

Output:

Enter the element to insert:
2
 
Node Inserted Successfully!!
 
Press 0 to insert more elements.
0
 
Enter the element to insert:
4
 
Node Inserted Successfully!!
 
Press 0 to insert more elements.
0
 
Enter the element to insert:
6
 
Node Inserted Successfully!!
 
Press 0 to insert more elements.
0
 
Enter the element to insert:
8
 
Node Inserted Successfully!!
 
Press 0 to insert more elements.
5