LRU Cache

MediumDesign · Hash Map + Doubly Linked List🧩 Data Structure Design LeetCode #146 ↗Updated Oct 30, 2026

Problem

Build a key–value cache with a fixed capacity. get(key) returns the value or -1; put(key, value) inserts or updates. Both count as a use. When an insert would exceed capacity, first evict the least recently used key. Both operations must be O(1) on average.

Inputcap=2; put(1,1) put(2,2) get(1)Output1

Inputput(3,3) get(2)Output-1 (2 was LRU)

Inputput(4,4) get(1) get(3)Output-1, 3

1 ≤ capacity ≤ 3000 · 0 ≤ key ≤ 10⁴ · 0 ≤ value ≤ 10⁵ · ≤ 2·10⁵ calls · O(1) get/put

Try it yourself

Java

class LRUCache {
    public LRUCache(int capacity) {
        
    }

    public int get(int key) {
        
    }

    public void put(int key, int value) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A hash map gives O(1) lookup but no order; a list gives order but O(n) lookup. Store list nodes in the map: a doubly linked list lets you unlink any node in O(1), so “move to front” and “evict from back” are both O(1).

PatternData Structure Design

Instinct Implement a class whose methods must all hit a time bound (often O(1)) - write each method's target cost, then glue a hash map to a structure that keeps order.

Memory hack Finder plus keeper - a hash map finds it fast, a list/heap/array keeps the order, and every method updates both.

Open the Data Structure Design guide →

Approaches

Brute ForceHashMap + Recency List (Linear Remove)

Time O(capacity) per opSpace O(capacity)

Values in a map, keys in a list from least to most recently used. Each use removes the key from the list and re-appends it; evict from the front. Finding the key in the list is a linear scan.

Java

class LRUCache {
    private final int capacity;
    private final Map<Integer, Integer> map = new HashMap<>();
    private final LinkedList<Integer> order = new LinkedList<>(); // front = LRU
    public LRUCache(int capacity) { this.capacity = capacity; }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        order.remove(Integer.valueOf(key)); // O(n) search by value
        order.addLast(key);
        return map.get(key);
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) order.remove(Integer.valueOf(key));
        else if (map.size() == capacity) map.remove(order.removeFirst());
        map.put(key, value);
        order.addLast(key);
    }
}

Easy to write, but every access scans the list — misses the O(1) requirement.

BetterLinkedHashMap (Access Order)

Time O(1) avgSpace O(capacity)

LinkedHashMap is a hash map threaded with a doubly linked list. With accessOrder = true each get/put moves the entry to the end; removeEldestEntry evicts the head after a put.

Java

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // true = order by access, not insertion
        this.capacity = capacity;
    }
    public int get(int key) { return super.getOrDefault(key, -1); }
    public void put(int key, int value) { super.put(key, value); }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

Optimal complexity in a few lines, but interviewers usually want it built by hand.

OptimalHashMap + Hand-built Doubly Linked List

Time O(1) avgSpace O(capacity)

Map key → Node; nodes sit between sentinels head (most recent) and tail (LRU). A use unlinks the node and re-adds it after head; overflow evicts tail.prev (its stored key cleans the map).

Java

class LRUCache {
    private class Node {
        int key, val; Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0); // sentinels
    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;
        addFront(unlink(node)); // mark as most recent
        return node.val;
    }
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) { // update in place, mark as recent
            node.val = value;
            addFront(unlink(node));
            return;
        }
        if (map.size() == capacity) map.remove(unlink(tail.prev).key); // evict LRU
        node = new Node(key, value);
        map.put(key, node);
        addFront(node);
    }
    private Node unlink(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
        return n;
    }
    private void addFront(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
}

True O(1) get/put with full control — the expected interview answer.

At a glance

Level	Approach	Time	Space
Brute Force	HashMap + Recency List (Linear Remove)	`O(capacity) per op`	`O(capacity)`
Better	LinkedHashMap (Access Order)	`O(1) avg`	`O(capacity)`
Optimal	HashMap + Hand-built Doubly Linked List	`O(1) avg`	`O(capacity)`

Common pitfalls

Evicting when put only updates an existing key.
Forgetting that get also refreshes recency.
Node without its key — eviction cannot clean the map.

Interview tips

Explain why each structure alone fails, then combine them.
Mention LinkedHashMap, then build it by hand.
Trace the capacity-2 example, drawing the list.

Pattern

Hash map + doubly linked list → O(1) lookup plus O(1) reordering (LRU, LFU, ordered sets).

My notes saved in this browser