Doubly Linked List – Explanation and Implementation

A doubly linked list is an advanced form of linked list which has the ability to traverse back and forth i.e. in both the direction. It possesses an extra pointer Prev in addition to the fields of a node in singly linked list. Conventionally, in a singly and circular linked list, Data and Next are two parts of a node. But, doubly linked list defines three Data, Next and Prev and the meaning of each section is as follows-

• Prev – Points to previous node
• Data – Containing data
• Next – Pointing next node

This Prev part makes this linked list has a huge implementation in many places.

Read – Linked List Types – Explanation

Structure and Declaration

struct node {
   int data;
   struct node *next;
   struct node *prev;
}

Implementation in C language

#include<stdio.h>
#include<stdlib.h>
 
//DECLARATION
struct node 
{
    int data;
    struct node *next;
    struct node *prev;
};
 
 //This function prints the content of linked list--forward direction
void printLLForward(struct node *list)
{   
   while (list)
    {
        printf(" %d ", list->data);
        list = list->next; // accessing and assigning the next node of list
    }
}
 
// This function prints the linked list--backward direction
void printLLBackward(struct node *list)
{
 
    while (list->next != NULL)
    {
        list = list->next;
    }
 
   while (list)
   {
       printf(" %d ", list->data);
       list = list->prev; // accessing and assigning the prev node of list
   }    
}
 
// Main method to initialize the program
int main()
{
    //INITIALIZATION
    //Declare and allocate 3 nodes in the heap 
    struct node* head;
    struct node* first = (struct node*)malloc(sizeof(struct node));
    struct node* second = (struct node*)malloc(sizeof(struct node));
    struct node* third = (struct node*)malloc(sizeof(struct node));
     
    //ASSIGNINMENT
    first->data = 10; //assign data in first node
    first->next = second; // Link first node with second
    first->prev = NULL;
     
    second->data = 20; //assign data to second node
    second->next = third;
    second->prev = first; 
     
    third->data = 30; //assign data to third node
    third->next = NULL; // last node pointing to the first node
    third->prev = second;
 
    head = first;    //head pointing to the linked list
     
   printf("Printing the linked list in forward direction :\t");
   printLLForward(head);
   printf("\nPrinting the linked list in backward direction:\t");
   printLLBackward(head);
     
    return 0;
}

Output:-
Printing the linked list in forward direction :	 10  20  30 
Printing the linked list in backward direction:	 30  20  10

Note:-
Many a times Circular doubly linked list is used where Next of last node rather points to Prev of the first node. As a result, no need to traverse back if required to traverse again.

Advantages:

1. Insertion/Deletion takes O(1) most of the time.
2. Linked list reversal is easy.
3. Better access of nodes as back and forth traversing can be done anytime.

Disadvantages:

1. Consumes more memory as each node causes to have two addresses. Also, there is a Memory Efficient Doubly linked list known as XOR linked list, using which only one address is used. It merges the Prev and Next Address using XOR operation as a result only single address is used. Thus, memory consuming is no longer a problem.
2. Because of Prev and Next two addresses system, it is a bit of overhead. Every time both the addresses have to be provided to a node.

Note:-
There is a type of linked list called as Multilevel linked list, where a node can point to any number of nodes as required. Doubly linked list is basically a special type of Multilevel linked list.

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂

Recommended -