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.
struct node *next;
struct node *prev;
//This function prints the content of linked list--forward direction
void printLLForward(struct node *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;
printf(" %d ", list->data);
list = list->prev; // accessing and assigning the prev node of list
// Main method to initialize the program
//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));
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");
printf("\nPrinting the linked list in backward direction:\t");
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.
Insertion/Deletion takes O(1) most of the time.
Linked list reversal is easy.
Better access of nodes as back and forth traversing can be done anytime.
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.
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..
Doubly Linked List – Explanation and Implementation was last modified: August 27th, 2016 by Vivek Kumar