A cache must evict the least recently used entry and every operation has to be O(1). Which two structures do you need, and why is one of them not enough?

Short answer

An O(1) LRU cache needs a hash map from key to list node and a doubly linked list ordered by recency. The map gives constant-time access by key, while the list exposes the least recently used node at one end for eviction. A hash map alone cannot find the oldest entry in O(1), and a list alone cannot find an arbitrary key in O(1).

Two lookups, not one

Write down what the cache is asked to find before naming a structure. get(key) has to locate an entry by its key. Eviction has to locate the entry nobody has touched for the longest time. Those are two different questions about the same set of entries, and no ordinary single structure answers both in constant time.

A hash map answers the first. It does so in expected constant time, and it has no opinion at all about the second. Finding its oldest entry means inspecting all of them, which is O(n).

A recency-ordered list answers the second. The least recently used entry sits at a fixed end, so eviction is a look at a known position. Finding an arbitrary key inside it is a walk, which is O(n) again.

So you keep both, over the same entries, and each covers the other's blind spot. That is the whole answer. Everything after it is about keeping the two in agreement.

What the map stores is the graded decision

A candidate who has memorised this problem says "hash map and a doubly linked list" in under two seconds. The question that separates recall from understanding is what the map's value is.

Suppose it is the cached value. Then the structures are not connected, and a hit has to move that entry to the front of the list, and to do that it must find the entry's node, and the only way to find a node in a linked list is to walk it. You have written an O(n) cache with two structures in it.

The map's value is the node. A hit resolves the key to a node in one step, and the node already holds pointers to its neighbours, so unlinking it and relinking it at the front is a fixed number of pointer writes with no search anywhere in the operation.

flowchart LR
  M[Hash map key to node] --> B
  M --> C
  M --> D
  H[head sentinel] --> B[node B most recent]
  B --> C[node C]
  C --> D[node D least recent]
  D --> T[tail sentinel]

The arrows worth looking at are the three leaving the map, because they point into the middle of the list. That is the only reason the list never has to be traversed.

That settles why the list is doubly linked. Unlinking a node requires the node before it, so that its forward pointer can be redirected. You have the node; you do not have its predecessor without walking to it. The backward pointer is not a convenience, it is what the constant-time claim rests on.

The implementation, and the two lines that carry it

Sentinel nodes at both ends remove every special case around an empty list or a single-element list, which is where hand-written versions leak bugs.

class Node { int key, value; Node prev, next; }

private final Map<Integer, Node> index = new HashMap<>();
private final Node head = new Node(), tail = new Node();   // sentinels, never hold data

int get(int key) {
    Node n = index.get(key);
    if (n == null) return -1;
    unlink(n);
    pushFront(n);          // a read reorders the cache - get is a write
    return n.value;
}

void put(int key, int value) {
    Node existing = index.get(key);
    if (existing != null) {
        existing.value = value;
        unlink(existing);
        pushFront(existing);
        return;            // an update must not evict anything
    }
    if (index.size() == capacity) {
        Node victim = tail.prev;
        unlink(victim);
        index.remove(victim.key);   // the node has to carry its key, or you cannot do this
    }
    Node n = new Node();
    n.key = key; n.value = value;
    index.put(key, n);
    pushFront(n);
}

The comment on the eviction line is the one people trip over. You reach the victim through the list, so you hold a node and need a key to delete from the map. If the node does not store its own key, the removal is impossible without scanning the map, and a working solution turns into a broken one at the last step.

The other line is the return inside put. Overwriting an existing key changes no entry count, so evicting there throws away an entry the cache had room for.

A read is a write, and that is not a detail

get mutates the structure. Interviewers watch for this specifically, because the version that returns a value without touching the order passes every test built from puts and produces the wrong victim under a realistic read-heavy workload, where the whole point of the policy is that reads count as use.

It also has a consequence people are asked about immediately afterwards. Because every read mutates shared state, a single lock around the cache serialises reads against each other, so this exact structure is the wrong shape for a concurrent cache. Production caches usually approximate recency instead, with per-entry reference bits or a small buffer of recent accesses drained in batches, precisely so that a read can avoid taking the write path. Saying that unprompted is worth more than the implementation itself.

Stating the complexity precisely

The list operations are O(1) worst case: a bounded number of pointer writes, no loops. The map is O(1) expected, amortised over resizes, and not O(1) worst case. A chained bucket that has collected many colliding keys degrades that lookup, and a resize on insert is O(n) for the one insert that triggers it. In HotSpot's HashMap, a bucket that grows past a threshold is converted to a tree, which bounds the bad case at O(log n) rather than O(n) for comparable keys.

So say it precisely. The cache is O(1) expected per operation, and the map is the reason it is not a worst-case bound. Candidates who say "O(1)" flatly are usually not wrong about the design, but the precision is free and it is being noticed.

Say why a heap is rejected on a bound rather than on instinct. Ordering entries by a last-used timestamp in a priority queue makes eviction O(log n), and updating a timestamp on a hit needs a decrease-key, which requires an index from key to heap position on top of the heap. More machinery, worse bound.

Where the language already has this

Java's LinkedHashMap takes an accessOrder flag in its constructor, and overriding removeEldestEntry turns it into a bounded LRU cache in about five lines. Naming it is a good instinct in real code and a bad answer to this question, because the interviewer is asking you to build the thing the standard library already built. Mention it in one sentence, then implement it.

The two structures are easy to name and easy to say wrongly: the map's value has to be the list node, because that pointer is the only thing standing between a constant-time hit and a traversal.

© 2026 Preptima. Originally published at preptima.com.