A Doubly Linked List (DLL) is very similar to a Linked List, but contains an extra pointer, typically referred to as previous pointer, together with next pointer and the data.
Advantages over singly linked list
- A doubly linked list can be traversed in both forward and backward direction.
- The delete operation for doubly linked lists is more efficient if pointer to the node to be deleted can be supplied.
- Quickly insert a new node before a given node.
- In a singly linked list, to delete a node, the pointer to the previous node is needed. To get the previous node, the list has to be traversed from the beginning. Whereas the doubly linked list can fetch the previous node using previous pointer.
DisadvantageS
- Every node of the doubly linked list requires extra space for the previous pointer.
- All operations have additional overhead because of the extra previous pointer. For example, in insertion, we need to modify previous pointers together with next pointers.
Insertion
A node can be added in four ways:
- At the front of the DLL
- After a given node.
- At the end of the DLL
- Before a given node.