LRU Cache
Medium HashMap + doubly linked list
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Design a fixed-capacity cache with get and put in O(1). When full, put evicts the least recently used key.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: a cache that evicts the least recently used key, with O(1) get and put.
Why this works: the HashMap finds nodes; the doubly linked list keeps usage order (most recent at the front) and removes any node in O(1).
Example: capacity 2: put 1, put 2, get 1, put 3
order after get 1: [1, 2]put 3 evicts the tail 2 → [3, 1]
✦Hints open one at a time
↗Approach
map: key → node. get: if present, move the node to the front and return its value. put: update and move to front, or insert a new node at the front; if over capacity, remove the node before the tail sentinel and delete its key from the map.
</>Solution (Java)
import java.util.*;
class LRUCache {
private static class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0), tail = new Node(0, 0); // sentinels
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node n = map.get(key);
if (n == null) return -1;
unlink(n);
addFront(n); // now the most recently used
return n.val;
}
public void put(int key, int value) {
Node n = map.get(key);
if (n != null) {
n.val = value;
unlink(n);
addFront(n);
return;
}
if (map.size() == capacity) {
Node lru = tail.prev; // least recently used
unlink(lru);
map.remove(lru.key);
}
n = new Node(key, value);
addFront(n);
map.put(key, n);
}
private void unlink(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void addFront(Node n) {
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
}
}!Common mistake
Forgetting to remove the evicted key from the HashMap, so the map keeps growing and returns stale nodes.
- Time: O(1) per operation.
- Space: O(capacity).