LRU Cache
A fixed-size cache that evicts the Least Recently Used item when full. A hash map gives O(1) lookup; a doubly linked list keeps recency order — together, O(1) get and put.
An LRU cache bounds memory by capacity and answers "get(key)" and "put(key, value)" in O(1), always evicting the item nobody has touched in the longest time when it needs room.
The classic implementation pairs a hash map (key → node) with a doubly linked list ordered by recency: the head is most-recently-used, the tail is least. Every get or put moves its node to the head in O(1) (unlink + relink, no shifting); eviction just removes the tail node and its hash entry.
Neither structure alone is enough: a hash map alone has no notion of order, and a linked list alone has no O(1) lookup. The pairing is what makes both operations O(1) — a recurring pattern anywhere you need "fast lookup" plus "fast reordering".
Operations
| Operation | Complexity |
|---|---|
| get(key) | O(1) |
| put(key, value) | O(1) |
| evict LRU | O(1) |
| space | O(capacity) |
Where it's used
CPU/OS page caches, database buffer pools, CDN edge caches, browser caches, in-memory memoization with bounded size.