Free lesson · DSA Mastery - Interview Prep, End to End

LRU Cache

Hard9 min readdsadata-structure-design

LRU Cache

LRU Cache opens the Cache Design sub-group with one of the most-asked design problems: a fixed-capacity key-value cache that evicts the least recently used entry when full, with both get and put in O(1). The canonical design composes a hash map (key → node, for O(1) lookup) with a doubly linked list ordered by recency (most recent at one end, least recent at the other), so touching an entry moves its node to the front and eviction removes the back node - both O(1). It is the definitive "hash map plus linked list" composition and a rite of passage for technical interviews. We present the hash map + doubly linked list design (canonical).

The insight: a cache needs two things at once - instant lookup by key and instant knowledge of which entry is least recently used. A hash map gives the first (key → entry in O(1)) but has no order. A doubly linked list gives the second (maintain entries in recency order, with O(1) removal and insertion if you hold the node) but can't find a key quickly. Compose them: the map stores key → the list node, and the list orders nodes by recency. Every access moves the touched node to the front; eviction pops the back. Each structure covers the other's blind spot.

The Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

LRUCache cache = new LRUCache(2);
cache.put(1, 1);      // cache: {1=1}
cache.put(2, 2);      // cache: {1=1, 2=2}
cache.get(1);         // returns 1; 1 is now most recent. cache: {2=2, 1=1}
cache.put(3, 3);      // evicts key 2 (LRU). cache: {1=1, 3=3}
cache.get(2);         // returns -1 (not found)
cache.put(4, 4);      // evicts key 1 (LRU). cache: {3=3, 4=4}
cache.get(1);         // returns -1 (not found)
cache.get(3);         // returns 3
cache.get(4);         // returns 4

Constraints:

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls will be made to get and put.

Approaches Overview

#	Approach	get	put	Verdict
1	Hash map + doubly linked list (recency order)	O(1)	O(1)	Canonical

This problem has one design that meets the O(1) requirement: a hash map from key to a doubly-linked-list node, plus a doubly linked list keeping nodes in recency order (most recent at the front, least recent at the back). get looks up the node in the map, moves it to the front (now most recent), and returns its value. put updates or inserts at the front; if over capacity, it removes the back node (the least recently used) and erases its map entry. The doubly linked list is essential - it allows O(1) removal of any node given a pointer to it.

Approach: Hash Map + Doubly Linked List - Canonical

The Idea

Maintain a doubly linked list of (key, value) nodes with sentinel head and tail dummies; the node just after head is most recently used (MRU), the node just before tail is least recently used (LRU). A hash map maps key → its node. get(key): if absent return −1; else unlink the node and re-insert it right after head (mark as MRU), return its value. put(key, value): if present, update value and move to front; else create a node, insert after head, add to map; if size exceeds capacity, remove the node before tail (LRU) and erase it from the map.

Logic Flowchart

graph TD
    A["map: key→node; list: head ⇄ ... ⇄ tail (MRU after head, LRU before tail)"] --> B["get(key)"]
    B --> C{"key in map?"}
    C -->|No| D["return -1"]
    C -->|Yes| E["move node to front (MRU); return value"]
    F["put(key, value)"] --> G{"key in map?"}
    G -->|Yes| H["update value; move to front"]
    G -->|No| I["insert new node at front; map[key]=node"]
    I --> J{"size > capacity?"}
    J -->|Yes| K["remove node before tail (LRU); erase from map"]
    J -->|No| L["done"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style J fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style K fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style L fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the LRU cache. A map locates each key's node and a doubly linked list orders nodes by recency; every access moves a node to the front, and when capacity is exceeded the least recently used node before the tail is evicted.

Code

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }

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

    public LRUCache(int capacity) {
        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);                       // mark most recently used
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToFront(node);
            return;
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        addAfterHead(fresh);
        if (map.size() > capacity) {             // evict LRU
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
    }

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

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

    private void moveToFront(Node node) {
        remove(node);
        addAfterHead(node);
    }
}

// Usage:
// LRUCache cache = new LRUCache(2); cache.put(1,1); cache.put(2,2); cache.get(1) -> 1;
// cache.put(3,3) evicts 2; cache.get(2) -> -1; cache.put(4,4) evicts 1; cache.get(3) -> 3

This Java code pairs a hash map from key to node with a doubly linked list using head and tail sentinels; get and put move the touched node just after head as most recently used, and put evicts the node before tail when capacity is exceeded.

Step-by-Step Walkthrough

A frame-by-frame trace on the Example (capacity 2):

graph LR
    F0["put(1,1), put(2,2): list head⇄2⇄1⇄tail (2 is MRU)"]
    F1["get(1): move 1 to front → head⇄1⇄2⇄tail. returns 1"]
    F2["put(3,3): insert 3 front; size 3 > 2 → evict tail.prev = 2. head⇄3⇄1⇄tail"]
    F3["get(2): -1. put(4,4): evict LRU 1 → head⇄4⇄3⇄tail. get(3)→3, get(4)→4"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough runs the cache. Accessing key one moves it to the front; inserting key three evicts the least recently used key two; inserting key four evicts key one, leaving three and four.

Result: evictions follow least-recently-used order; final gets return 3 and 4.

Complexity

Time: get and put both O(1). Space: O(capacity) for the map and list.

Complexity Comparison

Approach	get	put	Space	Key Idea
Hash map + doubly linked list	O(1)	O(1)	O(capacity)	Map locates node; list orders by recency

The composition is the canonical answer: the map gives O(1) key lookup, the doubly linked list gives O(1) reordering and eviction because each node can be unlinked in constant time given its pointers. A singly linked list would make removing a node O(n) (no back-pointer to fix the predecessor); the doubly linked list is what makes both operations O(1). This map-plus-list pattern is the foundation for LFU next.

Variations & Follow-ups

Why does the design need both a hash map and a doubly linked list?

The two requirements pull in different directions. get/put must find an entry by key in O(1) - that's a hash map's specialty, but a hash map has no concept of ordering, so it can't tell you which entry is least recently used. Tracking recency requires an ordered structure where you can move an accessed entry to the "most recent" end and read the "least recent" end - that's what the linked list provides. Neither alone suffices: a map can't answer "what's the LRU?" in O(1), and a list can't answer "where is key k?" in O(1). Composing them - the map's value is a pointer into the list - lets each operation use the right structure: the map to locate the node, the list to reorder or evict it. This is the same compose-two-structures principle as Insert Delete GetRandom, and it's why LRU is the archetypal example of it.

Why must the linked list be doubly linked, not singly?

The core operations move an arbitrary node to the front (on access) and remove the back node (on eviction), both of which require unlinking a node in O(1). To unlink a node, you must fix its predecessor's next pointer - which means you need a pointer to the predecessor. A singly linked list only has forward pointers, so finding a node's predecessor requires scanning from the head, O(n). A doubly linked list stores each node's prev pointer, so given any node (which the map hands you directly), you can splice it out in O(1): node.prev.next = node.next; node.next.prev = node.prev. The backward pointer is exactly what makes arbitrary-node removal constant time. Without it, LRU degrades to O(n) per operation, failing the requirement. The doubly linked list is not a stylistic choice; it's mandated by the O(1) arbitrary-removal need.

Why use sentinel head and tail dummy nodes?

The list constantly inserts at the front and removes at the back, and these operations involve rewiring neighbor pointers. Without sentinels, inserting into an empty list, removing the only node, or operating at the actual ends all become special cases requiring null checks (e.g., "if this is the first node, set head; if removing the last, update tail"). Sentinel dummies - a permanent head before the first real node and a permanent tail after the last - guarantee every real node always has a non-null prev and next, so insertion and removal are uniform pointer splices with no edge-case branching. "Insert after head" always works; "remove the node before tail" always works, even when the cache is empty (it just touches the sentinels). This eliminates a whole class of null-pointer bugs and is standard practice for production doubly-linked-list code. The two sentinels cost O(1) extra space for far simpler, more robust logic.

Why does both `get` and `put` (on an existing key) move the node to the front?

"Recently used" means accessed - and both reading (get) and writing (put) an existing key count as using it. The LRU policy evicts the entry untouched for the longest time, so every touch must refresh the entry's recency by moving it to the MRU end (just after head). If get didn't move the node, a frequently-read key could be wrongly evicted as "least recently used" despite constant access. Likewise, updating a key's value via put is an access and must refresh recency. The back of the list (just before tail) therefore always holds the genuinely least-recently-used entry, so eviction is correct. The discipline is: any operation that observes or modifies a key moves its node to the front; only never-touched-recently nodes drift toward the back and get evicted. This is the invariant that makes the list's back the true LRU.

What about edge cases?

Capacity 1: Every put of a new key evicts the previous one; only one entry ever held.
Updating an existing key (put on present key): Value updated, node moved to front, no eviction (size unchanged).
get on a missing key: Returns −1; list unchanged.
put that triggers eviction: Insert new node at front first, then remove the back if over capacity.
Repeated gets of the same key: Each refreshes its recency (already MRU, harmless re-splice).

Common Interview Pitfalls

Using a singly linked list. Arbitrary-node removal becomes O(n); use a doubly linked list for O(1) unlinking.
Forgetting to move the node on get. A read is an access; not refreshing recency causes wrong evictions.
Not erasing the evicted key from the map. The map and list must stay synchronized; remove both.
Mishandling empty-list edges. Use sentinel head/tail dummies to avoid null-pointer special cases.

Why This Topic Matters

LRU Cache is the definitive hash map + doubly linked list composition: the map gives O(1) key lookup, the doubly linked list gives O(1) recency reordering and eviction (enabled by backward pointers and sentinels). It cements that "recently used" means any touch refreshes recency, and that the right two structures, each covering the other's weakness, meet a contract neither could alone - the direct foundation for LFU.

The next topic, LFU Cache, raises the difficulty: evict the least frequently used entry, breaking ties by least recently used among those of equal frequency, still in O(1). It needs more bookkeeping than LRU - a key → node map, a frequency → doubly-linked-list map (one recency-ordered list per frequency count), and a running minFreq tracker - so that get/put bump a node's frequency by moving it from its current frequency list to the next, and eviction removes the LRU node from the minFreq list. It is the harder cousin of LRU and closes the Cache Design sub-group with the most intricate multi-structure bookkeeping so far.

Back to DSA Mastery - Interview Prep, End to End

LRU Cache

LRU Cache

The Problem

Approaches Overview

Approach: Hash Map + Doubly Linked List - Canonical

The Idea

Logic Flowchart

Code

Step-by-Step Walkthrough

Complexity

Complexity Comparison

Variations & Follow-ups

Why does the design need both a hash map and a doubly linked list?

Why must the linked list be doubly linked, not singly?

Why use sentinel head and tail dummy nodes?

Why does both get and put (on an existing key) move the node to the front?

What about edge cases?

Common Interview Pitfalls

Why This Topic Matters

Why does both `get` and `put` (on an existing key) move the node to the front?