The LRU Data Structure

Start here: the problem it solves#

TL;DRthe 30-second version

An LRU cache holds a fixed number of entries. When it is full and a new key arrives, it evicts the least-recently-used entry.
Get, put, and evict all need to be O(1). An array ordered by recency needs an O(n) shift to move a touched entry to the front. A plain map has no order to evict by.
So pair them. A hash map takes a key to its node in one step. A doubly-linked list keeps the nodes in recency order, so move-to-front and evict-from-tail are each a few pointer writes.

You are putting a cache in front of a slow store, say a database. The cache has room for far fewer entries than the store holds, so it has to decide what to keep. A simple rule is to keep what you used recently and drop what you did not. That is least-recently-used eviction. And because the cache sits on a hot path, every get and put has to be constant time, whatever the cache size.

Try the obvious designs first. Keep the entries in an array ordered from most- to least-recently-used. Now a lookup has to scan the array to find the key, which is O(n). And once found, moving that entry to the front means shifting every entry above it down a slot, O(n) again. Keep the entries in a hash map instead. Now the lookup is one step, but a map has no notion of order. When it is time to evict, you have no idea which key is the least recently used. Each structure solves exactly half the problem.

The mechanism: a map to find, a list to reorder#

Use both, and have them point at the same nodes. Every cache entry is a small node holding its key, its value, and two pointers: one to the node ahead of it and one to the node behind it. That is a doubly-linked list. Its order carries meaning. The node right after the head is the most-recently-used entry. The node right before the tail is the least-recently-used one, the eviction victim.

Alongside the list sits a hash map, keyed by the entry's key. Its value is a direct reference to that key's node in the list, not a copy of the cached value. Given a key, the map hands back its node in one step, with no walking of the list.

  hash map                doubly-linked list (most-recent first)
  ---------               -------------------------------------
  "C" ─────────┐   head <=> [C] <=> [B] <=> [A] <=> tail
  "B" ───────┐ └────────────^                 ^
  "A" ─────┐ └──────────────────────^         |
           └────────────────────────── least-recently-used (evict here)

the two structures point at the same nodes

Now the three operations. A get for a key that is present is a hit. The map finds its node in one step. That key was just used, so it must move to the front of the list. This is the signature move, and it has two stages. First unlink the node: point its previous neighbor and its next neighbor at each other, closing the gap. Then relink it at the front: set its two pointers to sit between the head and the old first node, and point those two back at it. Six pointer writes in total, two to unlink and four to relink. The list is never scanned, so a hit is O(1).

A put for a key that is already present overwrites the value on its node, then moves it to the front exactly as a hit does, because updating a key also counts as using it. A put for a new key is where the size cap bites. If there is room, create a node, link it in behind the head, and add the key-to-node entry to the map. If the cache is full, evict first. The least-recently-used node is the one right before the tail, so unlink it and delete its key from the map. Then insert the newcomer at the front.

  before (full, capacity 4):  head <=> [D] <=> [C] <=> [B] <=> [A] <=> tail
                                                              ^ least-recently-used
  step 1 unlink tail node A:  head <=> [D] <=> [C] <=> [B] <=> tail    (map deletes "A")
  step 2 insert E at head:    head <=> [E] <=> [D] <=> [C] <=> [B] <=> tail

evicting the tail on an insert past capacity

The head and tail are usually dummy sentinel nodes. They hold no entry and always exist, so every real node has a neighbor on both sides and there are no empty-list or single-element special cases.

That is the standard O(1) LRU cache. It is LeetCode 146, and it is the shape of Java's LinkedHashMap and Python's OrderedDict.

Complexity: constant time, and what it costs in space#

Get, put, and evict are each O(1) in the worst case, not amortized. A get is one map lookup plus at most six pointer writes. A put adds a node and maybe unlinks one whose location is already known. The one caveat is that the map lookup is O(1) on average, the same caveat every hash-backed structure lives with. Speed is bought with space: two extra pointers plus a map slot per entry.

Operation	Map-plus-list LRU	Array ordered by recency	Plain hash map
Get (find + mark used)	O(1)	O(n) scan + O(n) shift	O(1) find, but no recency
Put (insert, maybe evict)	O(1)	O(n) shift	O(1), but cannot pick a victim
Evict least-recently-used	O(1)	O(1) at the end, O(n) to maintain order	Impossible (no order)
Extra space per entry	2 pointers + map slot	None beyond the array	Map slot

PredictA colleague proposes dropping the doubly-linked list. Instead, store a last-access timestamp next to each value in the map, and evict by scanning the map for the smallest timestamp. Get and put stay O(1). What did they give up, and when does it bite?

Hint: Which operation just changed its cost, and how often does a full cache run it?

They made eviction O(n). Finding the least-recently-used key now means scanning every entry for the smallest timestamp. A full cache evicts on almost every insert, so that scan runs constantly and dominates. The doubly-linked list exists so the victim is always in a known place, right before the tail, and eviction stays O(1).

If this comes up in an interview#

The one-linerAn O(1) LRU cache is a hash map plus a doubly-linked list. The map takes a key to its node in one step. The list keeps nodes in recency order, so move-to-front and evict-from-tail are a few pointer writes.

Why not just use an array ordered by recency? It is simpler.

Because two of the three operations become O(n). Finding a key is a linear scan, and moving a touched entry to the front shifts every entry above it. The map removes the scan and the linked list removes the shift.

Why does the list need previous pointers? A singly-linked list is lighter.

Because unlinking a node in O(1) requires reaching the node before it, and a singly-linked list only goes forward. Without a previous pointer you would walk from the head to find the predecessor, which is the O(n) scan the structure exists to avoid.

Does the hash map store the values or the nodes?

The nodes. The map's value is a reference to the list node, not a copy of the cached value. If the map stored bare values, you would find the value fast but have no handle on its position in the list to reorder or evict it.

Is a get really O(1)? It performs a write, which feels wrong for a read.

Yes: one map lookup and a fixed number of pointer writes, none of it dependent on cache size. But under concurrency that per-read write needs a lock, so hot concurrent reads contend on the list. That is why large caches often approximate LRU with schemes whose reads are truly read-only.

Trade-offs and when to reach for it

Exact LRU is the right default for a bounded in-memory cache of moderate size. Its costs are paid on the read path, so it is the wrong default once reads are extremely hot and concurrent, or the cache is enormous. Plain LRU is also fooled by a single large scan of cold keys, which evicts the genuinely hot set.

Design	What a read costs	What you give up	Used by
Exact map + list (this page)	Six pointer writes under a lock	Contention under hot concurrent reads; 2 pointers per entry	Java LinkedHashMap (access-order mode), Python functools.lru_cache, LeetCode 146
CLOCK / second-chance	Flip one reference bit	Exact recency order	Linux page cache (active and inactive lists)
Sampled LRU	Update a per-key clock	Some accuracy: evicts the oldest of a few random keys	Redis (also offers an approximated LFU)
Segmented LRU, 2Q, ARC	Same as exact, on two lists	More bookkeeping, for scan resistance	ARC in ZFS and several databases
W-TinyLFU	Update a frequency sketch	Simplicity; admits only entries likely to be reused	Caffeine, the standard high-performance Java cache

The one-line decisionNeed a bounded cache with exact recency and constant-time operations, and reads are not brutally concurrent? Build the map-plus-list LRU. Need millions of entries, heavy concurrent reads, or scan resistance? Reach for an approximation.

References & further reading

References

LeetCode 146 — LRU Cache — the canonical problem: implement get and put in O(1) with the map-plus-list structure
Java — LinkedHashMap documentation — access-order mode and removeEldestEntry: a standard-library LRU built on this structure
Redis — Key eviction (approximated LRU/LFU) — why Redis samples instead of maintaining an exact LRU list
Caffeine — TinyLFU design (efficiency wiki) — W-TinyLFU: fronting LRU-style eviction with a frequency sketch

Up nextInverted Index

← Back to the learning path

Feedback on this topic →