The real-world analogy: the physical desk stack
Imagine working at a physical office desk. You have a stack of paper folders (representing cache records):
- MRU (Most Recently Used): Whenever you retrieve a folder to read or update its content, you place it directly on top of the pile.
- LRU (Least Recently Used): Folders you haven't touched for days slowly sink to the very bottom of the pile.
- Eviction: Your desk only has space to pile 10 folders. If you fetch an 11th folder, you look at the folder sitting at the very bottom of the stack, slide it out, and throw it in the archive bin (evict it) to keep the stack at exactly 10.
If we represent this stack in software, we need a way to pull any folder out of the middle in O(1) time and move it to the top. A singly linked list would require walking from the top down to find the pointer behind the folder—taking O(N) operations. By attaching string loops to the front and back of each folder (forming a Doubly Linked List), we can instantly unlink any item from its neighbors and splice it onto the top in O(1) time.
The ask
A fixed-capacity cache with O(1) get(key) and put(key, value); when full, evict the least-recently-used entry.
The insight
You need two things in O(1): lookup by key and "move this to most-recent" / "find the least-recent". No single structure gives both, so combine:
- a hash map
key → nodefor O(1) lookup, and - a doubly linked list in recency order (head = most recent, tail = least), so moving a node or evicting the tail is O(1).
See it run
Step through the canonical trace below. Watch how get promotes a key to the front, and how a put into a full cache evicts the tail (the least-recently-used key).
size 0/2 · left = most recent, right = first to be evicted
1/15Empty cache, capacity 2. The map (top) finds any key in O(1). The list (bottom) keeps everything in recency order — most-recently-used on the left, least-recently-used on the right.
Think it through like the interview
Don't memorize the structure — derive it. The derivation is reusable; the memorized answer dies on the first follow-up.
PROBLEMBuild a fixed-capacity cache with O(1) get(key) and put(key, value). When full, evict the least-recently-used entry.
- 1
Turn 'LRU' into operations
“Forget data structures. What operations must be O(1), stated precisely?”
- 2
Audit the candidates
“Which single structure gives all three in O(1)? Try each and find its failure.”
unlocks after the stage above - 3
Combine: each covers the other's weakness
“Map gives lookup but no order; doubly linked list gives O(1) reorder but no lookup. How do I wire them together?”
unlocks after the stage above - 4
Kill the edge cases structurally
“Empty list, single element, removing the head… how do I avoid a forest of null checks?”
unlocks after the stage above - 5
Trace it, then take the follow-ups
“capacity=2: put(1), put(2), get(1), put(3). Who got evicted — and what breaks under threads?”
unlocks after the stage above
Implementation
Below are complete implementations with sentinel nodes and thread-safe locks.
Python
import threading
from typing import Dict
class Node:
def __init__(self, key: int = 0, val: int = 0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.map: Dict[int, Node] = {}
self.head = Node() # Sentinel MRU
self.tail = Node() # Sentinel LRU
self.head.next = self.tail
self.tail.prev = self.head
self.lock = threading.Lock()
def _remove(self, node: Node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node: 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:
with self.lock:
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_front(node)
return node.val
def put(self, key: int, value: int) -> None:
with self.lock:
if key in self.map:
node = self.map[key]
node.val = value
self._remove(node)
self._add_front(node)
return
if len(self.map) == self.capacity:
lru_node = self.tail.prev
self._remove(lru_node)
del self.map[lru_node.key]
new_node = Node(key, value)
self._add_front(new_node)
self.map[key] = new_node
Java
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
class Node {
int key;
int val;
Node prev;
Node next;
Node() {}
Node(int k, int v) { this.key = k; this.val = v; }
}
public class LRUCache {
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(); // Sentinel MRU
private final Node tail = new Node(); // Sentinel LRU
private final ReentrantLock lock = new ReentrantLock();
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addFront(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
public int get(int key) {
lock.lock();
try {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
remove(node);
addFront(node);
return node.val;
} finally {
lock.unlock();
}
}
public void put(int key, int value) {
lock.lock();
try {
if (map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
remove(node);
addFront(node);
return;
}
if (map.size() == capacity) {
Node lruNode = tail.prev;
remove(lruNode);
map.remove(lruNode.key);
}
Node newNode = new Node(key, value);
addFront(newNode);
map.put(key, newNode);
} finally {
lock.unlock();
}
}
}
C++
#include <unordered_map>
#include <mutex>
#include <memory>
#include <cmath>
struct Node {
int key;
int val;
Node* prev = nullptr;
Node* next = nullptr;
Node(int k = 0, int v = 0) : key(k), val(v) {}
};
class LRUCache {
private:
int capacity;
std::unordered_map<int, Node*> map;
Node* head;
Node* tail;
std::mutex mtx;
void remove(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addFront(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
public:
LRUCache(int cap) : capacity(cap) {
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
~LRUCache() {
Node* curr = head;
while (curr) {
Node* next = curr->next;
delete curr;
curr = next;
}
}
int get(int key) {
std::lock_guard<std::mutex> lock(mtx);
auto it = map.find(key);
if (it == map.end()) return -1;
Node* node = it->second;
remove(node);
addFront(node);
return node->val;
}
void put(int key, int value) {
std::lock_guard<std::mutex> lock(mtx);
auto it = map.find(key);
if (it != map.end()) {
Node* node = it->second;
node->val = value;
remove(node);
addFront(node);
return;
}
if (map.size() == capacity) {
Node* lruNode = tail->prev;
remove(lruNode);
map.erase(lruNode->key);
delete lruNode;
}
Node* newNode = new Node(key, value);
addFront(newNode);
map[key] = newNode;
}
};
TypeScript
class Node {
constructor(
public key: number,
public val: number,
public prev: Node | null = null,
public next: Node | null = null,
) {}
}
class LRUCache {
private map = new Map<number, Node>();
private head = new Node(0, 0); // sentinel MRU side
private tail = new Node(0, 0); // sentinel LRU side
constructor(private capacity: number) {
this.head.next = this.tail;
this.tail.prev = this.head;
}
private remove(n: Node) {
n.prev!.next = n.next;
n.next!.prev = n.prev;
}
private addFront(n: Node) {
n.next = this.head.next;
n.prev = this.head;
this.head.next!.prev = n;
this.head.next = n;
}
get(key: number): number {
const n = this.map.get(key);
if (!n) return -1;
this.remove(n);
this.addFront(n); // mark most-recently-used
return n.val;
}
put(key: number, val: number): void {
const existing = this.map.get(key);
if (existing) { existing.val = val; this.remove(existing); this.addFront(existing); return; }
if (this.map.size === this.capacity) {
const lru = this.tail.prev!; // evict least-recently-used
this.remove(lru);
this.map.delete(lru.key);
}
const n = new Node(key, val);
this.addFront(n);
this.map.set(key, n);
}
}
The dummy head/tail nodes mean remove/addFront never check for null neighbors — no special-casing the empty list or single element. Mention this; it shows you write clean pointer code.
Interactive Quiz
1.
2.
3.
Complexity & follow-ups
- Time: O(1) for both
getandput. Space: O(capacity). - Thread-safety: wrap operations in a lock, or use a concurrent structure; note the lock is the contention point at scale (shard the cache to reduce it).
- TTL: store an expiry per node and treat expired as a miss (lazy) + a sweeper.
- LFU instead of LRU: evict least-frequently-used — needs frequency buckets; more complex, better for skewed access.
Practice — level up
The whole skill here is pairing a hash map with a second structure to make every operation O(1). Climb this ladder and that move becomes automatic — every rung is the same idea under a new disguise.
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up — build the two halves
Implement each structure alone before you combine them.- Design HashMapEasy
Buckets + chaining — the lookup half of the cache.
- Design Linked ListMedium
Pointer splicing with a sentinel — the recency half.
Core — the cache itself
Map → node, move-to-front, evict the tail.- LRU CacheMedium
The canonical map + doubly linked list in O(1).
Same trick: map (key → index) paired with an array.
Stretch — harder eviction policies
Say out loud which structure each new requirement forces.- LFU CacheHard
Add frequency buckets — a map of maps, evict the least-frequent.
Buckets of equal-count keys in a linked list — increment/decrement in O(1).