LRU Cache — Doubly Linked List + HashMap from Scratch
Sanjeev SharmaAdvertisement
Problem Statement
LeetCode 146 — LRU Cache Difficulty: Hard | Pattern: Doubly Linked List + HashMap
Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement the LRUCache class:
LRUCache(capacity): Initialize the cache with positive sizecapacity.get(key): Return the value ofkeyif it exists, otherwise return-1. Getting a key makes it the most recently used.put(key, value): Update the value ofkeyif it exists. Otherwise insert the key-value pair. If the number of keys exceedscapacity, evict the least recently used key.
Both get and put must run in O(1) average time.
Constraints:
1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^5- At most
2 * 10^5calls will be made togetandput.
Example:
Input:
LRUCache(2)
put(1, 1) -> cache: {1:1}
put(2, 2) -> cache: {1:1, 2:2}
get(1) -> returns 1. cache order: 2 is LRU, 1 is MRU
put(3, 3) -> evict key 2. cache: {1:1, 3:3}
get(2) -> returns -1 (not found)
put(4, 4) -> evict key 1. cache: {4:4, 3:3}
get(1) -> returns -1
get(3) -> returns 3
get(4) -> returns 4Why This Problem Matters
The LRU Cache is the most well-known hard design problem in technical interviews. Amazon, Microsoft, Google, and Facebook consider it a benchmark question — if you cannot implement it correctly, it signals a gap in data structure fundamentals. If you can implement it cleanly from scratch (without Python's OrderedDict), it signals strong engineering instincts.
LRU caches are used everywhere in production systems: CPU caches, browser caches, database buffer pools, CDN edge caches, and Redis cache eviction. Understanding the data structure behind O(1) LRU behavior is essential for anyone working on performance-sensitive systems.
The challenge is achieving O(1) for both get and put. A HashMap alone gives O(1) lookup but O(n) LRU identification. A doubly linked list alone gives O(1) addition/removal but O(n) lookup. The combination of both — with O(1) HashMap lookup pointing to O(1) DLL manipulation — is the elegant solution.
Interviewers specifically watch whether you:
- Know to use sentinel (dummy) nodes to avoid edge cases
- Implement
_removeand_add_to_tailas reusable helpers - Remember that
getmust also update recency (the most common bug) - Handle the eviction correctly: evict LRU before adding, or after?
The Core Insight
The two data structures work together:
HashMap: key -> DLL node. O(1) lookup of any node given its key.
Doubly Linked List: Maintains order of use. The tail is the Most Recently Used (MRU) and the head.next is the Least Recently Used (LRU). Insertion at tail and removal from head are both O(1) with doubly linked list.
Sentinel nodes (dummy head and tail): Always present, never holding real data. Their purpose is to ensure every real node always has non-null prev and next pointers, eliminating all special cases for head insertion and tail removal.
Four operations, all O(1):
_remove(node): Unlink from wherever it sits (useprevandnextpointers)._add_to_tail(node): Link before the sentinel tail.get(key): HashMap lookup,_remove+_add_to_tail(mark as recently used), return value.put(key, val): If key exists, remove old node. Create new node,_add_to_tail. If over capacity, removehead.next(LRU) and delete from HashMap.
Visual Dry Run
Initial state (capacity = 2):
[HEAD] <-> [TAIL]
HashMap: {}put(1, 1):
[HEAD] <-> [1:1] <-> [TAIL]
HashMap: {1: node(1)}put(2, 2):
[HEAD] <-> [1:1] <-> [2:2] <-> [TAIL]
HashMap: {1: node(1), 2: node(2)}get(1) — returns 1, moves node(1) to tail:
[HEAD] <-> [2:2] <-> [1:1] <-> [TAIL]
HashMap: {1: node(1), 2: node(2)}put(3, 3) — capacity exceeded, evict LRU = head.next = node(2):
Remove node(2), delete from HashMap
Add node(3) to tail:
[HEAD] <-> [1:1] <-> [3:3] <-> [TAIL]
HashMap: {1: node(1), 3: node(3)}Solution (Optimal)
class DLLNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> DLLNode
# Sentinel nodes — always present, never hold real data
self.head = DLLNode() # LRU end
self.tail = DLLNode() # MRU end
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: DLLNode) -> None:
"""Unlink a node from the doubly linked list."""
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_tail(self, node: DLLNode) -> None:
"""Insert a node just before the sentinel tail (most recently used)."""
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
# Mark as most recently used
self._remove(node)
self._add_to_tail(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = DLLNode(key, value)
self._add_to_tail(node)
self.cache[key] = node
if len(self.cache) > self.capacity:
# Evict the LRU node (head.next)
lru = self.head.next
self._remove(lru)
del self.cache[lru.key]class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // key -> node
// Sentinel nodes
this.head = { key: 0, val: 0, prev: null, next: null };
this.tail = { key: 0, val: 0, prev: null, next: null };
this.head.next = this.tail;
this.tail.prev = this.head;
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_addToTail(node) {
node.prev = this.tail.prev;
node.next = this.tail;
this.tail.prev.next = node;
this.tail.prev = node;
}
get(key) {
if (!this.cache.has(key)) return -1;
const node = this.cache.get(key);
this._remove(node);
this._addToTail(node);
return node.val;
}
put(key, value) {
if (this.cache.has(key)) {
this._remove(this.cache.get(key));
}
const node = { key, val: value, prev: null, next: null };
this._addToTail(node);
this.cache.set(key, node);
if (this.cache.size > this.capacity) {
const lru = this.head.next;
this._remove(lru);
this.cache.delete(lru.key);
}
}
}Complexity:
| Operation | Time | Space |
|---|---|---|
| get | O(1) | — |
| put | O(1) | — |
| Overall space | — | O(capacity) |
Common Mistakes
- Forgetting that
getupdates recency:getmust call_remove+_add_to_tailto mark the node as most recently used. Treatinggetas a passive read is the most common LRU bug. - Not storing the key in the DLL node: When evicting the LRU node (head.next), you need to delete it from the HashMap using its key. If the node does not store its key, you cannot do this in O(1).
- Wrong order of assignments in
_add_to_tail: The four pointer assignments must happen in the correct order. Assignnode.prevandnode.nextbefore updatingtail.prev.nextandtail.prev. - Evicting after adding (wrong order): In
put, check capacity AFTER adding the new node. If you evict first, you might remove the node you just added if the key existed. - Using a non-doubly-linked list: A singly linked list cannot do O(1) removal of an arbitrary node (you need the predecessor). The doubly linked list with sentinel nodes is required.
Interview Tips
- Name the sentinel pattern immediately: "I'll use sentinel head and tail nodes so every real node always has non-null prev and next — no edge case handling needed."
- Write helpers first: Implement
_removeand_add_to_tailas clean 4-line helpers before writinggetandput. This shows architectural thinking. - Draw the DLL: Show the initial state (head <-> tail) and the first few operations visually.
- Call out the get-updates-recency rule explicitly: "The most common bug is treating get as read-only. In an LRU cache, any access — including get — makes that key the most recently used."
- Discuss production variants: Python's
OrderedDict.move_to_end, Java'sLinkedHashMap, and Redis's LRU approximation.
Follow-up Questions
- LFU Cache (LeetCode 460): Least Frequently Used instead of Least Recently Used — requires frequency-indexed buckets.
- LRU Cache with TTL (Time-To-Live): Add expiration timestamps to each node. Use a priority queue for TTL-based eviction.
- Thread-safe LRU Cache: Add a read-write lock. Discuss the tradeoff between lock granularity and performance.
- Distributed LRU Cache: Consistent hashing to shard keys across nodes, with local LRU at each node.
- How does Redis implement LRU? Redis uses an approximation: sample a few random keys and evict the oldest among them — much simpler than a full DLL-based LRU.
Key Takeaways
- LRU Cache = HashMap (O(1) lookup) + Doubly Linked List (O(1) order maintenance). Neither alone achieves O(1) for both operations.
- Sentinel head and tail eliminate all null-check edge cases in
_removeand_add_to_tail. - The DLL node must store its key to enable O(1) HashMap deletion during eviction.
getis not passive — it must move the accessed node to the MRU end of the list.- Evict (
head.next) AFTER inserting the new node input, not before. - This problem is the gold standard for "design a data structure" interviews — knowing it cold, including all edge cases, is a must for any serious interview preparation.
Advertisement
