A Doubly Linked List is a type of linked list where each node contains a data field and two pointers: one to the next node in the sequence (next pointer) and one to the previous node (prev pointer). This bidirectional linking allows for traversal in both directions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
{
"status": "Initializing Doubly Linked List"
}Overview
A doubly linked list gives each node two pointers: next to the following node and prev to the previous one. The list usually tracks both the head and the tail. The extra pointer costs memory but allows walking in both directions and removing a node in O(1) when you already hold a reference to it.
That O(1) removal is what makes it the standard companion of a hash map in an LRU cache: the map finds the node instantly, and the doubly linked list moves it to the front or evicts the tail without searching.
The default commands insert 10, 20 and 30, then delete 20. Deleting a middle node updates two pointers: 10.next now points to 30 and 30.prev points back to 10. The list ends as 10 <-> 30 with head 10 and tail 30.
Step by step
- Insert at the end: set
newNode.prev = tail,tail.next = newNode, thentail = newNode. - Delete a node: set
node.prev.next = node.nextandnode.next.prev = node.prev. - If the deleted node was the head or tail, move that pointer as well.
- Traverse forwards from the head with
next, or backwards from the tail withprev.
Complexity
| Case | Cost | Why |
|---|---|---|
| Access / search | O(n) | Still sequential, although you can start from either end. |
| Insert / delete at either end | O(1) | Head and tail pointers are kept. |
| Delete a known node | O(1) | Both neighbours are reachable directly. |
| Space | O(n) | Two pointers per node. |
When to use it
- LRU and LFU caches (paired with a hash map).
- Browser history or editors that need both back and forward navigation.
- Implementing a deque.
Common mistakes
- Updating
nextbut forgettingprev(or the reverse) corrupts backward traversal in ways that are hard to spot. - Edge cases: deleting the only node must set both head and tail to null.
- Sentinel head and tail nodes remove most of these special cases and are worth using.
A dry run is the best way to check your understanding of Doubly Linked List: follow each row, predict the next one, and compare. The run below takes 11 steps in total. The Line column refers to the line numbers in the code listing above.
- Input
- insert 10,insert 20,insert 30,delete 20
- Result
- status = Operations complete
| Step | Line | What happens |
|---|---|---|
| 1 | 1 | status = Initializing Doubly Linked List |
| 2 | 13 | action = insert(10) |
| 3 | 22 | status = Inserted 10, head = 10, tail = 10 |
| 4 | 13 | action = insert(20) |
| 5 | 22 | status = Inserted 20, head = 10, tail = 20 |
| 6 | 13 | action = insert(30) |
| 7 | 22 | status = Inserted 30, head = 10, tail = 30 |
| 8 | 13 | action = delete(20) |
| 9 | 13 | action = delete(20), status = Found 20 at index 1 |
| 10 | 13 | status = Deleted 20, head = 10, tail = 30 |
| 11 | 23 | status = Operations complete |
What is a Doubly Linked List?
What are the advantages of a Doubly Linked List over a Singly Linked List?
What are the disadvantages?
What does a node in a Doubly Linked List contain?
How does deletion work in a Doubly Linked List?
What are the time complexities for operations?
- Access/Search: O(n).
- Insertion/Deletion at beginning/end: O(1) (if a tail pointer is maintained).
- Insertion/Deletion at a given node: O(1).