LRU Cache Design

Question 1

Why use a Doubly Linked List instead of Singly Linked List?

Accepted Answer

Because it allows O(1) removal without traversing to find the predecessor — To remove a node in O(1), we need to update its previous node pointer. Doubly linked list gives us O(1) access to both neighbors.

Question 2

What does LRU stand for as a cache eviction policy?

Accepted Answer

Least Recently Used — LRU evicts the Least Recently Used item when the cache is full, assuming recently used items are likely to be used again (temporal locality).

Question 3

Which data-structure combination gives O(1) get AND put for an LRU cache?

Accepted Answer

A hash map combined with a doubly linked list — The hash map gives O(1) key→node lookup; the doubly linked list gives O(1) move-to-front and O(1) eviction of the tail — together O(1) for both operations.

Question 4

In a doubly linked list used for LRU, why is the prev pointer specifically necessary?

Accepted Answer

It enables O(1) splicing without traversing to find the predecessor node — When a node must be unlinked from its current position, you need to update its predecessor's next pointer. A singly linked list requires O(n) traversal from head to find that predecessor. The prev pointer gives direct access to the predecessor, making splice O(1).

Question 5

On a cache HIT (get of an existing key), the LRU cache must…

Accepted Answer

Move the accessed node to the head of the list — Accessing an item makes it most-recently-used, so it is moved to the head (MRU end) to protect it from eviction.

Question 6

When the cache is FULL and a new key is inserted, the LRU policy evicts the node at the…

Accepted Answer

Tail of the list, where the oldest-accessed entry currently resides — The least-recently-used item sits at the tail; it is removed (and its key deleted from the map) to make room.

Question 7

What does the hash map store in an LRU cache?

Accepted Answer

A mapping from key to a linked list node pointer — Mapping keys to list nodes lets you find and splice any node in O(1); the node itself holds the key and value.

Question 8

Java's LinkedHashMap can implement an LRU cache by…

Accepted Answer

Using access-order mode and overriding removeEldestEntry — LinkedHashMap with accessOrder=true reorders on access; overriding removeEldestEntry to bound size yields an LRU cache with little code.

Question 9

Sentinel (dummy) head and tail nodes are used in the LRU list to…

Accepted Answer

To eliminate null checks at both ends of the list — Dummy head/tail mean every real node always has non-null neighbors, simplifying splice logic and removing edge cases.

Question 10

How does LFU (Least Frequently Used) differ from LRU?

Accepted Answer

LFU evicts by least frequency; LRU evicts by least recency — LRU tracks recency (time of last use); LFU tracks how often items are used and evicts the least frequent — better for skewed access but more complex (needs frequency buckets).

LRU Cache Design

Who does which job?

Test your knowledge

Why use a Doubly Linked List instead of Singly Linked List?

Write the code

LRU Cache

Example Cases

The short version

In more depth

HashMap + Doubly Linked List

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?