Design an LRU Cache Data Structure

An LRU cache needs get and put in O(1), and eviction of the least recently used entry in O(1). No single data structure does both: a hash map has the lookup and no order, a linked list has the order and no lookup. The answer is to run them together, with the map’s values pointing at the list’s nodes.

Written against Java 17.

The requirements

LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);        // 1     — key 1 is now the most recently used
cache.put(3, 3);     //       — evicts key 2, the least recently used
cache.get(2);        // -1    — gone

Note that get counts as a use. That is what makes a plain queue insufficient: recency changes on read, not only on write.

Why two structures

	lookup by key	reorder on access	evict oldest
HashMap	O(1)	—	—
Array or ArrayList	O(n)	O(n)	O(n)
Singly linked list	O(n)	O(n)	O(n) — no back pointer
Doubly linked list	O(n)	O(1) given the node	O(1)
HashMap + doubly linked list	O(1)	O(1)	O(1)

The combination works because the map stores the node, not the value. Given a key, the map finds the node in O(1); given the node, the list unlinks and relinks it in O(1) because it has both neighbours.

A singly linked list fails on exactly that point: unlinking a node needs its predecessor, and finding that is a scan.

The implementation

public class LRUCache {

    private static final class Node {
        int key, value;
        Node prev, next;

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

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);   // sentinel: most recent side
    private final Node tail = new Node(0, 0);   // sentinel: least recent side

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;

        moveToFront(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node existing = map.get(key);

        if (existing != null) {
            existing.value = value;
            moveToFront(existing);
            return;
        }

        if (map.size() == capacity) {
            Node lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);          // needs the KEY — this is why nodes store it
        }

        Node node = new Node(key, value);
        map.put(key, node);
        linkAfterHead(node);
    }

    private void moveToFront(Node node) {
        unlink(node);
        linkAfterHead(node);
    }

    private void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void linkAfterHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

The two details that matter

The nodes store the key as well as the value. On eviction the list gives you the node; removing it from the map needs the key, and there is no way to search a HashMap by value in O(1). Storing only the value produces a cache that leaks map entries for evicted nodes — the list stays the right size while the map grows forever.

The sentinels remove every null check. head and tail are permanent nodes that hold no data, so the list is never empty from the pointer manipulation’s point of view. unlink is two assignments with no branches, because node.prev and node.next are always non-null.

Without them, unlink needs cases for “the only node”, “the first node” and “the last node”, and linkAfterHead needs its own. That is roughly twelve extra lines and three places to get a null check wrong.

The cost is two objects for the lifetime of the cache, which is not a cost.

The eviction order

head.next is the most recently used and tail.prev is the least. Which end is which is arbitrary as long as it is consistent — picking one and writing it in a comment saves reading the pointer manipulation to work it out.

Eviction reads tail.prev, which is the node farthest from the head, meaning the one longest since its last moveToFront. Both get and put on an existing key call moveToFront, which is what implements “recently used” rather than “recently written”.

LinkedHashMap already does this

Map<Integer, Integer> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
};

The third constructor argument is access order rather than insertion order, and removeEldestEntry is a hook called after every insertion. Together they are an LRU cache in five lines.

LinkedHashMap maintains exactly the structure above internally — a hash table with a doubly linked list threaded through the entries. Writing it by hand is an exercise; in production this is the version to use, unless the eviction policy needs to be something the hook cannot express.

The interview question is really “do you know why two structures are needed”, and answering with LinkedHashMap alone usually does not demonstrate that.

Tracing an eviction

Capacity 2, after put(1,1), put(2,2), get(1), put(3,3):

operation	list, head first	map keys
put(1,1)	1	1
put(2,2)	2 1	1, 2
get(1)	1 2	1, 2
put(3,3)	3 1	1, 3

The get(1) is the step that decides the eviction. Without it, key 1 would be at the tail and key 2 would survive — which is why a test that never reads before overflowing does not exercise the policy at all.

That is the test worth writing first: fill to capacity, read the oldest entry, insert one more, and assert that the entry you did not read is the one gone.

Testing it against a reference

The invariants are easy to state and cheap to check after every operation:

private void checkInvariants() {
    int listSize = 0;
    for (Node n = head.next; n != tail; n = n.next) {
        assert n.next.prev == n : "broken back pointer";
        assert map.get(n.key) == n : "map and list disagree";
        listSize++;
        assert listSize <= capacity : "list longer than capacity";
    }
    assert listSize == map.size() : "map and list sizes differ";
}

The map-and-list-agree check is the one that catches the missing-key bug described above, and the size comparison catches it too — the map grows while the list does not. Running this after every operation in a randomised test of a few thousand calls is more effective than any number of hand-written scenarios.

Thread safety

Neither implementation is thread-safe, and the failure is worse than a lost update: two concurrent moveToFront calls can corrupt the list’s pointers, producing a cycle or a detached segment. After that, eviction walks into a loop or drops entries silently.

Wrapping every method in synchronized works and serialises the whole cache, which for a read-dominated workload is exactly the wrong shape.

The practical answer is Caffeine or Guava’s cache, which use a different design — an approximation of LRU with buffered access records — precisely because strict LRU has a single point of contention: the head of the list must be updated on every read, so a purely read-only workload still writes.

That is the structural criticism of LRU worth knowing. ConcurrentHashMap plus a random or segmented eviction policy scales better and approximates the hit rate closely.

Related: HashMap for the lookup half and Queue and Deque for the list half. More in the algorithms guides.

Frequently asked questions

Why does an LRU cache need two data structures?

A hash map gives O(1) lookup and no order; a doubly linked list gives O(1) reordering and eviction and no lookup. Neither does both.

Why a doubly linked list rather than a singly linked one?

Unlinking a node needs its predecessor. A singly linked list has to scan to find it, which makes the reorder O(n).

Why do the nodes store the key?

Eviction finds the node through the list, and removing it from the map needs the key. Without it the map grows forever while the list stays bounded.

What are the sentinel nodes for?

They remove every null check. With permanent head and tail nodes the list is never empty from the pointer code’s perspective, so unlink and link are branch-free.

Does get count as a use?

Yes — that is what LRU means, and it is why a plain queue is insufficient. Both get and an update to an existing key move the node to the front.

Can I just use LinkedHashMap?

Yes. Construct it with accessOrder = true and override removeEldestEntry. It maintains the same structure internally.

What is the time complexity?

O(1) for both get and put, amortised over the hash map’s resizing. Space is O(capacity).

Is it thread-safe?

No, and concurrent access corrupts the list pointers rather than merely losing an update. Synchronising every method serialises the cache.

Why do production caches not use strict LRU?

Every read must update the head of the list, so a read-only workload still contends on one pointer. Caffeine and similar libraries buffer access records and approximate the policy.

What should get return for a missing key?

The interview version returns -1. Real code should return Optional or throw, since -1 is a legitimate cached value.