Start here: the problem it solves#
TL;DRthe 30-second version
- An LRU cache holds a fixed number of entries. When a new key arrives and the cache is full, it evicts the least-recently-used entry — the one whose last access is oldest.
- The goal is that get, put, and evict are all O(1). Two obvious designs fail: an array ordered by recency needs an O(n) shift to move a touched entry to the front, and a plain map has no order to evict by.
- The answer pairs two structures. A hash map takes a key to its node in one step. A doubly-linked list keeps the nodes in recency order, so the touched node can be unlinked and spliced to the front, and the tail node evicted, each in constant time.
- The map finds the node; the list reorders it. Neither can do the job alone, and together they need only a few pointer writes per operation, which is the O(1) an interviewer is asking you to derive.
You are putting a cache in front of a slow store — a database, a disk, a remote service. The cache has room for only so many entries, far fewer than the store holds, so it has to decide what to keep. A good, simple rule is to keep what you have used recently and drop what you have not: least-recently-used eviction. When the cache is full and a new key comes in, throw out the entry nobody has touched in the longest time.
The policy is the easy half. The hard half is speed. This cache sits on a hot path, so every single get and put has to be fast — ideally constant time, independent of how many entries the cache holds. If a lookup or an update quietly costs time proportional to the cache size, the cache stops being a shortcut and becomes a tax on every request.
Try the obvious designs and watch them fall short. Keep the entries in an array ordered from most- to least-recently-used: a lookup has to scan the array to find the key (O(n)), and even once you find it, moving it 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, so 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#
Since each structure solves half the problem, 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, and its order is meaning, not accident: the node right after the head is the most-recently-used entry, and 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, whose value is a direct reference to that key's node in the list. This is the piece that makes lookups fast: given a key, the map hands back its node in one step, with no walking of the list. Once you hold the node, the list's pointers let you move it around in constant time. The map answers "where is this key's node?" and the list answers "what order are the nodes in?"
hash map doubly-linked list (most-recent first)
--------- -------------------------------------
"C" ─────────┐ head <=> [C] <=> [B] <=> [A] <=> tail
"B" ───────┐ └────────────^ ^
"A" ─────┐ └──────────────────────^ |
└────────────────────────── least-recently-used (evict here)Now walk the three operations. A get for a key that is present is a hit. The map finds its node in one step. Because this key was just used, it is now the most recently used, so it must move to the front of the list. Moving it is the signature move of the whole structure, and it happens in two stages. First unlink the node: its previous neighbor and its next neighbor are made to point at each other, closing the gap where the node sat. Then relink it at the front: the node's pointers are set to sit between the head and the old first node, and those two are pointed back at it. Six pointer writes in total — two to unlink, four to relink — and the list is never scanned, so a hit is O(1).
- GET (hit): ask the map for the key's node — one step, no scan.
- Unlink the node: its old neighbors point past it, lifting it out of the chain (two pointer writes).
- Relink it just behind the head: it is now the most-recently-used entry (four more pointer writes — its own two, plus the head and old-first pointers redirected at it).
- GET (miss): the map has no such key, so nothing moves and no pointers change.
A put for a key that is already present is almost the same: overwrite the value on its node, then splice that node to the front exactly as a hit does, because updating a key also counts as using it. A put for a brand-new key is where the cache's size cap bites. If there is room, create a node, link it in just behind the head, and add a key-to-node entry to the map. If the cache is already full, first evict: the least-recently-used node is the one right before the tail, so unlink it from the list and delete its key from the map, both in constant time, and only 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] <=> tailNotice that eviction never has to search for a victim. Because the list is kept in recency order on every access, the least-recently-used entry is always sitting in the same place — right before the tail — ready to be removed in one step. The work of keeping order is paid a little at a time, on each access, so that eviction itself is free.
Go deeperWhy the list must be doubly linked, and why the sentinels help
The list has to be doubly linked, with a previous pointer as well as a next one, and the reason is unlinking. To remove a node in one step you must reach both of its neighbors so they can be joined. With only next pointers you would know the node that follows, but to find the one before it you would have to walk the list from the head, which is the O(n) scan the whole design exists to avoid. The previous pointer is what makes an arbitrary-node removal constant time.
The head and tail are usually dummy sentinel nodes that hold no real entry and always exist. They earn their keep by erasing edge cases. Because a sentinel is always present on each end, every real node is guaranteed to have a node before it and a node after it, so a splice or an unlink can repoint neighbors without ever checking for a missing end. Inserting into an empty list, removing the only element, or moving the current front are all just the ordinary pointer dance, with no special-case branches to get wrong.
Complexity: constant time, and what it costs in space#
Get, put, and evict are each O(1). Not amortized O(1) and not average O(1), but worst-case constant time on every single call: a get is one map lookup plus at most six pointer writes; a put adds a node and maybe evicts one, again a fixed number of writes; eviction is a single unlink of a node whose location is already known. Nothing in any of these depends on how many entries the cache holds. There is no resize step and no rehash cascade, so unlike a growable array or a resizing hash table, there is not even an occasional expensive operation to amortize away.
The map lookup is itself O(1) on average rather than in the worst case, so strictly the guarantee inherits the hash table's average-case caveat. In practice that is the same constant every hash-backed structure lives with, and the linked-list half contributes a true worst-case constant on top of it.
| 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 |
Speed is bought with space and locality. Every entry carries two extra pointers for the list, plus its slot in the hash map, so the per-entry overhead is noticeably higher than a bare array. The nodes are also allocated separately and scattered across memory, so walking the list touches cache lines all over the heap, where an array would stream through contiguous memory. For a cache this rarely matters, because you almost never walk the whole list — you jump straight to a node through the map and touch only its immediate neighbors — but it is the reason a recency-ordered array can still win for very small, very hot caches.
PredictA colleague proposes dropping the doubly-linked list and instead storing, next to each value in the map, a timestamp of its last access. To evict, scan 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). With only timestamps, finding the least-recently-used key means scanning every entry in the map to find the smallest timestamp. Get and put are indeed still O(1), but a full cache evicts on almost every insert, so the O(n) scan runs constantly and dominates. The doubly-linked list exists precisely so the victim is always in a known place (right before the tail) and eviction stays O(1). The timestamp-scan idea is really the seed of the CLOCK approximation, which makes the scan cheap with a per-entry reference bit and a rotating hand instead of tracking exact order — a deliberate accuracy-for-speed trade the exact structure avoids.
Variants worth knowing
The map-plus-list LRU is the exact, textbook design. Real systems bend it in two directions: language libraries that package it, and large caches that approximate it to dodge its costs.
- Ordered-map wrappers — Java's LinkedHashMap is a hash map whose entries are also threaded on a doubly-linked list; construct it in access-order mode and override removeEldestEntry and you have an LRU cache in a few lines. Python's collections.OrderedDict does the same, exposing move_to_end and popitem for the two moves this page derived (functools.lru_cache is a separate C implementation with its own circular linked list, not built on OrderedDict).
- LFU (least-frequently-used) — instead of ordering by recency, order by how often each key is used, keeping a count per entry and buckets of equal-count keys. It protects a key that is popular over time but was not touched in the last moment, at the cost of more bookkeeping. The site's cache topic simulates LRU and LFU side by side as policies.
- CLOCK / second-chance — approximates LRU with a circular buffer and one reference bit per entry, so a read only flips a bit instead of doing pointer surgery. Eviction sweeps a hand around the clock, giving recently-touched entries a second chance. It trades exact recency order for far cheaper reads, which is why operating-system page caches use it.
- Segmented LRU, 2Q, and ARC — split the cache into a probationary list for new entries and a protected list for proven ones, so a one-off scan of many cold keys cannot flush everything useful. ARC (adaptive replacement cache) tunes the split automatically and is used in ZFS and several databases.
- TinyLFU / W-TinyLFU — front an LRU-style cache with a compact frequency sketch (a count-min-style estimator) that decides whether a new entry even deserves admission, giving near-optimal hit rates with tiny metadata. It backs Caffeine, the standard high-performance Java cache.
Trade-offs and when to reach for it
Exact LRU is the right default for a bounded in-memory cache of moderate size where you want simple, predictable behavior and every operation to be constant time. It is the wrong default the moment reads are extremely hot and concurrent, or the cache is enormous, because its costs are paid on the read path.
- For: a bounded cache that needs O(1) get, put, and evict with exact recency order — application-level caches, per-request memoization, session stores, and the classic interview answer. Simple to reason about and simple to get right.
- Against (read-heavy concurrency): every get moves a node to the front, which is a write. Under many threads that write turns the list into a point of contention, and the lock protecting it can serialize reads that would otherwise run in parallel. Approximations like CLOCK exist largely to make reads read-only.
- Against (very large caches): two pointers plus a map slot per entry is significant overhead across millions of entries, and the scattered nodes hurt memory locality. Sampling-based approximations (Redis) or sketch-based admission (TinyLFU) keep the hit rate without the per-entry list.
- Against (scan resistance): plain LRU is fooled by a single large scan of cold keys, which evicts the genuinely hot set. Segmented LRU, 2Q, and ARC exist specifically to resist that.
The duo vs an array, a plain list, and a lone map
| Map + doubly-linked list | Recency-ordered array | Doubly-linked list alone | Hash map alone | |
|---|---|---|---|---|
| Find a key | O(1) via map | O(n) scan | O(n) scan | O(1) |
| Move touched entry to front | O(1) splice | O(n) shift | O(1) once found | No order to move |
| Evict least-recently-used | O(1) tail | O(1) end | O(1) tail | Cannot choose a victim |
| What is missing | Nothing (but 2 pointers/entry) | Fast find + cheap move | Fast find | Any recency order |
Read the table down the last row. The array can evict cheaply but cannot find or reorder cheaply. The lone list can move and evict cheaply but cannot find cheaply. The lone map can find cheaply but has no order at all. Only the pairing has every cell fast, because the map supplies the fast find that the list lacks, and the list supplies the fast reorder and evict that the map lacks. That is the entire reason two structures are used where it looks like one should do.
Where this structure runs in the wild
- Java LinkedHashMap — a HashMap whose entries are also linked in a doubly-linked list; with accessOrder set to true it is an exact LRU, and overriding removeEldestEntry turns it into a fixed-capacity cache. This is the map-plus-list structure, shipped in the standard library.
- Python functools.lru_cache — the decorator that memoizes a function is backed by a hash map plus its own circular doubly-linked list of entries (a C implementation, not OrderedDict), moving a key to the front on each hit and dropping the oldest when full.
- Redis — does not keep an exact LRU list, because a pointer write on every read across millions of keys is too costly. Instead it stores a last-access clock per key and, on eviction, samples a handful of random keys and drops the oldest of the sample. It is an approximation tuned to trade a little accuracy for a lot of speed and memory, and newer versions also offer an approximated LFU (though the default eviction policy is still noeviction).
- Operating-system page caches — Linux does not run exact LRU on every page for the same reason; it uses two lists (active and inactive) with reference bits, a CLOCK-style second-chance scheme, so a page access only sets a bit instead of relinking a node.
- Caffeine and other high-performance caches — use W-TinyLFU, fronting an LRU-like eviction with a compact frequency sketch that admits only entries likely to be reused, reaching hit rates close to the theoretical optimum.
Common misconceptions & gotchas
Why not just use an array ordered by recency? It is simpler.
Because two of the three operations become O(n). Finding a key in the array is a linear scan, and moving a touched entry to the front means shifting every entry above it down one slot. On a hot cache those linear costs dominate. The map removes the scan and the linked list removes the shift, which is the whole point of using both.
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 lets you go forward. Without a previous pointer you would walk from the head to find the predecessor, which is O(n) — exactly the cost the structure is built to avoid. The previous pointer is what makes arbitrary-node removal constant time.
Is a get really O(1)? It performs a write, which feels wrong for a read.
Yes, it is O(1): one map lookup and a fixed number of pointer writes, none of it dependent on cache size. But you are right that a read mutating the structure is unusual, and it has a real consequence. Under concurrency that per-read write needs synchronization, so hot concurrent reads contend on the list. That single fact is why large-scale caches often approximate LRU with schemes whose reads are truly read-only.
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. That indirection is essential: it is what lets a lookup land directly on the node so the list pointers can move it. If the map stored bare values, you would find the value quickly but still have no handle on its position in the list to reorder or evict it.
How is this different from the cache topic's LRU simulation?
The cache topic shows the policy — which key gets evicted and why recency is a good guess at future use. This topic shows the machinery underneath that policy: the two structures side by side and the exact pointer writes that move a node to the front or drop it from the tail. One teaches what LRU does; this one teaches how it is made O(1).
QuizYou profile an LRU cache and find that inserts are fast but the cache spends most of its time in eviction. You discover the previous author replaced the doubly-linked list with just the hash map plus a last-used timestamp on each value. What is the fix?
- Use a faster hash function for the map
- Restore a doubly-linked list in recency order so the victim is always at the tail
- Increase the cache capacity so eviction runs less often
- Store the timestamp as an integer instead of a date
Show answer
Restore a doubly-linked list in recency order so the victim is always at the tail — Without the list, finding the least-recently-used key means scanning every entry for the smallest timestamp — O(n) per eviction, and a full cache evicts on nearly every insert. Restoring the doubly-linked list keeps the entries in recency order so the victim is always right before the tail and eviction is O(1) again. A faster hash, more capacity, or a cheaper timestamp type do not change the O(n) scan that is the actual bottleneck.
In an interview
Lead with the shape: an 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 the nodes in recency order so you can move a node to the front or drop the tail in constant time. State up front that neither structure can do it alone, because that framing is the answer to "why two structures?" before it is asked.
Then be ready to draw the two moves. On a get hit, the map finds the node, you unlink it by pointing its neighbors at each other, and you relink it just behind the head — six pointer writes, no scan. On a put that overflows capacity, the least-recently-used node is right before the tail, so you unlink it and delete its key from the map, then insert the new node at the head. Mention the sentinel head and tail nodes; they remove the empty-list and single-element edge cases that otherwise trip people up at the whiteboard.
Have the sharp follow-ups ready. Why doubly linked? Because unlinking in O(1) needs the previous node. Why does the map store nodes and not values? So a lookup lands on the node and can reorder it. Is a get really O(1) even though it writes? Yes, and that per-read write is exactly why huge caches approximate LRU with sampling or CLOCK. Then open the simulator and step a hit: watch the node lift out of the chain and splice in behind the head, one pointer at a time.
References & further reading
- Wikipedia — Cache replacement policies (LRU) — LRU and its relatives (LFU, CLOCK, ARC, segmented LRU) with the trade-offs between them
- LeetCode 146 — LRU Cache — the canonical problem: implement get and put in O(1) — the map-plus-list structure
- Java — LinkedHashMap documentation — access-order mode and removeEldestEntry: a standard-library LRU built on this structure
- CPython — OrderedDict and lru_cache — how functools.lru_cache uses a doubly-linked list of entries with move-to-front
- Redis — Key eviction (approximated LRU/LFU) — why Redis samples instead of maintaining an exact LRU list, with the accuracy trade-off
- Caffeine — TinyLFU design (efficiency wiki) — W-TinyLFU: fronting LRU-style eviction with a frequency sketch for near-optimal hit rates
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.