Part 1 · Concepts · Built for backends
LRU cache
A fixed-size cache that throws out the least recently used item when full. get and put are both O(1).
How it works
Two structures together: a hash map from key to node (O(1) lookup), and a doubly linked list ordered by use (O(1) move and remove). Dummy head and tail nodes remove edge cases. get: find the node, move it to the front. put: update or insert at the front. Over capacity: remove the node before the tail and delete its key from the map.
| get / put | O(1) |
| space | O(capacity) |
Reach for it when
- 'Design a cache', LRU or LFU questions
- Any time you need O(1) lookup plus O(1) ordering
Implementation (JavaScript, tested)
class LRUCache {
capacity;
map = new Map();
head = { key: 0, val: 0, prev: null, next: null }; // most recent side
tail = { key: 0, val: 0, prev: null, next: null }; // least recent side
constructor(capacity) {
this.capacity = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
unlink(n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
addFront(n) {
n.next = this.head.next;
n.prev = this.head;
this.head.next.prev = n;
this.head.next = n;
}
get(key) {
const n = this.map.get(key);
if (!n) return -1;
this.unlink(n);
this.addFront(n); // touched = most recent
return n.val;
}
put(key, val) {
const hit = this.map.get(key);
if (hit) {
hit.val = val;
this.unlink(hit);
this.addFront(hit);
return;
}
const n = { key, val, prev: null, next: null };
this.map.set(key, n);
this.addFront(n);
if (this.map.size > this.capacity) {
// evict least recently used
const lru = this.tail.prev;
this.unlink(lru);
this.map.delete(lru.key);
}
}
}Traps
- In JS, a Map keeps insertion order, so delete then set moves a key to the end. That's a valid shortcut, but say so and offer the linked-list version, which is what they're testing.
- Forgetting to delete the evicted key from the map.
- Node needs its key, so eviction knows what to delete from the map.
In real systems: Redis eviction policy allkeys-lru (Redis approximates it by sampling keys). CDN and browser caches. Database buffer pools use LRU variants.
Say out loud: A map gives O(1) lookup and a doubly linked list gives O(1) reordering. Together, both operations are O(1).