Design an LRU Cache

Intermediate · 20 min read · Low-Level Design, Case Studies: Core

HashMap + doubly linked list, generic and thread-safe.

"Design an LRU cache" is half data-structures question, half LLD question. The data-structure half: O(1) get and put with a hash map plus a doubly linked list. The LLD half: generics, a pluggable eviction policy, TTL, and thread safety — the follow-ups that distinguish senior answers.

What the interviewer expects

The full design in this lesson is longer than anything you'd write in one round. It's there so you understand the edge cases and can answer follow-up questions. In the round itself, aim for this:

1. Requirements

2. Core idea

Sentinel head and tail nodes remove null checks at the ends.

3. Implementation (single-threaded)

4. Making eviction pluggable

An LLD interviewer will ask: "What if we want LFU or FIFO?" Separate storage from the eviction policy:

5. TTL (expiry)

Store an expiry time with each entry and treat expired entries as misses:

6. Thread safety

The map and the linked list must change together atomically — a ConcurrentHashMap alone is not enough, because get also mutates the list (moves the node to the head).

7. Patterns used

Interview questions

  • Why do you need both a hash map and a doubly linked list?
  • Why isn't a ConcurrentHashMap enough to make the LRU cache thread-safe?
  • How would you implement LFU in O(1)?

Further reading

Key takeaways

  • LRU = hash map (lookup) + doubly linked list (recency), both O(1); sentinels simplify edge cases.
  • LinkedHashMap with access order is the built-in shortcut.
  • Make eviction a strategy so LFU/FIFO plug in; add TTL with an injected Clock.
  • Thread safety needs atomic map-plus-list updates: one lock, segments, or buffered access recording.

Previous: Design Tic-Tac-Toe · Next: Design a Logging Framework