--- title: "LRU Cache (LeetCode #146)" description: "O(1) get and put — a hash map and a doubly linked list working as one" source: https://vizlearn.app/algorithms/leetcode/lru-cache access: premium (interactive player requires Lifetime; this doc is free) --- # LRU Cache (LeetCode #146) An LRU cache keeps recently used key-value pairs close while discarding the one left untouched longest. The hard part is not deciding *which* key is least recent; it is maintaining both fast lookup and a reliable recency order after every `get` and `put`, without scanning the cache. Imagine a rail of index cards on a desk. The card nearest the left end was used most recently; the card at the right end has gone untouched longest. Moving a card to the front is cheap if you already have it in your hand, but finding a card by key would require walking the whole rail. Production systems use the same recency idea in Python's `functools.lru_cache`, Redis's approximate `allkeys-lru` policy, and LRU-style page replacement in operating systems. ## How LRU cache works ### Why one data structure is not enough A hash map solves the finding problem. It maps each key directly to that key's node on the rail. The rail itself is a doubly linked list, so a known node can be detached and reattached at the front with a fixed number of pointer writes. Each structure covers the other's weakness: - The hash map answers "where is key `k`?" in expected O(1) time, but it does not track recency. - The doubly linked list answers "which key is newest or oldest?" and moves a known node in O(1) time, but it cannot find an arbitrary key quickly. The two views describe the same set of live entries. If a node is in the list, its key must be in the map. If a key is in the map, the mapped node must be in the list. ### The recency list The list runs from most recently used (MRU) to least recently used (LRU). Two dummy nodes, `HEAD` and `TAIL`, sit outside the real data: `HEAD ↔ MRU ↔ ... ↔ LRU ↔ TAIL` These sentinels remove awkward empty-list and one-node branches. Inserting at the front always happens between `HEAD` and `HEAD.next`. Eviction always removes `TAIL.prev`. No real entry needs to be treated as a special endpoint. There are only two pointer operations to understand. To detach a node, make its neighbors point to each other. If `node.prev` is `before` and `node.next` is `after`, write `before.next = after` and `after.prev = before`. To add a node at the front, place it between `HEAD` and the current first node (`TAIL` when the cache is empty). Update the node's two links, then update `HEAD.next` and that first node's `prev` link. The animation separates those writes deliberately. A node can be temporarily detached while the map still points to it, or linked into the list just before the map receives its new entry. Those are short-lived implementation states, not finished cache states. ## LRU cache step by step ### What get does `get(key)` begins with the map. If the key is missing, return `-1`. Nothing in the recency list moves. A failed lookup is not a use of any cached entry. If the key exists, the map gives us the node immediately. Save its value, detach the node, add it after `HEAD`, and return the saved value. Even a read changes the cache: the returned key becomes MRU. If the node is already MRU, the implementation can skip the pointer writes. The important invariant is the same either way: after a successful `get`, that key is at the front. ### What put does `put(key, value)` has two paths. When the key already exists, update the existing node's value and move that same node to the front. Do not allocate a second node, and do not increase the cache size. When the key is new, create one node, add it to the front, and add `key → node` to the map. If the map now holds more than `capacity` entries, select `TAIL.prev`, detach that LRU node, and delete its key from the map. Evicting from only one structure leaves a broken cache. Removing the list node but keeping the map entry creates a stale lookup. Deleting only the map entry leaves an unreachable node occupying capacity. The two removals form one logical eviction. ### Walk through the default trace The default capacity is 3. Start with these operations: `put(1, 10), put(2, 20), put(3, 30), get(1), put(4, 40)` After the first three puts, the recency list is `3, 2, 1`. Key 3 is MRU because it was inserted last; key 1 is LRU. `get(1)` returns `10` and moves key 1 to the front. The list becomes `1, 3, 2`. The cache contains the same three keys, but that read changes which card will be removed next. `put(4, 40)` inserts key 4 at the front, producing `4, 1, 3, 2`. The size is now 4, one above capacity. `TAIL.prev` identifies key 2 as LRU, so key 2 is detached and removed from the map. The finished list is `4, 1, 3`. Without the successful `get(1)` touch, key 1 would still be LRU and the final put would evict it instead. A read is part of the replacement policy, not a passive observation. ## Time and space complexity Let `capacity` be the maximum number of live entries. | Operation | Expected time | Why | |---|---:|---| | `get` | O(1) | One hash lookup and a fixed number of pointer writes | | `put` existing key | O(1) | One hash lookup, one value update, and one move | | `put` new key | O(1) | One insertion and, at most, one tail eviction | | Space | O(capacity) | One map entry and one list node per live key | The time bounds use the standard expected O(1) hash-map model. The linked-list work itself is worst-case O(1) because it never walks by position. ## Edge cases - With capacity 1, every new key after the first replaces the only resident key. The sentinels keep this path identical to larger capacities. - A missing `get` returns `-1` and leaves the order unchanged. - Updating an existing key overwrites its value, moves the same node to MRU, and keeps the size stable. - Getting the current MRU returns its value without changing the visible order. - Updating an existing key must reuse its current node; allocating a duplicate can leave the map pointing at one node while another copy still occupies the list. ## Common mistakes The most common bug is treating `get` as read-only. The returned key must become MRU. Another is evicting the front of the list. With this lesson's order, the front is MRU and the back is LRU; eviction must use `TAIL.prev`. Pointer-update order also matters. Save a node's neighbors before rewiring them, and keep the map and list synchronized by the end of every public operation. Dummy sentinels make the code shorter, but they do not replace the core invariant: the map finds the node, and the list ranks exactly the same live nodes by recency.