Interactive Lab · DSA & Algorithms

Keep what you just used, throw out what you haven't, the LRU cache

Your cache has room for only a few items. A new one arrives and the cache is full: who gets thrown out? The Least Recently Used rule says evict whatever you touched longest ago, because what you used a moment ago you'll probably use again. The trick interviewers want is doing it in O(1): a hashmap finds any key instantly, and a doubly linked list keeps keys in recency order, so a hit is "unlink, move to front" and an eviction is "drop the tail". Fire requests at it, then race it against plain FIFO on the exact same stream.

The setup, LeetCode 146, the design question that never goes away

Design a cache with a fixed capacity and two operations, both in O(1): get(key) returns the value (or a miss) and marks the key as just used; put(key, value) inserts or updates it, and if the cache is full, first evicts the least recently used key.

In the playground a get that misses behaves like a real app cache: it loads the value from the database and puts it in (a "read-through" cache). Two caches, LRU and FIFO (evict whatever went in first, no matter how often it's used), see every request side by side.

▶ The playground, stream requests and watch both caches

capacity 4

auto-play speed 3/s

access pattern

or type a key

Each box is a node in the doubly linked list: the head (left) is the most recently used key, the tail (right) is next to be evicted. The small chips above are the hashmap, one lookup jumps straight to the node. On a hit LRU unlinks the node and moves it to the head; FIFO leaves it where it is. On a miss with a full cache, the tail node drops out.

🧭 Where this fits

LRU eviction runs underneath almost everything fast: your CPU's caches and the operating system's page cache approximate it, Redis and Memcached offer it as an eviction policy, browsers and CDNs use it to decide which pages and images to keep, and database buffer pools are built around it. The hashmap + doubly-linked-list design is also the textbook answer to "how do you make both lookup and reordering O(1)?", which is why it is a placement-interview favourite at product companies. The hashmap half is the same idea as the Hashing lab.

The code that's actually running, a hashmap pointing into a linked list

🔮 Predict, then test

Pick hot keys + one-off reads and hit ⏩ +500 requests: compare the two hit rates. Then switch the pattern to looping scan, where the requests cycle through capacity + 1 keys in order, and fast-forward again. Predict LRU's hit rate on the scan before you press it. Why does keeping the most recent keys fail so completely here, and what does that tell you about when LRU is (and isn't) the right policy?

The takeaway

Your new mental model of the LRU cache

Two structures, one job each. The hashmap answers "where is key k?" in O(1). The doubly linked list answers "who is least recently used?" in O(1): it's always the node at the tail.
Why doubly linked? To unlink a node from the middle in O(1) you need its previous neighbour too. A singly linked list would force an O(n) walk to find it.
Sentinel head and tail nodes mean you never special-case an empty list or the first/last node. Every operation is a fixed handful of pointer writes, at most 6, whether the capacity is 4 or 4 million.
LRU bets on temporal locality. "Used recently ⇒ used again soon" holds for most real workloads, so LRU beats FIFO, which happily evicts your hottest key just because it arrived first.
The gotcha: a loop just bigger than the cache. Cycling through capacity + 1 keys makes LRU evict exactly the key you need next, a 0% hit rate. Databases fight this with scan-resistant variants (LRU-K, 2Q, ARC). In Python, OrderedDict with move_to_end or functools.lru_cache give you LRU for free, but in the interview, build the linked list.

← Hashing Placement prep →Try: Binary Heap