LRU Cache

LeetCode 146 — LRU Cache

Problem

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

Implement the LRUCache class:

• LRUCache(int capacity) — initialises the cache with a positive size capacity.
• int get(int key) — returns the value of key if it exists, otherwise -1. Counts as a “use”.
• void put(int key, int value) — inserts or updates key. If inserting causes the cache to exceed capacity, evict the least recently used key first.

Both operations must run in O(1) average time.

Example

cache = 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 MRU, 2 is LRU
cache.put(3, 3)   // evicts key 2 (LRU), cache: {1=1, 3=3}
cache.get(2)      // returns -1 — 2 was evicted
cache.put(4, 4)   // evicts key 1 (LRU), cache: {4=4, 3=3}
cache.get(1)      // returns -1
cache.get(3)      // returns 3
cache.get(4)      // returns 4

Approach

Two structures working together give O(1) for both operations:

• HashMap<Integer, Node> — O(1) lookup of any node by key.
• Doubly linked list — tracks recency order. Head = LRU (eviction candidate), tail = MRU (most recently used).

Every get and put moves the touched node to the tail. Eviction always removes the head. The map keeps a direct pointer to each node so repositioning is O(1) — no search needed.

Complexity

• Time: O(1) for both get and put.
• Space: O(capacity).

Solution

class Node {
    Integer key;
    Integer value;
    Node prev = null;
    Node next = null;

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

class LRUCache {
    HashMap<Integer, Node> map;
    int capacity;
    Node head;  // LRU end — eviction candidate
    Node tail;  // MRU end — most recently used

    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        head = null;
        tail = null;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToTail(node);
            return;
        }
        if (map.size() == capacity) {
            map.remove(head.key);
            head = head.next;
            // MEMORY LEAK: head.prev still points to the evicted node, keeping it alive.
            // The evicted node was removed from the map but B.prev = A holds a reference,
            // so GC cannot collect A.
            //
            //   Before:  head → [A] ⇄ [B] ← tail
            //   After:         [A]   head → [B] ← tail
            //                   ↑___________________|
            //                  B.prev still points to evicted A
            //
            // FIX: null out the new head's back-pointer after advancing:
            //   if (head != null) head.prev = null;
            //   else tail = null;  // list is now empty (capacity==1 case)
        }
        Node node = new Node(key, value);
        map.put(key, node);
        makeTail(node);
        if (head == null) {
            head = node;
        }
    }

    private void makeTail(Node node) {
        node.prev = null;
        node.next = null;
        if (tail == null) {
            tail = node;
            head = node;
            return;
        }
        node.prev = tail;
        tail.next = node;
        tail = node;
    }

    // test : head and tail both null
    // test : move head to tail in single element list
    // test : move head to tail in a list
    // test : move tail to tail in a single element list
    // test : move tail to tail in a list
    // test : move center to tail
    private void moveToTail(Node node) {
        if (head == null && tail == null) {
            head = node;
            tail = node;
            return;
        }
        if (node == tail) return;
        if (node == head) {
            head = head.next;
            // MEMORY LEAK: same stale back-pointer problem as in put().
            // head.prev still points to node (the old head) after we advance.
            // FIX: head.prev = null;
            makeTail(node);
            return;
        }
        node.prev.next = node.next;
        node.next.prev = node.prev;
        makeTail(node);
    }
}

Memory leak — capacity=1 worst case

For a cache of size 1 the leak compounds with every eviction. When head.next is null, advancing head leaves tail pointing to the evicted node. makeTail then wires the new node’s .prev to that stale tail, creating a chain:

put(1): head = tail = [1]
put(2): evict [1] → head = null, tail still = [1]
        makeTail([2]): [2].prev = [1]  ← evicted [1] kept alive
put(3): evict [2] → head = null, tail still = [2]
        makeTail([3]): [3].prev = [2].prev = [1]  ← chain grows

Each new node’s .prev anchors the entire history of evicted nodes. The fix (nulling the pointer + resetting tail when the list empties) cuts that chain after every eviction.

Edge Cases

• put on an existing key — updates value and moves to MRU; eviction is not triggered.
• get on a missing key — returns -1, list is unchanged.
• capacity = 1 — every put of a new key evicts the only existing entry; the stale-tail variant of the leak applies here.