LRU Cache Design

A fixed-size cache that evicts the least recently used entry, with O(1) get and put from a hash map and a doubly linked list.

Overview

An LRU cache holds at most capacity entries. When it is full and a new key arrives, it throws out the entry that was used longest ago. The bet is that recent use predicts future use, which holds for most caches in front of a database or an API.

The design question is one of the most common in low-level design interviews because it has a clean answer with a clear reason. Each operation must be O(1), and no single standard structure gives that: a hash map finds a key fast but keeps no order, and a list keeps order but finds a key slowly. The fix is to use both, pointing at the same nodes.

Why two structures

Hash map — O(1) — No order to move in — Unknown which is oldest
Array or singly linked list — O(n) search — O(n) to find and remove — O(1) at one end
Doubly linked list — O(n) search — O(1) once you hold the node — O(1) at the tail
Hash map plus doubly linked list — O(1) map lookup — O(1): unlink the node, insert at head — O(1): remove the tail node and its map entry

The doubly linked list matters because removing a node from the middle needs both its neighbors, and the map hands you the node directly, not its position.

A trace with capacity 2

Read the list column as most recent on the left and the eviction candidate on the right.

1 — put(1, a) — 1 — 1
2 — put(2, b) — 2, 1 — 1, 2
3 — get(1) — 1, 2 — 1, 2 — a
4 — put(3, c) — 3, 1 — 1, 3 — evicts 2
5 — get(2) — 3, 1 — 1, 3 — -1
6 — put(1, z) — 1, 3 — 1, 3 — updates in place
7 — get(3) — 3, 1 — 1, 3 — c

Step 3 is the whole point of LRU: reading key 1 saved it, so key 2 was the one evicted at step 4.

An implementation that runs

Two sentinel nodes, head and tail, sit at the ends so that unlinking and inserting never check for None. The node stores its key so that evicting the tail node can also delete the map entry.

The standard library already has it

Python collections.OrderedDict — move_to_end(key) and popitem(last=False) — The docs say it is suited to LRU caches; a full cache is about ten lines
Python functools.lru_cache(maxsize=128) — Memoizes a function with LRU eviction — Thread-safe; maxsize=None disables eviction
Java LinkedHashMap(capacity, loadFactor, true) — Access-order iteration — Override removeEldestEntry to evict when size() > MAX

In an interview, build the linked-list version first; then say which library call you would use in production and why the hand-built one is only for the interview.

What you will be able to do

Explain in one minute why a hash map and a doubly linked list together give O(1) get and put.
Write the cache from memory with sentinel nodes and no null checks.
Trace a sequence of operations on paper and say which key is evicted and why.
Make it thread-safe, add a TTL, and compare LRU with LFU and FIFO.
Name the library class that does this in Python and Java.

Interview questions

Walk through the O(1) design and show the shortest correct implementation.
How would you make the cache thread-safe, and why does a read-write lock not help?
Compare LRU, LFU and FIFO. When would you choose each?
How would you add TTL (expiry) to the cache?
How does this change when the cache is distributed across many machines?