In an O(1) LRU cache, why isn't a hash map alone enough, and what does the doubly linked list add?
answer
- Two structures, two different questions
- One is fast to find, one is ordered
- The map stores references, not payloads
- Which end holds the eviction victim?
- Unlinking from the middle needs both neighbours
basics
~20 sThe hash map gives O(1) lookup from key to node but knows nothing about recency. The doubly linked list orders nodes by last use, so the eviction victim sits at a known end and unlinking it costs O(1).
solid answer
~40 sThe two structures answer two different questions. The map answers "where is the entry for this key?" in expected O(1), but a hash map has no useful order, so it cannot tell you which entry was used longest ago. The doubly linked list answers "who is stalest?" by keeping nodes in recency order between a head sentinel (most recent) and a tail sentinel (least recent) — the victim is always the tail's predecessor. The map's values are node *references*, not raw payloads, which is what makes the two views the same objects: after a lookup you already hold the node, so relinking it to the recent end is pointer surgery, not a search. It must be doubly linked because unlinking a node you reached through the map requires its predecessor pointer.
go deeper
Be ready to say what each half is for in one breath: the map finds an entry fast, the list remembers what was used when. Know that the map's values are nodes, not payloads.
Explain the mechanics: which end is most recent, why removal needs a predecessor pointer, and how the node's stored key lets eviction clean up the map in constant time.
Demonstrate the cost honesty an interviewer probes for — expected versus worst-case constant time, the per-entry memory overhead of nodes and pointers, and the fact that reads mutate the structure.
Own the framing that this is a composition pattern, not a trick: two indexes over the same objects, each answering a query the other cannot, and be able to say when the overhead is not worth it.
## The requirement, stated precisely A bounded least-recently-used cache has to do three things quickly: 1. **Find** the entry for a key. 2. **Mark** that entry as the most recently used one. 3. **Identify and remove** the least recently used entry when the cache is full. No single classic structure does all three in constant time. That is why the answer is a *composition* of two, each covering the other's blind spot. ## What each half contributes A hash map gives you (1) in **expected O(1)** — worst-case O(n) if an adversary or a bad hash piles every key into one bucket, a caveat worth stating out loud. What it does not give you is any order at all. Iterating a plain hash map hands back entries in whatever arrangement the buckets happen to have; nothing in that arrangement correlates with when an entry was last touched. A doubly linked list gives you (3): if you *maintain* the list so that the most recently used node is at the front and the least recently used is at the back, the victim is simply the node before the tail. Unlinking it is a fixed number of pointer writes — **O(1) worst case**, no scan, no comparison, no clock reading. The glue is that the map does not store the cached payload directly. It stores a **reference to the list node**, and the node carries the key, the payload, and its two neighbour pointers. So a lookup lands you *inside* the list, holding the exact node you need to move. ## Walking a thumbnail cache Picture a photo service caching rendered thumbnails, keyed by `(photo id, size variant)`, capacity a few thousand entries. - **Read hit:** look up the key in the map (expected O(1)), take the node, unlink it from wherever it sits, splice it in right after the head sentinel, return its payload. Total: O(1) expected. - **Read miss:** render the thumbnail, then fall through to the write path. - **Write:** create a node, splice it after the head sentinel, store the reference in the map. If the entry count now exceeds capacity, take `tail.prev` as the victim, unlink it, and erase *its key* from the map — which is exactly why the node stores its own key. Every step is a constant number of pointer writes plus a constant number of expected-O(1) map operations. ## Why doubly linked, and why sentinels The map hands you a node, not a position. To unlink a node in constant time you must be able to reach both neighbours from the node itself; a singly linked node knows only its successor, so removing it would require walking from the front to find the predecessor — O(n), and the whole design collapses. The second pointer is the price of O(1) removal from the middle. The **sentinels** — a permanent dummy head and a permanent dummy tail that never hold data — exist so that no operation ever has to ask "am I at an end?". Insert-after-head and unlink-node become branch-free, and the empty cache is not a special case: head points to tail and tail points back to head. Most eviction bugs in hand-written caches are missing end-of-list branches that sentinels delete outright. ## The wrong answers this design replaces - **"Give each entry a last-used timestamp and evict the oldest."** Correct in outcome, wrong in cost: finding the minimum timestamp means scanning every entry, O(n) per eviction. The list *is* the timestamp — position encodes recency, and moving a node updates it in O(1). - **"Put the entries in a priority queue keyed on last-use time."** Better, but O(log n) per touch, and every hit needs a decrease-key on an arbitrary element, which needs its own index structure. You pay more to get less. - **"Sweep periodically and drop cold entries."** That is a batch job with unbounded latency spikes and no hard capacity guarantee; an LRU cache must be exactly bounded at all times. ## Costs to state honestly | Approach | Find | Mark recent | Evict LRU | |---|---|---|---| | Array or list scan with timestamps | O(n) | O(1) | O(n) | | Heap ordered by last use | O(1) with an index | O(log n) | O(log n) | | Hash map + doubly linked list | O(1) expected | O(1) | O(1) | The price is memory: every entry carries two extra pointers and a node object, and the key is reachable from both structures. For a cache of large payloads that overhead is noise; for a cache of tiny values it can be a meaningful fraction. And the honest bound on the whole cache is *expected* O(1), inherited from the map half — the list half is the only part that is O(1) in the worst case.
- Why can't you just keep a last-used timestamp on each entry and evict the oldest?Because finding the minimum timestamp means examining every entry — O(n) on each eviction, on the hot path of a full cache. The linked list stores the same information positionally: the order of nodes *is* the recency order, so the oldest is at a known end and moving an entry to "now" is a few pointer writes. No clock, no scan, no comparison.
- Is the get operation on this design O(1) in the worst case?No — it is O(1) *expected*. The list work is genuinely constant in the worst case, but the map lookup inherits hash-table behaviour: expected constant, degrading toward O(n) when many keys collide into one bucket. With a decent hash and a bounded load factor that is a theoretical corner, but claiming flat worst-case O(1) is the answer that gets challenged.
- Why does each list node store its own key when the map already has it?Because eviction runs in the opposite direction. You pick the victim from the list end, holding only a node, and you must then delete that entry from the map — which needs the key. Without a key on the node you would have to search the map for the entry pointing at that node, turning an O(1) eviction into an O(n) one.
A coat check: the ticket number finds your coat instantly, but the rail order tells the attendant which coat has hung there longest.
saying these in an interview costs you the question
- Says a hash map alone can evict the oldest entry
- Stores payloads in the map instead of node references
- Uses a singly linked list and claims O(1) removal
- Adds a timestamp per entry plus an eviction scan
- Claims worst-case O(1) rather than expected O(1)