LRU Cache — Least Recently Used Eviction in O(1)

Why it matters

Every caching system needs an eviction policy. LRU is the most common because it's simple, effective, and O(1) with the right data structure. Understanding it is basic infrastructure knowledge.

The architecture

Data structures: hash map keys → list nodes (O(1) lookup), doubly-linked list (O(1) move-to-front and remove).

Get: hash lookup finds node; move node to front of list.

Put: if capacity exceeded, remove tail (LRU item); add new to front.

How it works end to end

Alternatives: LFU (least frequently used), FIFO, Random, ARC (adaptive replacement), CLOCK. Each has different characteristics.

Thread safety: needs lock for concurrent access. Segmented LRU or CLOCK approximations reduce contention.

Applications: OS page cache, DB buffer pool, Redis eviction, CDN caching, Java Guava CacheBuilder.