A doubly linked list gives each node two pointers — next and prev — so you can traverse in both directions and delete a node in O(1) when you already hold a reference to it (no need to walk from the head to find the predecessor).
Structure
text
null <- [10] <-> [20] <-> [30] -> null
prev/next links in BOTH directions
O(1) deletion of a known node
python
class Node:
def __init__(self, val):
self.val, self.prev, self.next = val, None, None
def remove(node): # O(1) — no traversal needed
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
In a singly linked list, deleting a node requires finding its predecessor first → O(n).
Comparison
| Aspect | Singly | Doubly |
|---|---|---|
| Pointers per node | 1 (next) | 2 (next, prev) |
| Traverse backward | no | yes |
| Delete known node | O(n) | O(1) |
| Memory overhead | lower | higher |
When to use
- Doubly: LRU caches, browser history, undo/redo, and any structure needing O(1) removal from the middle.
- Singly: when memory is tight and you only move forward.
Why it matters
The O(1) splice-out of a known node is the key property that makes doubly linked lists the partner of hash maps in an LRU cache.
The extra prev pointer trades memory for the flexibility of bidirectional movement and constant-time deletion.