What is a doubly linked list?
The limitations of singly linked lists
The singly linked list (SLL) is a linear data structure comprising of nodes chained together in a single direction. Each node contains a data member holding useful information, and a pointer to the next node.
The problem with this structure is that it only allows us to traverse forward, i.e., we cannot iterate back to a previous node if required.
This is where the doubly linked list (DLL) shines. DLLs are an extension of basic linked lists with only one difference:
A doubly linked list contains a pointer to the next node as well as the previous node. This ensures that the list can be traversed in both directions.
The doubly linked list class
From the definition above, we can see that a DLL node has three fundamental members:
- the data
- a pointer to the next node
- a pointer to the previous node
A DLL costs more in terms of memory due to the inclusion of a p (previous) pointer. However, the reward for this is that iteration becomes much more efficient.
Time Complexity
The worst case complexity for search, insertion, and deletion is O(n). Insertion and deletion at the head can be done in O(1).
