Design an LRU Cache (Low-Level Design)

A cache keeps a bounded number of recently useful entries so that repeated lookups avoid slow work. When it is full, an eviction policy decides which entry to drop. LRU (least recently used) drops the entry that has gone unused the longest. This article treats the cache as an object design problem: which types exist, which parts vary, and how the pieces fit together in Java.

The classic data structure walkthrough, with a focus on getting get and put to O(1), is in LRU cache interview in Java. This article is different in scope. It designs a small family: a Cache interface, a hand-written LRU implementation, a policy interface that makes eviction pluggable, and a thread-safe wrapper. For the system-level view of where caches sit and why policies differ, see cache eviction policies. The framework used here is described in the LLD interview framework.

Every example is a complete program that prints its results. They use only the standard library and need Java 21.

Requirements

Functional

put(key, value) stores an entry. If the cache is full, one entry is evicted first.
get(key) returns the value if present and marks the entry as recently used.
Capacity is fixed at construction and must be at least 1.
The cache is generic over key and value types. Keys and values are never null.
The eviction policy can be swapped (LRU, FIFO, or another) without changing callers.

Non-functional

get and put are O(1) for the LRU implementation.
A thread-safe variant must be available without slowing the single-threaded one.

Out of scope for now: time-based expiry (see design a key-value store with TTL), persistence, and distribution.

Entities and class diagram

The nouns are the cache, an entry, a capacity, and a policy. Two things vary: the eviction rule and whether access is shared between threads. Everything else is fixed.

classDiagram
    class Cache~K,V~ {
        <<interface>>
        +get(key) Optional~V~
        +put(key, value) PutOutcome
    }
    class LruCache~K,V~ {
        -map: Map~K,Node~
        -head: Node
        -tail: Node
    }
    class PolicyCache~K,V~ {
        -map: Map~K,V~
        -policy: EvictionPolicy
    }
    class EvictionPolicy~K~ {
        <<interface>>
        +onInsert(key)
        +onAccess(key)
        +onRemove(key)
        +victim() Optional~K~
    }
    class SharedCache~K,V~ {
        -delegate: Cache
    }
    Cache <|.. LruCache : implements
    Cache <|.. PolicyCache : implements
    Cache <|.. SharedCache : implements
    PolicyCache o-- EvictionPolicy : uses
    EvictionPolicy <|.. FifoPolicy
    EvictionPolicy <|.. LruPolicy
    SharedCache o-- Cache : wraps

Two implementations of Cache appear on purpose. LruCache is the specialised one with its own linked list. PolicyCache is the flexible one that receives the policy through its constructor. The trade-off is discussed under design decisions.

API

The interface is the public contract. Callers depend on it, so the implementation can change. This block is a fragment of the full program below, so the checker skips it.

Java

sealed interface PutOutcome<K, V> {
    record Inserted<K, V>() implements PutOutcome<K, V> {}
    record Replaced<K, V>(V old) implements PutOutcome<K, V> {}
    record Evicted<K, V>(K key, V value) implements PutOutcome<K, V> {}
}

interface Cache<K, V> {
    Optional<V> get(K key);   // counts as a use
    Optional<V> peek(K key);  // does not change recency
    PutOutcome<K, V> put(K key, V value);
    int size();
    int capacity();
}

The types encode decisions from the requirements. The constructor of each implementation throws IllegalArgumentException for a capacity below 1, so a zero-size cache never exists (encapsulation and invariants). The exception fits because the caller passed an argument that breaks a documented precondition. get returns Optional because a miss is a normal result, and Optional is used for return values only. PutOutcome is a sealed interface because the set of results is closed. A switch over it needs no default, and returning the evicted pair lets the caller write it back or log it.

Design decisions

Why a map plus a linked list. A HashMap finds an entry in O(1) but keeps no order. A list keeps recency order and moves a node to the front in O(1) if you hold a reference to it, but finding it costs O(n). Combining them gives O(1) for everything: the map stores, for each key, the list node that holds the entry.

Why nodes with object references. Each node has prev and next fields that refer to neighbouring nodes. The map values refer to the same node objects, so one node is reachable from the map and from the list. Moving a node changes four references and allocates nothing. Two sentinel nodes (head and tail, which hold no entry) remove the special cases for an empty list and for the first and last element: every real node always has a neighbour on both sides. The general topic of object graphs and cycles is in object graphs and references. The cycle between neighbouring nodes is not a leak in Java, because the garbage collector reclaims a node once nothing reachable refers to it.

Eviction unlinks the tail. When the cache is full, the node before the tail sentinel is the least recently used. The code unlinks it, removes its key from the map, and inserts a fresh node at the front. The size never exceeds capacity, and the evicted node becomes garbage.

The library version. LinkedHashMap can be created in access order (new LinkedHashMap<>(16, 0.75f, true)), where every get and every put of an existing key moves the entry to the end of its iteration order. Its first entry is then the least recently used one. Subclassing it and overriding removeEldestEntry is the usual short LRU cache. The hand-written version is shown because the design question is how the two structures cooperate, and because LinkedHashMap has no peek that leaves recency unchanged.

Strategy for eviction, but only where it varies. LRU is the required policy, so LruCache hard-codes it. PolicyCache takes an EvictionPolicy through its constructor (constructor injection, runtime dispatch through the interface). The trade-off: PolicyCache keeps two structures, a map of values and the policy's own bookkeeping, and calls the policy on every operation. LruCache has one structure and no extra calls. Use the specialised type when LRU is all that is needed and the policy interface when the policy is a real requirement.

Thread safety as a wrapper. Putting a lock inside LruCache would tax single-threaded users. A separate SharedCache that wraps any Cache keeps the core simple. Because get mutates recency, a reader-writer lock gives no benefit, so one lock for every operation is the right tool. See thread-safe components.

Full implementation: the LRU cache

This is the specialised O(1) implementation. The types from the API section are repeated so that the example runs on its own. Node is a private static nested class: it is an implementation detail and callers never see it.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;

public class Main {
    sealed interface PutOutcome<K, V> {
        record Inserted<K, V>() implements PutOutcome<K, V> {}
        record Replaced<K, V>(V old) implements PutOutcome<K, V> {}
        record Evicted<K, V>(K key, V value) implements PutOutcome<K, V> {}
    }

    interface Cache<K, V> {
        Optional<V> get(K key);
        Optional<V> peek(K key);
        PutOutcome<K, V> put(K key, V value);
        int size();
        int capacity();
    }

    static final class LruCache<K, V> implements Cache<K, V> {
        private static final class Node<K, V> {
            final K key;
            V value;
            Node<K, V> prev;
            Node<K, V> next;

            Node(K key, V value) {
                this.key = key;
                this.value = value;
            }
        }

        private final Map<K, Node<K, V>> map = new HashMap<>();
        private final Node<K, V> head = new Node<>(null, null); // sentinel: next is the most recently used
        private final Node<K, V> tail = new Node<>(null, null); // sentinel: prev is the least recently used
        private final int capacity;

        LruCache(int capacity) {
            if (capacity < 1) {
                throw new IllegalArgumentException("capacity must be at least 1");
            }
            this.capacity = capacity;
            head.next = tail;
            tail.prev = head;
        }

        private void unlink(Node<K, V> node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void pushFront(Node<K, V> node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void touch(Node<K, V> node) {
            unlink(node);
            pushFront(node);
        }

        /** Keys from most to least recently used, for debugging and tests. */
        List<K> keysByRecency() {
            var keys = new ArrayList<K>(map.size());
            for (var n = head.next; n != tail; n = n.next) {
                keys.add(n.key);
            }
            return keys;
        }

        @Override
        public Optional<V> get(K key) {
            var node = map.get(key);
            if (node == null) {
                return Optional.empty();
            }
            touch(node);
            return Optional.of(node.value);
        }

        @Override
        public Optional<V> peek(K key) {
            var node = map.get(key);
            return node == null ? Optional.empty() : Optional.of(node.value);
        }

        @Override
        public PutOutcome<K, V> put(K key, V value) {
            Objects.requireNonNull(key, "key");
            Objects.requireNonNull(value, "value");
            var existing = map.get(key);
            if (existing != null) {
                var old = existing.value;
                existing.value = value;
                touch(existing);
                return new PutOutcome.Replaced<>(old);
            }
            PutOutcome<K, V> outcome = new PutOutcome.Inserted<>();
            if (map.size() == capacity) {
                // Full: drop the least recently used entry before inserting.
                var victim = tail.prev;
                unlink(victim);
                map.remove(victim.key);
                outcome = new PutOutcome.Evicted<>(victim.key, victim.value);
            }
            var fresh = new Node<>(key, value);
            map.put(key, fresh);
            pushFront(fresh);
            return outcome;
        }

        @Override
        public int size() {
            return map.size();
        }

        @Override
        public int capacity() {
            return capacity;
        }
    }

    /** Code written against the interface works with any implementation. */
    static void warm(Cache<String, Integer> cache, List<String> names) {
        for (int i = 0; i < names.size(); i++) {
            cache.put(names.get(i), i);
        }
    }

    public static void main(String[] args) {
        try {
            new LruCache<String, Integer>(0);
        } catch (IllegalArgumentException e) {
            System.out.println("rejected: " + e.getMessage());
        }

        var cache = new LruCache<String, Integer>(3);
        warm(cache, List.of("a", "b", "c"));
        System.out.println("order: " + cache.keysByRecency());

        System.out.println("get a: " + cache.get("a"));
        System.out.println("order: " + cache.keysByRecency());

        // Inserting "d" evicts the least recently used entry, which is "b".
        var outcome = cache.put("d", 99);
        System.out.println("put d: " + outcome);
        System.out.println("order: " + cache.keysByRecency());

        System.out.println("peek c: " + cache.peek("c"));

        System.out.println("replace: " + cache.put("a", 7));
        System.out.println("get b: " + cache.get("b"));
        System.out.println("size " + cache.size() + " of capacity " + cache.capacity());

        String text = switch (outcome) {
            case PutOutcome.Inserted<String, Integer> i -> "stored";
            case PutOutcome.Replaced<String, Integer> r -> "replaced " + r.old();
            case PutOutcome.Evicted<String, Integer> e -> "evicted " + e.key();
        };
        System.out.println(text);
    }
}

Output

rejected: capacity must be at least 1
order: [c, b, a]
get a: Optional[0]
order: [a, c, b]
put d: Evicted[key=b, value=1]
order: [d, a, c]
peek c: Optional[2]
replace: Replaced[old=0]
get b: Optional.empty
size 3 of capacity 3
evicted b

The output shows the invariants. After get a, a moves to the front. d displaces b, the tail. peek reads without reordering, and replacing an existing key returns the old value and refreshes recency. Every operation touches a constant number of nodes and one hash lookup, so both get and put are O(1). The final switch has no default branch: the sealed interface lets the compiler check that every outcome is handled.

Pluggable eviction policy

PolicyCache separates storage from which entry to drop. The cache owns a HashMap<K, V> and tells the policy about every event. When the cache is full, it asks the policy for a victim. The policy owns only bookkeeping, never values.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Optional;
import java.util.Set;

public class Main {
    interface EvictionPolicy<K> {
        void onInsert(K key);
        void onAccess(K key);
        void onRemove(K key);
        Optional<K> victim();
    }

    /** First in, first out: reads do not matter. */
    static final class FifoPolicy<K> implements EvictionPolicy<K> {
        private final Deque<K> queue = new ArrayDeque<>();

        @Override public void onInsert(K key) { queue.addLast(key); }
        @Override public void onAccess(K key) { }
        @Override public void onRemove(K key) { queue.remove(key); }
        @Override public Optional<K> victim() { return Optional.ofNullable(queue.peekFirst()); }
    }

    /** Least recently used: a LinkedHashSet keeps keys in order of last use. */
    static final class LruPolicy<K> implements EvictionPolicy<K> {
        private final LinkedHashSet<K> order = new LinkedHashSet<>();

        private void touch(K key) {
            order.remove(key);
            order.add(key); // re-added keys go to the end
        }

        @Override public void onInsert(K key) { touch(key); }
        @Override public void onAccess(K key) { touch(key); }
        @Override public void onRemove(K key) { order.remove(key); }
        @Override public Optional<K> victim() {
            return order.isEmpty() ? Optional.empty() : Optional.of(order.getFirst());
        }
    }

    static final class PolicyCache<K, V> {
        private final Map<K, V> map = new HashMap<>();
        private final EvictionPolicy<K> policy;
        private final int capacity;

        PolicyCache(int capacity, EvictionPolicy<K> policy) {
            if (capacity < 1) {
                throw new IllegalArgumentException("capacity must be at least 1");
            }
            this.capacity = capacity;
            this.policy = policy;
        }

        Optional<V> get(K key) {
            var value = map.get(key);
            if (value == null) {
                return Optional.empty();
            }
            policy.onAccess(key);
            return Optional.of(value);
        }

        /** Returns the evicted key, if any. */
        Optional<K> put(K key, V value) {
            if (map.containsKey(key)) {
                map.put(key, value);
                policy.onAccess(key);
                return Optional.empty();
            }
            Optional<K> evicted = Optional.empty();
            if (map.size() == capacity) {
                evicted = policy.victim();
                evicted.ifPresent(victim -> {
                    map.remove(victim);
                    policy.onRemove(victim);
                });
            }
            policy.onInsert(key);
            map.put(key, value);
            return evicted;
        }
    }

    /** Same workload for every policy. */
    static void workload(String name, EvictionPolicy<String> policy) {
        var cache = new PolicyCache<String, Integer>(3, policy);
        for (var k : new String[] {"a", "b", "c"}) {
            cache.put(k, 0);
        }
        cache.get("b");
        cache.get("b");
        cache.get("c");
        cache.get("a");
        var evicted = cache.put("d", 0);
        System.out.println(name + ": evicted " + evicted);
    }

    public static void main(String[] args) {
        workload("fifo", new FifoPolicy<>());
        workload("lru", new LruPolicy<>());
    }
}

Output

fifo: evicted Optional[a]
lru: evicted Optional[b]

After inserting a, b, c and reading b, b, c, a, the two policies disagree. FIFO ignores reads and evicts the oldest insert, a. LRU evicts b, whose last use is the oldest. The cache code did not change between the runs. That is the payoff of the strategy: adding LFU, random or 2Q is one new class that implements the interface.

The cost of the generic design is visible in the code. LruPolicy keeps its own ordered set next to the cache's map, so every key is stored twice, and the two structures must stay in step. FifoPolicy.onRemove scans the queue, which is O(n); the cache only calls it for the key it took from victim(), which is at the front, so the scan ends at once here. An LFU policy would fit the same interface but needs frequency counters and a tie-break rule. In an interview, name such limitations and move on.

Thread-safe wrapper

SharedCache wraps any Cache and holds one lock for the duration of each operation. Java values are references, so get can return the stored value directly. The example uses a short stand-in cache built on LinkedHashMap in access order, which is the library version described under design decisions. The wrapper also adds getOrCompute, which holds the lock across the check and the load.

Java

import java.util.LinkedHashMap;
import java.util.Optional;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Function;

public class Main {
    interface Cache<K, V> {
        Optional<V> get(K key);
        void put(K key, V value);
        int size();
    }

    /** A short LRU cache built on LinkedHashMap in access order. Not thread-safe. */
    static final class MapCache<K, V> implements Cache<K, V> {
        private final LinkedHashMap<K, V> map = new LinkedHashMap<>(16, 0.75f, true);
        private final int capacity;

        MapCache(int capacity) {
            this.capacity = capacity;
        }

        @Override public Optional<V> get(K key) { return Optional.ofNullable(map.get(key)); }
        @Override public void put(K key, V value) {
            map.put(key, value);
            if (map.size() > capacity) {
                map.pollFirstEntry(); // the first entry is the least recently used
            }
        }
        @Override public int size() { return map.size(); }
    }

    static final class SharedCache<K, V> implements Cache<K, V> {
        private final Cache<K, V> delegate;

        SharedCache(Cache<K, V> delegate) {
            this.delegate = delegate;
        }

        @Override public synchronized Optional<V> get(K key) { return delegate.get(key); }
        @Override public synchronized void put(K key, V value) { delegate.put(key, value); }
        @Override public synchronized int size() { return delegate.size(); }

        /** Check and load under one lock: the loader runs at most once per missing key. */
        synchronized V getOrCompute(K key, Function<K, V> loader) {
            var hit = delegate.get(key);
            if (hit.isPresent()) {
                return hit.get();
            }
            var loaded = loader.apply(key);
            delegate.put(key, loaded);
            return loaded;
        }
    }

    public static void main(String[] args) {
        var cache = new SharedCache<Integer, Integer>(new MapCache<>(100));

        try (var pool = Executors.newVirtualThreadPerTaskExecutor()) {
            for (int t = 0; t < 4; t++) {
                int base = t * 100;
                pool.submit(() -> {
                    for (int i = 0; i < 10; i++) {
                        cache.put(base + i, i);
                    }
                });
            }
        } // close() waits for every task

        System.out.println("entries: " + cache.size());
        System.out.println("103 -> " + cache.get(103));
        System.out.println("missing -> " + cache.get(999));

        var loads = new AtomicInteger();
        try (var pool = Executors.newVirtualThreadPerTaskExecutor()) {
            for (int t = 0; t < 8; t++) {
                pool.submit(() -> {
                    cache.getOrCompute(500, key -> {
                        loads.incrementAndGet();
                        return key * 2;
                    });
                });
            }
        }
        System.out.println("loads for key 500: " + loads.get());
        System.out.println("500 -> " + cache.get(500));
    }
}

Output

entries: 40
103 -> Optional[3]
missing -> Optional.empty
loads for key 500: 1
500 -> Optional[1000]

Each method holds the lock for exactly one cache operation, so operations from different threads never interleave inside the cache. The result is deterministic (40 distinct keys) even though the order in which threads run is not. The lock also makes each write visible to the next thread that takes it, and close() on the executor waits for the tasks, so the reads in main see every put.

The wrapper does not make compound operations atomic: "get, and if missing compute and put" written by a caller is two lock acquisitions, so two threads can both miss and both compute. getOrCompute closes that gap by holding the lock across the check and the insert, so the loader ran once for eight callers. The cost is that a slow loader blocks every other caller, including callers of unrelated keys. For high contention, shard the cache into N independent SharedCache instances chosen by Math.floorMod(key.hashCode(), N), or use per-key futures in a ConcurrentHashMap.

Extensions

Follow-up question	Answer
Add `remove(key)`	Detach the node, then remove it from the map. The garbage collector reclaims the node.
Weighted entries (by bytes, not count)	Replace the length check with a running total and evict from the tail until the new entry fits.
Entries that expire	Store a deadline in each entry and check it in `get`; see design a key-value store with TTL.
Loading on a miss	Add `getOrCompute(key, loader)` on the wrapper so the lock covers check and load.
Distributed cache	Consistent hashing across nodes; see design a key-value store.

Summary

An LRU cache is a hash map for lookup plus a doubly linked list for recency order, which together give O(1) get and put.
In Java the list nodes refer to each other with object references, and the map values refer to the same nodes. Sentinel head and tail nodes remove the empty-list special cases. The garbage collector reclaims evicted nodes.
LinkedHashMap in access order is the library version of the same structure.
Put the public contract in a Cache interface, return a sealed type such as PutOutcome for closed result sets, and reject an invalid capacity in the constructor.
Make the eviction policy an interface only because it is a stated requirement. The price is a second structure of bookkeeping and an extra call on every operation.
Keep locks out of the core type. A wrapper adds thread safety, and compound operations need their own locked method.
Test against a simple reference model and against the interface so every implementation shares the same checks.