Why this matters: this problem's implementation act has a specific failure mode — pointer surgery narrated as "and then we just move it to the front" while the code quietly does five steps, one of them wrong. The fix is structural: isolate the list surgery in two small helpers, and every operation becomes a short story built from verified moves.
The node and the shell
class Node {
final K key; // eviction must know which map entry to kill
V value;
Node prev, next;
}
class LruCache {
final int capacity;
final Map<K, Node> index; // key -> NODE, the O(1) insight
final Node head, tail; // sentinels — never null, never data
long hits = 0, misses = 0, evictions = 0;
}Two decisions to narrate as you write. The map's value type is Node — say again that this is the pointer O(1) depends on. And head/tail are sentinels: permanent dummy nodes at both ends, so every real node always has a non-null neighbor on each side. Sentinels remove every if (node == head) special case from the surgery below — cheap insurance against exactly the bugs interviewers watch for.
Two helpers own all the pointer surgery
void unlink(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
void linkAtHead(Node n) { // head side = most recently used
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
}Every recency refresh is now unlink(n); linkAtHead(n); — two calls you verified once. This is the same move as the parking lot's fit rule: the delicate logic has exactly one home (single responsibility, applied to pointer arithmetic), so an off-by-one can only exist in one place.
get: the hot path
V get(K key) {
Node n = index.get(key);
if (n == null) { misses++; return null; } // null IS the miss signal
unlink(n);
linkAtHead(n); // a read is a use
hits++;
return n.value;
}Hash lookup, two pointer moves, a counter. Narrate the requirement each line honors: null-return is unambiguous because nulls can't be stored; the relink is "get refreshes standing" made real; the counter is the stats contract.
put: two paths, visibly
void put(K key, V value) {
Node existing = index.get(key);
if (existing != null) { // UPDATE path
existing.value = value;
unlink(existing);
linkAtHead(existing); // update counts as a use
return; // never evicts
}
if (index.size() == capacity) evictVictim(); // INSERT path, at capacity
Node n = new Node(key, value);
index.put(key, n);
linkAtHead(n);
}The early return is doing design work: the update path physically cannot reach the eviction code, which makes "updates never evict" a property of the control flow rather than a hope. Reviewers of your own code should be able to see the two paths from the shape alone.
Eviction: lockstep or bust
void evictVictim() {
Node victim = tail.prev; // least recently used
unlink(victim);
index.remove(victim.key); // node knew its key for this
evictions++;
}One flow, both structures. The invariant from lesson 02 — an entry is in the cache iff it's in both the map and the list — is enforced by never letting an operation touch one without the other. remove(key) is the same discipline in the other direction: look up the node, unlink it, remove the map entry.
Stats
CacheStats stats() {
return new CacheStats(hits, misses, evictions,
hits + misses == 0 ? 0.0 : (double) hits / (hits + misses));
}Trivial code, but it's the enforcement point for lesson 02's definitions: only get moves hits or misses; remove touches neither. If a future edit makes an update increment hits, this is where the contract visibly broke.
What you'd say about complexity
get, put, and remove are each one hash operation plus O(1) pointer moves — and the justification is the map-to-node pointer plus the sentinel-guarded list; without the former it's O(n) per refresh. Space is O(capacity) nodes plus the map. Offer the honest footnote unprompted: hash operations are O(1) expected, and each entry pays a constant overhead of two pointers and a stored key — that's the price of the ordering being maintained instead of recomputed.
Key takeaway
Sentinels kill the edge cases, two helpers own all pointer surgery, and every operation reads as its requirement: get refreshes standing and counts the hit, put's early-returning update path provably never evicts, and eviction removes from list and map in one flow so the lockstep invariant survives. O(1) each — justified by the map-to-node pointer, not asserted.