LRU Cache Visualization for Coding Interviews

By Rahul Kumar · Senior Software Engineer · Updated May 2026 · Category: Linked Lists

HashMap + doubly-linked list; O(1) get/put with eviction.

Concept

An LRU (Least Recently Used) cache is the canonical example of a data structure that has to satisfy two access patterns at once: constant-time key lookup and constant-time ordering updates. Neither a plain HashMap nor a plain linked list gets you there. A HashMap knows who is there but not who is oldest; a linked list tracks recency but makes you scan to find a key. The standard construction stitches them together: a HashMap from key to node pointer, and a doubly linked list of nodes in recency order. Every get and put then runs in genuine O(1) time, because every operation is a hash lookup plus a constant number of pointer rewires. This pattern shows up everywhere in system design, from CDN edge caches and database buffer pools to Redis maxmemory-policy=allkeys-lru, which makes it the single most useful cache structure to know by heart.

LRU Cache — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive LRU Cache visualization — animated algorithm, step-through, and live data-structure updates.

How it works

The doubly linked list stores entries in order of recency, with the most recently touched entry at the head and the least recently used at the tail. Two sentinel nodes at the head and tail eliminate all of the usual null checks when inserting and removing. The HashMap maps each key to the list node that holds its value, so you can find a node in O(1) and splice it out of wherever it currently sits in O(1). On get, you hash the key, fail fast if it is absent, and otherwise unlink the node from its current position and reinsert it right after the head sentinel, then return its value. On put, if the key already exists you overwrite the value and move the node to the head. If it does not exist you create a new node, insert it after the head, register it in the HashMap, and if the size now exceeds capacity you remove the node right before the tail sentinel and also delete its key from the HashMap. Because every path is bounded by a fixed set of pointer updates plus a single hash operation, the amortized and worst-case cost of both operations is O(1). The space cost is O(capacity), one node and one map entry per cached key.

Implementation

LRUCache with HashMap + doubly linked list

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

public class LRUCache<K, V> {
    private static class Node<K, V> {
        K key; V val;
        Node<K, V> prev, next;
        Node(K k, V v) { this.key = k; this.val = v; }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> index = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);

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

    public V get(K key) {
        Node<K, V> n = index.get(key);
        if (n == null) return null;
        moveToHead(n);
        return n.val;
    }

    public void put(K key, V value) {
        Node<K, V> n = index.get(key);
        if (n != null) { n.val = value; moveToHead(n); return; }
        Node<K, V> fresh = new Node<>(key, value);
        index.put(key, fresh);
        addAfterHead(fresh);
        if (index.size() > capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            index.remove(lru.key);
        }
    }

    public int size() { return index.size(); }

    private void addAfterHead(Node<K, V> n) {
        n.prev = head; n.next = head.next;
        head.next.prev = n; head.next = n;
    }
    private void unlink(Node<K, V> n) {
        n.prev.next = n.next; n.next.prev = n.prev;
    }
    private void moveToHead(Node<K, V> n) { unlink(n); addAfterHead(n); }
}

Complexity

Time: O(1) amortized and worst-case for get and put
Space: O(capacity) for the map plus doubly linked list

Common pitfalls

Using a singly linked list: O(N) unlink forces get/put to O(N)
Forgetting to remove the evicted key from the HashMap, leaving a dangling pointer
Not using head/tail sentinels, leading to null-pointer branches in every splice
Using LinkedHashMap with accessOrder=true is fine for interviews but hides the mechanics and is not thread-safe
Treating put of an existing key as insert: you must update and move, not add a duplicate
Making the cache shared across threads without external synchronization or a concurrent variant

Key design decisions & trade-offs

Eviction policy — Chosen: LRU over LFU or FIFO. LRU matches temporal locality of most workloads; LFU needs frequency counters and decay, FIFO ignores recency
List implementation — Chosen: Custom doubly linked list instead of java.util.LinkedList. java.util.LinkedList does not expose node handles, so removing a known element would be O(N)
Concurrency — Chosen: Single-threaded by default, synchronize externally. A lock-free LRU is complex; for multi-threaded workloads prefer Caffeine or a segmented cache

Practice problems

LRU Cache

Interview follow-ups

Implement an LFU cache with O(1) get and put
Add TTL expiry on top of LRU
Make the cache thread-safe with a single lock, then with striping
Implement a size-weighted LRU where entries have variable cost
Implement an LRU-K cache that tracks the last K accesses instead of just the last one

Why it matters

LRU Cache is a core part of the Linked Lists toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".