LRU Cache
Combine a doubly-linked list (most recent at head, least recent at tail) with a hash map (key → node). On get: move node to head. On put: add to head, if over capacity, remove tail. All operations O(1).
How It Works
An LRU cache must do three things in O(1): look up a key, mark an entry as most recently used, and evict the least recently used when full. A hash map alone gives O(1) lookup but no usage ordering; a list alone gives ordering but O(n) lookup. The classic design combines them: a doubly linked list holds entries ordered from most recent (head) to least recent (tail), and a hash map maps each key to its list node. On get, jump to the node via the map and unlink-and-move it to the head. On put, insert at the head; if capacity is exceeded, remove the tail node and delete its key from the map.
Double links are essential — removing a node in O(1) requires knowing its predecessor without traversal. Sentinel head and tail nodes eliminate every edge case.
Step-by-Step Visualization
Code
class LRUCache {
private int cap;
private LinkedHashMap<Integer, Integer> map;
public LRUCache(int capacity) {
this.cap = capacity;
this.map = new LinkedHashMap<>(16, 0.75f, true);
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
if (map.size() > cap)
map.remove(map.keySet().iterator().next());
}
}Tips & Gotchas
Practice Problems
- 1LRU Cache
- 2LFU Cache
- 3Design Browser History
- 4Max Stack
About the Design Problems Pattern
Build more complex data structures on top of linked lists. These combine linked lists with hash maps for O(1) operations.
Most linked list problems are about pointer manipulation. Draw it out! Fast & slow pointers detect cycles and find midpoints. In-place reversal is the other core technique.
Common Linked List Interview Problems
- Reverse Linked List
- Merge Two Sorted Lists
- Linked List Cycle
- Remove Nth Node From End
- LRU Cache
- Reorder List
Frequently Asked Questions
Why not a singly linked list, since it is simpler?
The core operation is removing an arbitrary node found through the hash map, and unlinking requires updating the predecessor's next pointer. A singly linked list would need an O(n) walk to find that predecessor, destroying the O(1) guarantee; the prev pointer makes removal constant time.
How does LFU differ from LRU in structure?
LFU evicts by usage count, breaking ties by recency, so one recency list is not enough. The standard O(1) design keeps a hash map from frequency to its own doubly linked list of nodes, plus a running minimum frequency; a node moves to the next frequency's list on each access.
What details commonly break an LRU implementation?
Three classics: forgetting that put on an existing key must update its value and refresh its recency, evicting from the map without unlinking the list node (or vice versa), and mishandling capacity-one caches. Sentinel head and tail nodes prevent most null-pointer slips.