LRU cache

Evict the least-recently-used item when full. Hash map + doubly-linked list = O(1) everything.

Two O(1) needs, no single structure

• Look up by key, fast → hash map (but no order)
• Track & update recency, fast → linked list (but O(n) lookup)
• Combine: map key → node in a doubly-linked list ordered by recency
• Front = most recent · back = least recent (eviction victim)

Watch the recency list

put E (full) → evict B (back, least recent). get A → move A to front. The front fills with what you use; the back is what you evict.

Why LRU: hit rate

Skewed (Zipf) workload, cap 50: LRU 71% vs FIFO/random 65%. Recency predicts reuse.

Doubly-linked is load-bearing

• Eviction & move-to-front need O(1) removal of a MIDDLE node
• Singly-linked can't (needs the predecessor) → must be doubly-linked
• Sentinel head/tail avoid edge cases
• Blind spot: SCANS pollute the cache → ARC / 2Q / LRU-K variants

Takeaway

Two structures sharing nodes meet a two-part requirement — the composition pattern. OrderedDict / functools.lru_cache ARE this under the hood. Next: k-d trees — nearest-neighbour search by partitioning space.