Insertion in doubly linked list at the beginning

by

Compared to a singly linked list, more number of pointers are maintained in the doubly linked list, since every node of a doubly linked list contains double pointers. While inserting an element into the doubly linked list, there can be two scenarios, either the list is empty or it contains at least one element. To insert a node in the doubly linked list at the beginning, we can follow the below steps:

  • Use the below statement to allocate the space for the new node in the memory. 
    ptr = (struct node *)malloc(sizeof(struct node));
  • Now, we need to check whether the list is empty or not. If the condition head == NULL holds, the list is empty. And, the node will be inserted as the only node of the list, if the list is empty. This means that the prev and the next pointer of the node will point to NULL and the head pointer will point to this node. 
    ptr->next = NULL;  
ptr->prev=NULL;  
ptr->data=item;  
head=ptr;
  • If the condition head == NULL becomes false, then it is another scenario. In this case, we will use the below statements, to insert the node in the beginning. This means that the next pointer of the node will point to the existing head pointer of the node and the prev pointer of the existing head will point to the new node being inserted. 
    ptr->next = head;  
head→prev=ptr;

At last, we will assign null to the previous part of the node being inserted and will make the head point to this node. Here, the node being inserted must contain NULL in its prev pointer, because it is the first node of the list.

ptr→prev =NULL  
head = ptr

Algorithm:

  • Step 1:IF ptr = NULL
    Write OVERFLOW
    Go to Step 9
    [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 -> PREV = NULL
  • Step 6: SET NEW_NODE -> NEXT = START
  • Step 7: SET head -> PREV = NEW_NODE
  • Step 8: SET head = NEW_NODE
  • Step 9: EXIT

Example in C:

#include<stdio.h>  
#include<stdlib.h>  
void insertAtBeginning(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);  
        insertAtBeginning(item);  
        printf("\nPress 1 to insert more:\n");  
        scanf("%d",&choice);  
    }while(choice == 1);  
}  
void insertAtBeginning(int item)  
{  
 
   struct node *ptr = (struct node *)malloc(sizeof(struct node));  
   if(ptr == NULL)  
   {  
       printf("\nOVERFLOW");  
   }  
   else  
   {  
 
 
   if(head==NULL)  
   {  
       ptr->next = NULL;  
       ptr->prev=NULL;  
       ptr->data=item;  
       head=ptr;  
   }  
   else   
   {  
       ptr->data=item;  
       ptr->prev=NULL;  
       ptr->next = head;  
       head->prev=ptr;  
       head=ptr;  
   }  
}  
 
}

Output:

Enter the element to insert: 
2 
 
Press 1 to insert more: 
1 
 
Enter the element to insert: 
4 
 
Press 1 to insert more: 
1 
 
Enter the element to insert: 
6 
 
Press 1 to insert more: 
1 
 
Enter the element to insert: 
8 
 
Press 1 to insert more: