Doubly Linked List

A doubly linked list (DLL) is a special type of linked list in which each node contains a pointer to the previous node as well as the next node of the linked list.

• Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence.
• Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer).
• A sample node in a doubly linked list is shown in the figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the following image.

Operations on doubly linked list :

Advantages of Doubly Linked List over the singly linked list :

• A DLL can be traversed in both forward and backward directions. 
• The delete operation in DLL is more efficient if a pointer to the node to be deleted is given. 
• We can quickly insert a new node before a given node. 

Disadvantages of Doubly Linked List over the singly linked list :

• Every node of DLL Requires extra space for a previous pointer.
• All operations require an extra pointer previous to be maintained. 

Applications of Doubly Linked List :

• It is used by web browsers for backward and forward navigation of web pages 
• LRU ( Least Recently Used ) / MRU ( Most Recently Used ) Cache are constructed using Doubly Linked Lists. 
• Used by various applications to maintain undo and redo functionalities.