LRU cache
hardThe map finds a key in O(1) but has no order; the list keeps order in O(1) but cannot find anything. Store the list node as the map's value and every operation - including eviction - becomes constant time.
O(1) get and putSpace O(capacity)Saved in this browser - no sign-up, nothing sent anywhere.
How lru cache works
A cache of capacity k must evict something when a new key arrives beyond k, and least recently used is the policy: drop the entry untouched the longest. The catch is doing it in O(1). A hash map finds any key instantly but has no idea which entry is oldest; a doubly linked list keeps perfect recency order but cannot find anything.
The design stores the list node as the map's value. get hashes to the node, reads it, and moves it to the front of the list - most recently used. put inserts at the front, and on overflow evicts the tail, which is by construction the least recently used. No timestamps, no scanning: position in the list is the recency order.
The list must be doubly linked. Moving a node to the front means unlinking it from the middle, and eviction unlinks the tail - both need the predecessor in O(1), which only a prev pointer gives. This exact pairing ships built-in as Python's OrderedDict and Java's LinkedHashMap.
Step by step
- Take capacity 2, empty. put(1): a node for key 1 goes to the list's front, and the map stores key 1 pointing at it.
- put(2): key 2's node enters at the front. Recency now reads 2 then 1 - newest first.
- get(1): the map finds the node in O(1). Unlink it, relink at the front - recency flips to 1 then 2.
- put(3) on a full cache: the tail is key 2, the least recently used. Remove it from both the list and the map.
- Insert 3 at the front. Recency reads 3 then 1 - that earlier get is what saved key 1.
- get(2) now misses; get(1) still hits. Every step so far - hit, miss, move, evict - was constant time.
Complexity
| Worst case time | O(1) get and put |
|---|---|
| Space | O(capacity) |
Reference implementation
Python
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # evict the oldest
# Under the hood OrderedDict is exactly a hash map plus a
# doubly linked list - the classic interview answer built in.JavaScript
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // JS Map preserves insertion order
}
get(key) {
if (!this.map.has(key)) return -1;
const v = this.map.get(key);
this.map.delete(key);
this.map.set(key, v); // reinsert = move to the most-recent end
return v;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
this.map.set(key, value);
if (this.map.size > this.capacity) {
this.map.delete(this.map.keys().next().value); // evict oldest
}
}
}Worth noticing
Two structures, each covering the other's weakness
A hash map finds a key in O(1) but has no order. A doubly linked list maintains order in O(1) but cannot find anything. Store the list *node* as the map's value and you get both - which is the entire design.
Why the list has to be doubly linked
Eviction removes the tail, and moving a node to the front removes it from the middle. Unlinking a node in O(1) needs its predecessor, which only a prev pointer provides. Singly linked would make every touch O(n).
Every operation is O(1), including eviction
No scanning for the oldest entry, no timestamps to compare. Position in the list *is* the recency ordering, maintained incrementally as you go.
Common pitfalls
- Evicting from the wrong end: the front holds the most recently used, and removing there keeps hot data out - accidental MRU eviction.
- Forgetting to move a node on get: reads stop refreshing recency, and frequently read keys get evicted as if never touched.
- put on an existing key that evicts before checking existence - the cache ends up under capacity with a needlessly dropped entry.
- Removing the node from the list but not the map on eviction: the map grows forever and later hands back pointers to dead nodes.
- Rolling your own in production: Python's OrderedDict with move_to_end and popitem(last=False) is the same machinery, already correct.
Where it is used
- Page caches and database buffer pools, where LRU or a close approximation decides eviction.
- Redis and memcached both offer LRU-style eviction when memory fills.
- LeetCode 146 - one of the most frequently asked design interview questions.
- Image and asset caches in mobile apps, keeping recently viewed items warm.
Frequently asked questions
What is the time complexity of an LRU cache?
get and put are both O(1) worst case - a hash lookup plus a constant number of pointer writes, including eviction, because the victim is always sitting at the list's tail. Space is O(capacity): the map and the list each hold at most capacity entries.
Why does an LRU cache need both a hash map and a linked list?
Each covers the other's weakness. The map finds a key in O(1) but keeps no order; the list keeps recency order with O(1) reordering but cannot find anything. Storing the list node as the map's value gives you both properties at once.
Why must the linked list be doubly linked?
Every access moves a node out of the middle, and eviction removes the tail. Unlinking in O(1) requires the node's predecessor, which only a prev pointer provides - with a singly linked list, each of those operations would cost an O(n) walk instead.
Can I just use OrderedDict or LinkedHashMap instead of building one?
Yes - both are literally a hash map threaded onto a doubly linked list. Python's OrderedDict offers move_to_end and popitem(last=False); Java's LinkedHashMap has an access-order mode with removeEldestEntry. Interviews want the internals; production code should take the built-ins.