Hash map + doubly linked list (LRU)

43 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A cache is a small shelf for things you fetched recently, so the next fetch is instant. The shelf has room for 2 items. When it is full and something new arrives, throw out the item that was used longest ago: the Least Recently Used one. Watch it: put(1), put(2), get(1), put(3). Before put(3) the shelf holds 1 and 2, and 1 was used more recently (the get), so 2 is thrown out. Now get(2) fails.

By hand you might keep the items in a row ordered by last use and, on every get, find the item, pull it out and move it to the front; on every put when full, drop the last one. Finding the item in a row is a scan: O(n) for a shelf of n. Moving it to the front in an array shifts everything: also O(n). A cache that does O(n) work per lookup defeats its own purpose when n is thousands.

We need two things fast: find any item by its key, and move any item to the front. No single simple structure does both; two together do.

Build the structure, one piece at a time

Piece 1: a doubly linked list for order. A chain of boxes where each box has an arrow to the next and to the previous. The front is the most recently used, the back is the least. In a doubly linked chain, a box can be unhooked from wherever it is in constant time (point its neighbours at each other) and hooked in at the front in constant time. With dummy boxes at both ends, no edge cases.

Piece 2: a hash map for lookup. map[key] = the box holding that key. Finding a box is one lookup.

Piece 3: the operations. get(key): if the key is not in the map, return −1; otherwise unhook its box and hook it at the front, return its value. put(key, value): if the key exists, update the value and move the box to the front; else create a box at the front and add it to the map; if the shelf is now over capacity, unhook the back box and delete its key from the map.

Why it is correct

The invariant: the map and the list contain exactly the same set of keys; the list is ordered by last use, front most recent; the list has at most capacity boxes.

Every use (get or put of an existing key) moves that box to the front, so after any operation the touched key is the most recent and the relative order of the others is unchanged; by induction the list is in order of last use. Every insertion adds to both map and list, every eviction removes from both, so the two agree. Eviction happens exactly when the size would exceed capacity and removes the back box, which by the ordering is the least recently used. So the cache keeps precisely the capacity most recently used keys.

keys(map) = keys(list), |list| ≤ capacity, and list is sorted by time of last use

The doubly linked list is essential: a singly linked box cannot be unhooked in constant time because its previous box is unknown.

Why it is fast

A get is one map lookup plus one unhook and one hook: a constant number of pointer changes. A put is at most one lookup, one creation, one hook, one unhook and two map updates.

get = O(1), put = O(1), memory = O(capacity)

Compared with scanning and shifting a row, which is O(n) per operation, this is the difference between a cache that helps and one that hurts.

How to recognise it in an interview

The cues are "LRU", "least recently used", "O(1) get and put", "move to front", "most recently used queue", or any design where items must be found by key and also kept in an order that changes on access. Say: "A hash map for O(1) lookup and a doubly linked list for O(1) reordering; each map entry points at its list box, and the back of the list is evicted."

LRU Cache is the example above. LFU Cache keeps one such list per frequency count and a map from frequency to list, evicting from the lowest non-empty frequency. Design Browser History is the list alone, with a current pointer that moves back and forward.

02The idea in one line

A map for O(1) lookup, a list for O(1) recency moves; evict from the tail.

Reach for it when: LRU/LFU caches, 'move to front', most recently used queues.

Cost: O(1) per op.

03The walk-through, step by step

The video works one example: LRU capacity 2: put 1, put 2, get 1, put 3, get 2. These are its captions in order, so you can follow without the video or check a step you missed.

1. A map finds a node in O(1); the list keeps recency order in O(1)
2. put(1,1): insert at the front, map[1] = node
3. put(2,2): insert at the front, map[2] = node
4. get(1) = 1: found via the map, move it to the front
5. put(3,3): full, evict the tail key 2
6. put(3,3): insert at the front, map[3] = node
7. get(2) = −1: not in the map
8. put(4,4): full, evict the tail key 1
9. put(4,4): insert at the front, map[4] = node
10. get(1) = −1: not in the map
11. get(3) = 3: found via the map, move it to the front
12. Every op touches one node and one map entry: O(1)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Design: Hash map + array for O(1) random, Time-versioned map, Lazy iterators, Ordered intervals (range module), Streaming data structures.