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.

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.