Introduction

Almost every backend system has a cache somewhere in it.

A database connection pool, an API response cache, a CDN edge node, even your operating system's page table — they all face the same constraint: memory is finite, but the data you'd like to keep around is not.

So you need a policy for deciding what stays and what gets thrown away.

The Least Recently Used (LRU) policy is the most common answer, and it shows up everywhere: Redis' maxmemory-policy, Java's LinkedHashMap, CPU cache eviction, browser caches, and almost every "design a cache" interview question you'll ever get.

This post walks through how an LRU cache actually works under the hood, builds one from scratch in Java, and then covers the mistakes that quietly break correctness or performance even after the interview is over.

What Is an LRU Cache, Really?

The rule is simple to say and easy to get wrong in code:

When the cache is full and a new item needs to be added, evict the item that hasn't been accessed for the longest time.

Two operations need to support this:

• get(key) — return the value, and mark this key as "just used"
• put(key, value) — insert or update a value, and if the cache is now over capacity, evict the least recently used entry

The hard constraint that makes this an interesting problem is performance: both operations are expected to run in O(1) time, not O(n). That single requirement eliminates most "obvious" solutions.

Why Not Just Use an Array or a Simple HashMap?

It's worth ruling out the naive options first, because understanding why they fail is what makes the real solution make sense.

A plain array or ArrayList: You could store entries in order of use and shift the accessed one to the front. The problem is that shifting elements in an array is O(n) — every get would scan and re-arrange the whole list.

A plain HashMap alone: A HashMap gives you O(1) lookups, but it has no concept of order. There's no cheap way to ask "which key has gone untouched the longest?" without scanning every entry.

A HashMap + a sorted structure by timestamp: You could store a "last used" timestamp per key and sort by it, but maintaining that order on every access means O(log n) or worse, and timestamp collisions get messy.

What you actually need is a structure that gives you:

1. O(1) lookup by key (a HashMap solves this)
2. O(1) "move this item to the front" and O(1) "remove the item at the back" (a doubly linked list solves this)

Combine them, and you get O(1) for everything.

The Core Idea: HashMap + Doubly Linked List

The classic LRU cache is two data structures working together:

• A HashMap that maps key → node, for instant lookups.
• A doubly linked list that keeps nodes ordered from most recently used (head) to least recently used (tail).

Every get or put on an existing key moves that node to the head. Every eviction removes the node at the tail. Both are O(1) pointer operations on a doubly linked list — no shifting, no scanning.

graph LR
    subgraph HashMap
        K1["key: 7"] --> N1
        K2["key: 3"] --> N2
        K3["key: 9"] --> N3
    end

    subgraph "Doubly Linked List — MRU → LRU"
        HEAD["head (dummy)"] <--> N3["Node: key 9"]
        N3 <--> N2["Node: key 3"]
        N2 <--> N1["Node: key 7"]
        N1 <--> TAIL["tail (dummy)"]
    end

The dummy head and tail nodes aren't strictly required, but they remove almost every null-check edge case from the implementation — more on that in the mistakes section.

Building It in Java: Step by Step

The Node

Each node needs a key (so it can be removed from the HashMap during eviction), a value, and two pointers.

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

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

The Cache Shell

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head; // most recently used side
    private final Node tail; // least recently used side

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

Notice the cache starts as head <-> tail with nothing in between. Every real node will be inserted somewhere in that gap.

Helper Operations

These three private methods are the entire engine. Everything else is just composition of these.

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

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

private void moveToHead(Node node) {
    removeNode(node);
    addToHead(node);
}

get(key)

public int get(int key) {
    Node node = cache.get(key);
    if (node == null) {
        return -1; // or throw, depending on your contract
    }
    moveToHead(node);
    return node.value;
}

put(key, value)

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

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

    Node newNode = new Node(key, value);
    cache.put(key, newNode);
    addToHead(newNode);

    if (cache.size() > capacity) {
        Node lru = tail.prev;
        removeNode(lru);
        cache.remove(lru.key);
    }
}

That's a complete, correct, O(1)-per-operation LRU cache in about 50 lines.

Complexity Analysis

Operation	Time	Space
get	O(1)	—
put	O(1)	—
Overall space	—	O(capacity)

Every pointer update touches a fixed number of nodes regardless of how many entries are in the cache. The HashMap gives the lookup, the linked list gives the ordering, and neither one needs to scan the other.

The Lazy Way: Java's Built-in LinkedHashMap

If you're not in an interview and just need this behavior in production code, Java already ships an LRU-capable structure.

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheSimple<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCacheSimple(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true reorders on get()
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

LinkedHashMap already maintains a doubly linked list internally — passing true for accessOrder tells it to reorder on access instead of just on insertion. Overriding removeEldestEntry is the entire eviction policy. It's genuinely the same data structure as the manual version, just hidden behind the JDK's implementation.

Knowing both matters: the manual version is what interviewers want to see because it proves you understand why it's O(1); the built-in version is what you should actually ship unless you have a specific reason not to.

Mistakes Engineers Make With LRU Caches

1. Using an ArrayList or LinkedList (Java's, not a custom doubly linked list) for ordering

java.util.LinkedList doesn't give you O(1) removal of an arbitrary node unless you already hold a reference to it — and Java's LinkedList doesn't expose its internal nodes. Calling remove(Object) on it still does an O(n) search internally. You need your own Node class with raw prev/next pointers, exactly like the implementation above.

2. Skipping the dummy head and tail nodes

Without sentinel nodes, every insert and remove needs special-case branches for "is this the first node?" and "is this the last node?" That's where most LRU bugs come from in practice — an off-by-one in a null check that only shows up when the cache has exactly one element.

// Fragile — works most of the time, breaks on edge cases
if (head == null) {
    head = newNode;
} else {
    // ...now handle tail separately, and update separately, and...
}

The dummy-node version sidesteps this entirely because head and tail always exist, so addToHead and removeNode never need a null check.

3. Updating a value without moving the node

A common bug:

// Bad — value is updated but the node's position never changes
public void put(int key, int value) {
    Node existing = cache.get(key);
    if (existing != null) {
        existing.value = value; // forgot moveToHead(existing)
        return;
    }
    // ...
}

This silently breaks the eviction order. The entry was just touched, but the cache still thinks it's stale, and a genuinely fresher entry might get evicted instead.

4. Evicting before inserting, or checking capacity at the wrong time

// Bad — checks capacity before the new entry is added,
// so the cache can grow one element past its limit
if (cache.size() >= capacity) {
    evict();
}
cache.put(key, newNode);

The check has to happen after the new node is added, comparing against the post-insert size — otherwise you evict one entry too early on every single insert, or let the cache silently overflow by one.

5. Forgetting that capacity == 0 is a valid input

A cache with zero capacity should accept no entries and always miss on get. If your constructor doesn't validate this, put will happily insert a node and then try to evict it in the same call — which works by accident in the implementation above, but plenty of hand-rolled versions assume capacity >= 1 somewhere and throw or corrupt state.

6. Treating LinkedHashMap as "good enough" for high-throughput concurrent caches

LinkedHashMap is not thread-safe. Wrapping every call in synchronized works but turns your cache into a single global lock — every thread blocks every other thread, even threads working on unrelated keys. For real concurrent workloads, this becomes the bottleneck before the rest of your system does.

// Works, but serializes all access — no real concurrency
public synchronized int get(int key) { ... }
public synchronized void put(int key, int value) { ... }

For anything beyond light, mostly-single-threaded use, reach for Caffeine or Guava's CacheBuilder, which implement segmented, lock-light eviction specifically so concurrent reads and writes don't serialize on one lock.

7. Ignoring what eviction actually does to the evicted value

If your cached values hold resources — open file handles, database connections, native buffers — silently dropping them on eviction leaks those resources. LinkedHashMap.removeEldestEntry and a custom doubly-linked-list eviction both need an explicit cleanup hook (a close() call, a listener, whatever your value type requires) at the point of eviction, not just removal from the map.

Where LRU Shows Up in Real Systems

It's worth knowing this isn't just an interview exercise:

• Redis uses an approximate LRU algorithm (sampling a small set of keys rather than tracking exact recency) as one of its maxmemory-policy options, trading perfect accuracy for speed at scale.
• CDNs and browser caches evict the least recently requested assets when storage fills up.
• Database buffer pools (including parts of how InnoDB manages its buffer pool) use LRU-like lists to decide which pages stay in memory.
• CPU caches use LRU or LRU-approximations as part of their cache replacement policy.

The pattern repeats because the underlying constraint — finite memory, unbounded demand — is universal. Once you understand the HashMap + doubly linked list combination, you'll recognize it disguised inside a dozen other systems.

Final Thoughts

The LRU cache is a small piece of code that teaches a disproportionately large lesson: picking the right combination of data structures can turn an O(n) problem into an O(1) one.

The HashMap gives you the lookup. The doubly linked list gives you the ordering. Neither one alone solves the problem, but together — with dummy head and tail nodes to keep the edge cases honest — they make both get and put constant time.

Whether you're implementing it by hand for an interview or reaching for LinkedHashMap or Caffeine in production, the mental model is the same. Know how it works underneath, and the mistakes in the section above stop being mysterious bugs and start being things you catch in code review before they ship.