← Back to the linked lists page
Doubly Linked List
Nodes point both ways, so any node can delete itself in O(1) once you hold a reference to it — the key to LRU caches.
What to know
- LRU cache = hashmap (key → node) + doubly linked list ordered by recency.
- Sentinel head and tail nodes eliminate all edge cases at both ends.
- Costs one extra pointer per node versus singly linked.
In the wild: Browser back/forward history, MRU lists, text editor gap navigation, OS page replacement.
Algorithms to reach for
LRU cache (hashmap + DLL)
O(1) per opO(1) get and put with eviction (LeetCode 146)
O(1) node unlink
O(1)Remove a known node without traversal
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.