LRU Cache
Design a least recently used cache with O(1) get and put, using a hash map over a doubly linked list.
Problem Understanding
LRU Cache: design a cache with a fixed capacity.
get(key)returns the value forkey, or-1if it is not cached.put(key, value)inserts or updates the key. If that pushes the cache over capacity, evict the least recently used key.
Both operations must run in O(1) average time. A get counts as a use.
Attempt 1: A List With Timestamps
Keep entries in a list with a last-used timestamp and scan for the oldest when evicting. Lookups and evictions are O(n). The two things that need to be fast, finding a key and finding the least recent entry, need two different structures.
The Intuition: Map for Lookup, List for Order
Keep entries in a doubly linked list in recency order: the most recently used right after a head sentinel, the least recently used right before a tail sentinel. Keep a hash map from key to node.
get: find the node through the map, unlink it and reinsert it at the front.put: unlink any old node for the key, insert the new node at the front, and if the size is over capacity, unlink the node beforetailand delete its key from the map.
Unlinking and inserting a node you already hold are O(1) with prev and next pointers, and the sentinels mean there are no empty-list special cases.
Interactive Walkthrough
CAPACITY 2
EMPTY CACHE
⇄
MOST RECENT ← → LEAST RECENT
Operation
—
Size
0/2
map keys
Empty
get returns
No gets yet
An empty cache with capacity 2: head and tail sentinels linked to each other, and an empty map
Next
put(1, 1): add a node at the front and point the map at it
Operations
capacity
Legend & Complexity
The node this operation touches
The node being evicted
Front = most recently used; back = least
get / put
O(1)
Space
O(capacity)
The list runs from head (most recent) to tail (least recent). Each operation fills the node it touches; a get moves its node to the front, and when a put overflows the capacity, the node that falls off the tail end is shown in red.
Dry Run Table
Capacity 2
| Operation | List (most → least recent) | Returns |
|---|---|---|
| put(1, 1) | 1 | |
| put(2, 2) | 2, 1 | |
| get(1) | 1, 2 | 1 |
| put(3, 3) | 3, 1 (evict 2) | |
| get(2) | 3, 1 | -1 |
| put(4, 4) | 4, 3 (evict 1) | |
| get(1) | 4, 3 | -1 |
| get(3) | 3, 4 | 3 |
| get(4) | 4, 3 | 4 |
The Solution Template
A hash map of nodes over a doubly linked list with sentinels. The JavaScript and TypeScript versions use Map, whose insertion order serves as the recency list.
LRU Cache Code
1class LRUCache {2 constructor(capacity) {3 this.cap = capacity;4 this.map = new Map();5 }67 get(key) {8 if (!this.map.has(key)) return -1;9 const val = this.map.get(key);10 this.map.delete(key);11 this.map.set(key, val);12 return val;13 }1415 put(key, value) {16 if (this.map.has(key)) this.map.delete(key);17 this.map.set(key, value);18 if (this.map.size > this.cap) {19 this.map.delete(this.map.keys().next().value);20 }21 }22}
Edge Cases & Common Mistakes
- Updating an existing key: remove the old node first, or the list holds two nodes for one key and evicts the wrong thing.
- Forgetting that get is a use: a
getmust move the node to the front, or a frequently read key gets evicted. - Not deleting the evicted key from the map: the map then points at a node that is no longer in the list.
- Capacity 1: every new key evicts the previous one; the sentinels make this need no special case.
- Storing the key in the node: needed so eviction knows which map entry to delete.
Summary
An LRU cache is a hash map for O(1) lookup plus a doubly linked list for O(1) recency updates: move a node to the front on every use, insert at the front on put, and evict from the back. Sentinel head and tail nodes keep the list code free of edge cases.
More practice: DSA interview questions with answers · patterns cheat sheet