Doubly Linked List
A doubly linked list extends the singly linked list by giving each node an additional prev pointer that points back to its predecessor. The list itself also maintains a tail pointer to the last node. Together, these two additions unlock O(1) operations at both ends and O(1) deletion whenever you hold a direct reference to a node.
Structure#
Each node holds three fields: its data, a next pointer to the following node, and a prev pointer to the preceding node. The list maintains a head pointer to the first node and a tail pointer to the last node, providing O(1) access to either end without any traversal.
Doubly Linked List Class
Core class structure: each node carries prev and next pointers, and the list maintains both head and tail. The size field is a convenience counter that avoids traversal when you only need the length.
Advantages Over Singly Linked List#
| Operation | Singly Linked | Doubly Linked | Improvement |
|---|---|---|---|
| Delete at Tail | O(n) | O(1) | Use tail.prev instead of traversing |
| Delete Given Node | O(n) | O(1) | Use node.prev to unlink directly |
| Traverse Backward | O(n) but needs O(n) space | O(n) | O(1) space with prev pointer |
| Insert Before Node | O(n) | O(1) | Use node.prev to find predecessor |
| Memory per Node | data + 1 pointer | data + 2 pointers | Cost: one extra pointer per node |
Traversal#
Because each node knows its predecessor, you can iterate from head to tail or from tail to head with equal ease. In a singly linked list, backward traversal requires collecting all nodes into a stack first (O(n) extra space). In a doubly linked list, it is simply O(n) time and O(1) space.
Bidirectional Traversal
Traverse forward from head to tail using next pointers, or backward from tail to head using prev pointers — both in O(n) time and O(1) space
Insertion#
Insertion into a doubly linked list requires updating both prev and next pointers on the affected nodes — more steps than in a singly linked list, but the payoff is O(1) insertion at both ends.
Insert at Head#
Insert at Head
Add a new node at the beginning. For a non-empty list, point the new node's next at the old head, update the old head's prev to the new node, then advance the head pointer. For an empty list, both head and tail point to the new node.
Insert at Tail#
Because we maintain a tail pointer, appending to the end is O(1) — no traversal needed. This is one of the most significant practical advantages over a singly linked list, where tail insertion requires walking the entire list.
Insert at Tail
Add a new node at the end. Point the new node's prev at the old tail, link the old tail's next to the new node, then advance the tail pointer. For an empty list, both head and tail point to the new node.
Insert at Position#
Insert at Position
Add a new node at a specific index (0-based). Inserting in the middle requires traversing to that position (O(n)) and then updating four pointers: new.prev, new.next, current.prev.next, and current.prev.
Deletion#
With prev pointers, deletion becomes simpler and more efficient — particularly at the tail and when deleting a node you already have a reference to.
Delete at Head#
Delete at Head
Remove the first node and return its data. Advance the head pointer to head.next, then clear its prev to null. If the list had only one node, set both head and tail to null.
Delete at Tail#
This is where the doubly linked list's prev pointer truly pays off. In a singly linked list, deleting the tail requires traversing the entire list to reach the second-to-last node. Here, tail.prev gives us that node directly — making deletion O(1).
Delete at Tail
Remove the last node and return its data. Move the tail pointer to tail.prev, then clear its next to null. If the list had only one node, set both head and tail to null.
Delete at Position#
Delete at Position
Remove and return the node at a specific index. For middle nodes, traverse to the target and unlink it by updating only two pointers: current.prev.next and current.next.prev. This is simpler than singly linked list deletion, which also requires tracking the predecessor during traversal.
Common Patterns#
Reverse Doubly Linked List#
Reversing a doubly linked list is straightforward: visit each node and swap its prev and next pointers. After all swaps, the old tail is the new head, and vice versa — so swap them too. No extra pointer variable is needed to track the previous node during traversal, because after the swap, current.prev is exactly where current.next used to point.
Reverse Doubly Linked List
Reverse the list in-place by swapping prev and next at every node, then swapping head and tail. After each swap, move forward by following current.prev (which is the original current.next).
LRU Cache Concept#
A classic application of the doubly linked list is the LRU (Least Recently Used) Cache — a fixed-size cache that, when full, evicts the item accessed least recently. By pairing a doubly linked list with a hash map, every cache operation (get and put) runs in O(1) time.
The key insight: the doubly linked list maintains access order (most recent at the head, least recent at the tail), and the hash map provides O(1) lookup by key. Because nodes have prev pointers, we can remove any node from the middle of the list in O(1) and move it to the front — no traversal needed.
A common implementation trick is to use dummy head and tail sentinel nodes that are never removed. This eliminates all the empty-list and boundary checks from _remove and _add_to_front.
LRU Cache Structure
Combining a doubly linked list (for O(1) move-to-front and O(1) evict-from-tail) with a hash map (for O(1) key lookup) gives O(1) time for every cache operation. Dummy sentinel nodes at the head and tail simplify the implementation by removing all boundary checks.
Complexity Summary#
The table below compares doubly and singly linked list performance. The key takeaways are the O(1) improvements at the tail and for node deletion — both made possible by the prev pointer.
| Operation | Singly Linked | Doubly Linked | Notes |
|---|---|---|---|
| Insert at Head | O(1) | O(1) | Same efficiency |
| Insert at Tail | O(n) | O(1) | Tail pointer benefit |
| Insert at Position | O(n) | O(n) | Must traverse to position |
| Delete at Head | O(1) | O(1) | Same efficiency |
| Delete at Tail | O(n) | O(1) | prev pointer benefit |
| Delete at Position | O(n) | O(n) | Must traverse to position |
| Delete Given Node | O(n) | O(1) | prev pointer benefit |
| Traverse Forward | O(n) | O(n) | Same efficiency |
| Traverse Backward | O(n) + O(n) space* | O(n) | O(1) space with prev |
| Memory per Node | data + 1 ptr | data + 2 ptrs | One extra pointer per node |
* Backward traversal in a singly linked list requires O(n) extra space (e.g., a stack) to first collect all nodes, then iterate in reverse
Reviewing AI-Generated Code#
Doubly linked list code is a common source of AI errors because every modification requires keeping two sets of pointers consistent. Understanding the invariants lets you spot mistakes quickly.
What to Verify#
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Both Pointers | Update both next AND prev on every affected node | Updating only next, leaving prev stale |
| Head/Tail Updates | Maintain both head and tail correctly after every operation | Stale tail pointer after deletion at tail |
| Single Node Case | Handle when head equals tail (list has exactly one node) | Not setting both head and tail to null when deleting the last node |
| Pointer Count | Middle insert/delete requires updating four pointers | Missing one of the four pointer updates |
| Null Boundaries | head.prev must be null; tail.next must be null | Leaving a dangling pointer that causes circular reference bugs |
Common AI Pitfalls#
Doubly Linked List Bugs
Common mistakes in doubly linked list code — two bugs AI tools frequently produce: forgetting to update prev pointers, and mishandling the single-node deletion case
Questions to Ask AI#
When AI generates doubly linked list code, verify:
- "Are all four pointers updated for middle insert/delete operations?"
- "What happens when head equals tail (single-node list)?"
- "Is head.prev null? Is tail.next null?"
- "Is the size counter updated on every insertion and deletion?"
- "Does backward traversal produce the correct results after this change?"
Summary#
| Concept | Key Takeaway |
|---|---|
| Structure | Each node holds data, next, and prev; the list keeps both head and tail |
| Head & Tail | Maintaining both pointers enables O(1) operations at either end |
| Bidirectional | Traverse forward or backward in O(n) time and O(1) space |
| Tail Operations | O(1) insert and delete at tail — a major advantage over singly linked |
| Node Deletion | O(1) when you hold a direct reference to the node |
| Trade-off | One extra pointer per node in exchange for significantly more flexibility |
| Use Cases | LRU cache, browser history, text editor undo/redo, deques |
Doubly linked lists trade a small amount of memory — one extra pointer per node — for significant flexibility: O(1) operations at both ends and O(1) deletion whenever you hold a node reference. They form the backbone of many practical data structures, from LRU caches to browser history stacks. When you encounter them in the wild, or in AI-generated code, you now know exactly what invariants to check.