LRU Cache: O(1) Get and Put With a Hash Map + Doubly Linked List
Design an LRU cache with O(1) get and put using a hash map plus a doubly linked list — intuition, JavaScript code, a full walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
LRU Cache is the problem that separates people who know data structures from people who can combine them. No single structure solves it. A hash map gives you O(1) lookup but no notion of order. A linked list gives you O(1) reordering but no fast lookup. The trick — and the reason this shows up in real system design and in interviews at every level — is welding the two together so both operations stay O(1).
The prompt sounds like an implementation chore: build a fixed-capacity cache that evicts the least recently used entry when it fills up. But every design decision inside it is load-bearing. Get the structure right and both get and put run in constant time. Get it wrong and you're scanning a list on every access.
The problem
Design a data structure that supports two operations on a cache with a fixed capacity:
get(key)— return the value if the key exists, otherwise return-1. A successful get counts as using the key.put(key, value)— insert or update the key. If the cache is already at capacity, evict the least recently used key first.
Both operations must run in O(1) average time. "Recently used" means touched by either a get or a put.
LRUCache cache = new LRUCache(2); // capacity 2
cache.put(1, 1); // cache: {1=1}
cache.put(2, 2); // cache: {1=1, 2=2}
cache.get(1); // returns 1 // 1 is now most-recent → {2=2, 1=1}
cache.put(3, 3); // evicts key 2 // cache: {1=1, 3=3}
cache.get(2); // returns -1 // 2 was evicted
cache.put(4, 4); // evicts key 1 // cache: {3=3, 4=4}
cache.get(1); // returns -1
cache.get(3); // returns 3
cache.get(4); // returns 4Notice get(1) at line 4 saved key 1 from eviction — accessing it made it the freshest, so put(3,3) evicted key 2 instead. Recency is not insertion order; it updates on every touch.
The brute force baseline
The naive version stores entries in a plain array (or a single map) and tracks recency with timestamps. To evict, you scan for the oldest.
class SlowLRU {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // key -> { value, lastUsed }
this.clock = 0;
}
get(key) {
if (!this.map.has(key)) return -1;
const entry = this.map.get(key);
entry.lastUsed = this.clock++;
return entry.value;
}
put(key, value) {
if (this.map.size >= this.capacity && !this.map.has(key)) {
// scan every entry to find the least-recently-used one
let lruKey, oldest = Infinity;
for (const [k, v] of this.map) {
if (v.lastUsed < oldest) { oldest = v.lastUsed; lruKey = k; }
}
this.map.delete(lruKey);
}
this.map.set(key, { value, lastUsed: this.clock++ });
}
}get is O(1), but put on a full cache walks the entire map to find the oldest timestamp — that's O(n) per eviction, where n is the capacity. On a cache holding 10⁵ entries with a heavy write load, every insert triggers a 10⁵-element scan. The whole point of a cache is speed; an O(n) eviction defeats it.
The key insight: order is a linked list
The missing ingredient is a structure that remembers order and lets you move any element to the front in O(1). That's a doubly linked list. Splice a node out (node.prev.next = node.next; node.next.prev = node.prev) and splice it back in at the most-recent end — both are pointer rewires, no scanning.
But a linked list can't find a node by key in O(1). So pair it with a hash map that stores key → node pointer. Now the two structures divide the labor cleanly:
| Structure | Answers | Cost |
|---|---|---|
| Hash map | "Where is the node for this key?" | O(1) lookup |
| Doubly linked list | "What order were things used in?" | O(1) move / evict |
Every access is a two-step dance: the map jumps you straight to the node, then the list moves that node to the fresh end. The least-recently-used node is always sitting at the stale end, ready to evict without a search. One detail makes the code clean: sentinel head and tail nodes. They're dummy endpoints that never hold data, so every real node always has a non-null prev and next — no edge cases for empty lists or first/last insertions.
The optimal solution
This mirrors the algorithm in the LRU Cache visualizer: keep the LRU end next to head, the MRU end next to tail. remove and insert are tiny O(1) helpers; get and put compose them.
class Node {
constructor(key, val) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // key -> Node
this.head = new Node(-1, -1); // sentinel: LRU side
this.tail = new Node(-1, -1); // sentinel: MRU side
this.head.next = this.tail;
this.tail.prev = this.head;
}
remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
insert(node) { // insert right before tail (MRU)
node.prev = this.tail.prev;
node.next = this.tail;
this.tail.prev.next = node;
this.tail.prev = node;
}
get(key) {
if (!this.map.has(key)) return -1;
let node = this.map.get(key);
this.remove(node); // pull it out of its old spot
this.insert(node); // re-insert as most-recent
return node.val;
}
put(key, value) {
if (this.map.has(key)) {
this.remove(this.map.get(key)); // drop the stale node
}
let newNode = new Node(key, value);
this.insert(newNode);
this.map.set(key, newNode);
if (this.map.size > this.capacity) {
let lru = this.head.next; // stalest real node
this.remove(lru);
this.map.delete(lru.key); // key lives on the node — that's why
}
}
}Two things earn their place here. First, put re-uses insert/remove instead of re-implementing the pointer surgery — fewer places to get a rewire wrong. Second, each node stores its own key. During eviction you have the node (head.next), but you need to delete from the map, which is keyed by key. Without node.key you'd have no way to find the map entry to remove.
Walkthrough
Tracing the example from the top, capacity = 2. The list is written LRU-end → MRU-end (left is stalest, right is freshest).
| Operation | Map keys | List (LRU → MRU) | Returns / Evicts |
|---|---|---|---|
LRUCache(2) | {} | (empty) | — |
put(1, 1) | {1} | [1] | — |
put(2, 2) | {1, 2} | [1, 2] | — |
get(1) | {1, 2} | [2, 1] | returns 1 |
put(3, 3) | {1, 3} | [1, 3] | evicts key 2 |
get(2) | {1, 3} | [1, 3] | returns -1 |
put(4, 4) | {3, 4} | [3, 4] | evicts key 1 |
get(1) | {3, 4} | [3, 4] | returns -1 |
get(3) | {3, 4} | [4, 3] | returns 3 |
get(4) | {3, 4} | [3, 4] | returns 4 |
Follow get(1) on row 4: key 1 was at the LRU end after put(2,2), but touching it moved it to the MRU end, so the list flipped to [2, 1]. That's why the next put(3,3) evicted key 2, not key 1 — key 2 had become the stalest. Later, get(2) returns -1 because that key is already gone, and the list stays untouched since nothing was accessed. Every row is a constant number of pointer moves plus one map operation.
Complexity
| Metric | Cost | Why |
|---|---|---|
get time | O(1) | one map lookup + two pointer rewires |
put time | O(1) | one map op + fixed-size insert, plus O(1) eviction |
| Space | O(capacity) | at most capacity nodes in the list and map |
Both operations do a bounded amount of work regardless of how many items the cache holds — no loops over the data. The space is proportional to the capacity, not the number of operations, because eviction keeps the cache from ever exceeding its limit.
Common mistakes
- Using a singly linked list. To splice a node out in O(1) you need its
prevpointer. A singly linked list forces an O(n) walk to find the predecessor, collapsing back to brute force. - Not storing the key inside the node. During eviction you hold
head.nextand must callmap.delete(...). Withoutnode.keyyou can't identify the map entry — a classic bug that only surfaces on the first eviction. - Skipping sentinel nodes. Without dummy head/tail, inserting into an empty list, removing the only node, or touching the ends all need null checks. Sentinels make
prev/nextalways valid and delete every edge case. - Forgetting that
getcounts as a use. A read must move the node to the MRU end. Ifgetonly returns the value without reordering, recency drifts out of sync and you evict the wrong key. - Checking capacity before insert. Insert first, then evict if
size > capacity. Evicting before inserting mishandles the case where the incoming key already exists (an update, not a new entry).
Where this pattern shows up next
The doubly-linked-list-plus-pointer-surgery skill here is the foundation for the rest of the linked list track:
- Reverse Linked List — the pure pointer-rewiring drill that makes the
remove/insertmoves feel automatic. - Middle of the Linked List — fast/slow traversal, the other core linked list technique.
- Linked List Cycle — detecting a loop with two pointers, no extra memory.
- Linked List Cycle II — extending cycle detection to locate where the loop begins.
You can also step through the LRU Cache visualizer to watch the map and the doubly linked list update together on every get, put, and eviction.
FAQ
Why do you need both a hash map and a linked list for an LRU cache?
Neither structure alone can do both jobs in O(1). A hash map finds a value by key instantly but has no concept of access order, so it can't tell you which entry is least recently used. A doubly linked list maintains order and lets you move or remove any node in O(1), but it can't locate a node by key without an O(n) scan. Combining them — the map stores key → node, the list stores recency order — lets each operation borrow the other's strength, keeping both get and put at O(1).
Why sentinel head and tail nodes instead of null endpoints?
Sentinels are dummy nodes that bookend the list and never hold real data. They guarantee that every genuine node always has a non-null prev and next, which erases a whole category of edge cases: inserting into an empty list, removing the last remaining node, or updating the first/last element. Without them, insert and remove would each need branching null checks. With them, the pointer rewires are the same four lines every time, which is both faster to write and much harder to get wrong.
What is the time complexity of get and put in an LRU cache?
Both are O(1) average time. get performs a single hash-map lookup and, on a hit, two constant-time pointer rewires to move the node to the most-recently-used end. put does one map operation and a fixed-size list insert, plus an O(1) eviction (remove head.next, delete its key) when the cache overflows. There are no loops over the stored elements, so the cost never grows with the number of cached items. Space is O(capacity).
Why does a get operation change the state of the cache?
Because "least recently used" counts reads as usage. A successful get means the caller just touched that key, so it becomes the most recently used entry and must move to the fresh end of the list. If get returned the value without reordering, the recency information would be wrong, and the next eviction could throw out an entry you just accessed. This is the detail that trips people up: in an LRU cache, reading has a side effect on order.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.