Appearance
4.9.9 — LRU Cache
LeetCode 146 · Medium · ★ Blind 75
The problem
Design a cache with a fixed capacity supporting two operations, both in O(1):
get(key)— return the value, or −1 if absent. This counts as using the key.put(key, value)— insert or update. If the cache is over capacity, evict the least recently used key.
LRUCache(2)
put(1,1); put(2,2)
get(1) → 1 (1 is now the most recently used)
put(3,3) (over capacity → evict 2, the least recently used)
get(2) → -1The pattern
Two requirements pull in different directions:
- Find a key instantly. That is a hash map.
- Know which key was used longest ago, and move keys to the front instantly. A hash map cannot do this — it has no order.
Neither structure alone works, so use both, and let each cover the other's weakness.
- A hash map from key to node, giving O(1) lookup.
- A doubly linked list holding the nodes in use order, most recent at the front.
The map finds the node; the list knows the order. This combination is the answer, and being able to say why in one sentence is the whole point of the problem.
Why the list must be doubly linked
To move a node to the front you must first unlink it from where it is, and to unlink a node you need the node before it.
In a singly linked list, finding the previous node costs O(n) — you would have to walk from the head. A prev pointer makes it O(1). That is the entire justification, and it is the reason doubly linked lists exist at all.
Why two dummy nodes
Insertion at the front and removal at the back both have edge cases: an empty list, a single element, the node being at the boundary. Every one of them disappears if you put permanent sentinel nodes at both ends.
head ⇄ [most recent] ⇄ … ⇄ [least recent] ⇄ tail
↑ ↑
dummy, never holds data dummy, never holds dataNow every real node has a real neighbour on both sides, so unlinking is always the same two lines with no branches. This is the dummy-head idea from 4.9.2, applied at both ends.
The solution
python
class Node:
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {} # key → Node
self.head = Node() # dummy: most recent side
self.tail = Node() # dummy: least recent side
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._remove(node) # it was just used…
self._add_front(node) # …so it moves to the front
return node.val
def put(self, key: int, value: int) -> None:
if key in self.map:
self._remove(self.map[key]) # drop the old node entirely
node = Node(key, value)
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap:
lru = self.tail.prev # the node just before the tail dummy
self._remove(lru)
del self.map[lru.key] # ← this is why nodes store their keyts
class LNode {
key = 0; val = 0;
prev: LNode | null = null;
next: LNode | null = null;
constructor(key = 0, val = 0) { this.key = key; this.val = val; }
}
class LRUCache {
private cap: number;
private map = new Map<number, LNode>();
private head = new LNode();
private tail = new LNode();
constructor(capacity: number) {
this.cap = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
private remove(node: LNode) {
node.prev!.next = node.next;
node.next!.prev = node.prev;
}
private addFront(node: LNode) {
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
}
get(key: number): number {
const node = this.map.get(key);
if (!node) return -1;
this.remove(node);
this.addFront(node);
return node.val;
}
put(key: number, value: number): void {
const existing = this.map.get(key);
if (existing) this.remove(existing);
const node = new LNode(key, value);
this.map.set(key, node);
this.addFront(node);
if (this.map.size > this.cap) {
const lru = this.tail.prev!;
this.remove(lru);
this.map.delete(lru.key);
}
}
}The node stores its key as well as its value, and that is not redundant. When evicting, you find the node from the list — but you must also delete its entry from the map, and for that you need the key. Without it you would have to search the map for the node, which is O(n) and destroys the whole design. This is the detail most people miss.
get must reorder. A read counts as a use. Forgetting this makes it a least-recently-inserted cache, which passes some tests and fails the ones that matter.
On put of an existing key, the old node is removed and a fresh one inserted at the front. Updating the value in place and moving the node would work equally well and allocates less.
Complexity
O(1) for both operations. Every step is a map lookup or a fixed number of pointer assignments.
O(capacity) space.
The shortcut, and why to know both
Python has OrderedDict, which is a hash map that remembers insertion order and can move a key to either end in O(1):
python
from collections import OrderedDict
class LRUCache(OrderedDict):
def __init__(self, capacity):
self.cap = capacity
def get(self, key):
if key not in self: return -1
self.move_to_end(key)
return self[key]
def put(self, key, value):
if key in self: self.move_to_end(key)
self[key] = value
if len(self) > self.cap:
self.popitem(last=False)JavaScript's Map also preserves insertion order, so map.keys().next().value gives the oldest key and re-inserting moves a key to the end.
Both are correct and both are how you would write it in production. In an interview, write the manual version — the question is testing whether you can build the structure, and OrderedDict is a hash map with a doubly linked list inside it, doing exactly what you would have done. Say that, then offer the shortcut.
Where this goes next
- LFU Cache (LeetCode 460) — evict the least frequently used instead. Now you need a map from frequency to a list of keys at that frequency, plus a running minimum frequency. Considerably harder, and it is the natural follow-up.
- Real caches — Redis, your CPU's cache, a database buffer pool, and your browser's HTTP cache all face this decision. Most do not use true LRU, because maintaining it costs memory and locking; they approximate it with clock or second-chance algorithms. Chapter 10.14 covers eviction policies properly, and Chapter 2.5 covers the operating system's page replacement.
The rule: when one structure cannot give you both fast lookup and useful ordering, combine two and keep them in step. That combination is the recurring idea; the list is not special.
What the interviewer will push on
"Why a doubly linked list?" Unlinking a node needs its predecessor, and only a prev pointer gives that in O(1).
"Why does the node store its key?" To delete the map entry when evicting.
"Does get change the order?" Yes — a read is a use.
"How would you make it thread-safe?" The map and the list must stay consistent, so both updates go inside one lock. A per-structure lock lets another thread see a node in the map that has already left the list. Chapter 2.4.
"How is a real cache different?" True LRU costs a pointer update on every read, which is expensive under contention. Production caches approximate it. Saying this shows you know the difference between an exercise and a system.
One thing to volunteer: state the design in one sentence before writing anything. "A hash map for O(1) lookup, and a doubly linked list for O(1) reordering, with the map pointing at list nodes." Then build it.
Next: 4.9.10 Merge K Sorted Lists — the merge from 4.9.2 scaled up, and the first appearance of a heap.