Example

Suppose we have an LRU cache with capacity = 3, and we perform the following operations:

Final cache state: {3:C, 1:A, 4:D} (in order of usage from least to most recent)

In this chapter, we will explore the low level design of a LRU cache.

Lets start by clarifying the requirements:

Before starting the design, it's important to ask thoughtful questions to uncover hidden assumptions, clarify ambiguities, and define the system's scope more precisely.

Here is an example of how a discussion between the candidate and the interviewer might unfold:

After gathering the details, we can summarize the key system requirements.

Now that we understand what we're building, let's identify the building blocks of our system.

Unlike systems that model real-world concepts (such as users, products, or bookings), the design of an LRU Cache is centered around choosing the right data structures and internal abstractions to achieve the required functionality and performance.

The core challenge here is twofold:

Let's walk through our requirements and identify what needs to exist in our system.

The Need for Fast Lookup

"Both  get and  put operations must run in O(1) time"

To efficiently retrieve values by key, we need a data structure that supports constant-time key access.

The natural choice is a HashMap. It provides O(1) average-case lookup and update. When someone calls get("user_123"), we need to find that entry immediately, not scan through a list.

But here's the problem: a HashMap doesn't maintain any order. It can't tell us which entry was accessed least recently. If we only used a HashMap, we'd have to scan all entries to find the LRU item during eviction, making that operation O(n).

The Need for Fast Ordering

"If the cache exceeds its capacity, automatically evict the least recently used item"

The second challenge is maintaining the recency order of cache entries so we can:

An array won't work because inserting or moving elements from the middle involves shifting, which is O(n). A regular linked list won't work either because finding a specific node to move requires O(n) traversal.

The key insight is using a Doubly Linked List. Each node maintains references to both its prev and next nodes, allowing us to:

But how do we get a direct reference to a node without traversing the list? That's where the HashMap comes back into play.

Combining Both Structures

The magic of achieving O(1) for both get and put lies in combining a HashMap and a Doubly Linked List:

This combination gives us the best of both worlds:

Additional Core Entities

Beyond the HashMap and Doubly Linked List, we need two more classes to encapsulate and organize our logic:

Why store the key in the Node?

When we evict from the tail, we need to remove the entry from the HashMap too. The HashMap needs the key to remove an entry, so each Node must remember its key.

Entity Overview

Here's how these entities relate to each other:

These entities form the core abstractions of our LRU Cache. They enable the system to maintain a fixed-size cache, support constant-time access and updates, and evict the least recently used entry when necessary.

With our entities identified, let's define their attributes, behaviors, and relationships.

Now that we know what entities we need, let's flesh out their details. For each class, we'll define what data it holds (attributes) and what it can do (methods). Then we'll look at how these classes connect to each other.

We'll work bottom-up: simple types first, then the classes with real logic. This order makes sense because complex classes depend on simpler ones.

Node<K, V>

The Node class represents an individual entry in the cache and serves as a node in the doubly linked list.

The Node class is intentionally simple. It's a data container with minimal behavior. The prev and next pointers are mutable because the node's position in the list changes as items are accessed.

DoublyLinkedList<K, V>

A utility class that manages the MRU (Most Recently Used) to LRU (Least Recently Used) ordering of cache entries.

LRUCache<K, V>

The main class that provides the public API (get and put) and manages the overall cache logic.

Key Design Principles:

Before looking at the complete implementation, try building the LRU Cache yourself. Below you'll find template stubs for all the classes we designed. Each stub includes method signatures and // TODO comments where you need to add the implementation logic.

Your task: Implement all the // TODO sections based on the design we discussed. Once complete, run the demo to verify your implementation produces the expected output.

Once you've implemented all the classes and verified the output matches, compare your solution with the complete implementation in the next section.

Now let's translate our design into working code. We'll build bottom-up: the Node class first, then the DoublyLinkedList, and finally the LRUCache that ties everything together.

Inside a multi-threaded server, many request threads share one LRUCache instance and call get and put concurrently. The cache holds two pieces of state that must stay in sync: the map from keys to nodes, and the list ordering those nodes from most to least recently used. It is correct only when the map and the list agree.

The implementation wraps both get and put in a single lock, so only one thread runs either method at a time. The two concerns below show why that lock is needed, and why even get cannot run lock-free.

Concern 1: Concurrent Operations Corrupting the Linked List (High Risk)

The list's prev and next pointers only make sense as a group. addFirst, remove, and moveToFront each rewrite three or four of them in sequence. If two threads run those sequences at once, their half-finished updates interleave and the list points at nodes that have already moved.

Setup

The cache holds {a, b, c} ordered head <-> c <-> b <-> a <-> tail. Thread 1 calls get("a"), running moveToFront(nodeA). Thread 2 calls put("d", 4) at capacity, running removeLast() to evict nodeA, the LRU node just before the tail. Both touch nodeA and its neighbors.

Without synchronization

Result

The list and the map disagree. nodeA is still reachable through the list but its key was deleted from the map, so a later removeLast() can return a node whose key is not in the map. map.remove(lru.key) then deletes nothing while the list grows past capacity, leaking entries and returning stale values.

With synchronization

One lock around the whole get and the whole put makes each operation atomic. Thread 1 finishes its entire moveToFront before Thread 2 acquires the lock, so Thread 2 reads a consistent tail.prev, evicts the real LRU node, and removes the matching key. The list and the map move together, one operation at a time.

The lock must cover the map and the list together. Locking only one leaves the same window open, since the corruption comes from the two structures being updated out of step.

Concern 2: A Single Global Lock Becomes the Bottleneck (Medium Risk)

The single lock that fixes Concern 1 is correct, but it serializes every operation. Under heavy load, every get and put across all keys queues behind one lock, turning the cache into a contention point. This is a scaling problem, not a correctness one.

Setup

Sixteen worker threads run reads and writes spread across thousands of unrelated keys. The work on each key is independent, but all of it shares one lock.

Without striping (single lock)

Thread 1 works on "user_1" and Thread 2 on "user_9999", keys that never touch the same node, yet Thread 2 still blocks until Thread 1 releases the lock. Throughput is capped at one operation at a time no matter how many cores are available.

Result

Correct values, but poor scaling. Latency climbs as threads queue on the lock, and adding cores does not help because the critical section is global.

With striped locking

Partition the cache into N independent shards, each with its own map, list, and lock. A key is routed to a shard by its hash, for example shard = hash(key) % N. Operations on keys in different shards run in parallel because they take different locks, and each shard runs the same single-lock logic from Concern 1. The trade-off is that eviction is now per-shard rather than global: each shard evicts its own LRU entry, which approximates global LRU closely enough for most workloads. Production caches like Java's ConcurrentHashMap and Guava's Cache use this approach internally.

These two concerns follow the usual path for shared-state design: first make it correct with a lock that covers the whole operation, including the read path, then trade strict global ordering for throughput by partitioning the lock. Correctness comes from Concern 1; striping is the optimization added once a single lock becomes the bottleneck.

The base cache does one job: keep the most recently used entries and evict the rest. Real caching layers usually need more, such as expiring stale data, capping by memory instead of count, reporting how well the cache performs, and staying consistent with a backing store. Each extension below adds a focused capability without rewriting the core get and put logic.

Scenario: "Cached values should expire after a fixed time, even if they are still being accessed."

LRU evicts based on recency, but some data goes stale on a clock rather than on usage. A session token or a price quote might be valid for only 60 seconds. The fix is to stamp each node with an expiry time and treat an expired entry as a miss. The cleanest place to enforce this is inside get: if the looked-up node is past its expiry, remove it and return null as if it were never there.

Expiry on access (lazy expiration) is cheap but leaves dead entries in the cache until someone looks them up. For aggressive memory reclamation, a background sweeper thread can periodically scan and drop expired nodes, at the cost of an extra thread contending for the same lock.

Scenario: "Cap the cache by total memory, not by a fixed number of entries."

Counting entries assumes every value is the same size. When the cache holds objects of wildly different sizes (a 2 KB thumbnail next to a 5 MB image), a count limit either wastes memory or under-uses it. The fix is to give each node a weight and track the running total. Eviction then keeps calling removeLast until the total weight fits under the limit, which can remove several small entries or a single large one.

The one edge case to handle is a single entry whose weight exceeds maxWeight on its own. The loop above would evict everything else and still be over budget. A production cache either rejects such entries or caps weight at the limit, so the cache never tries to store something it can never fit.

Scenario: "Report how often the cache actually helps."

A cache is only worth its memory if it serves enough requests from memory to justify itself. The hit ratio (hits divided by total lookups) is the single most useful number for tuning capacity. The fix is to increment two counters inside get: a hit when the key is present and live, a miss when it is absent or expired. Exposing a small stats snapshot lets a dashboard or log line track the ratio over time.

Because the counters are updated inside the same locked section as the lookup, they stay accurate under concurrency without a separate lock. A low hit ratio is a signal to either raise the capacity, reconsider what is being cached, or accept that the access pattern does not favor caching at all.