LRU Cache
Constant-time lookup with eviction by recent use
Combine two structures
A least recently used cache keeps a hash table from keys to nodes and a doubly linked list in recency order. The hash table finds a key in expected O(1); the list removes or moves that known node in O(1).
Try it
3
val 30
↑ most recent
↑ least recent
2
val 20
↑ most recent
↑ least recent
1
val 10
↑ most recent
↑ least recent
Capacity 3/4
Entries run from most recently used on the left to least recently used on the right.
Every successful get moves its node to the most-recent end. A put updates or inserts there. When capacity is full, the node at the least-recent end is removed from both the list and the hash table.
Invariant: each cached key has exactly one list node, and list order always matches the order of most recent access.
LRU is useful when recent access predicts future reuse, including page caches, database buffer pools, and bounded memoization. It can perform poorly for scans larger than the cache.