Design an LRU cache with O(1) get and put. Say exactly which pointer updates each operation performs, then explain what breaks if the doubly linked list is replaced by a singly linked one.

Design an LRU cache with O(1) get and put. Say exactly which pointer updates each operation performs, then explain what breaks if the doubly linked list is replaced by a singly linked one.

Approach: Combine a hash map from key to node with an intrusive list ordered by recency, and check that every step touches only a constant number of nodes.

A hash map from key to list node plus a doubly linked list with the most recent entry at the head. get looks the key up in the hash map, unlinks the node by setting node.prev.next = node.next and node.next.prev = node.prev, then relinks it at the head, which is a constant number of pointer writes, so get runs in constant time. put on a hit does the same and overwrites the value. put on a miss inserts at the head and, once the size exceeds the capacity, evicts the tail node and erases its key from the map, which is why each node must store its own key. Sentinel head and tail nodes remove every null check. A singly linked list cannot unlink an arbitrary node in O(1), since reaching its predecessor means walking the list, so get degrades to O(n). Storing predecessor pointers in the map is a doubly linked list with extra bookkeeping and it breaks on eviction, when the predecessor of the removed tail must also be updated.

Follow-up: How does an approximate policy such as CLOCK or a sampled LRU compare when the cache is shared across threads?

Key concepts: hash map, doubly linked list, eviction, constant time.