LRU Cache

mediumLinked List114 stepsJava · Python · C++

A cache with O(1) get and put that evicts the least recently used key when full. A hash map finds nodes by key; a doubly linked list keeps them in usage order, most recent at the front. Every access moves the node to the front; eviction removes the node before the tail.

▶ Watch the animated trace

Traced input: LRUCache(2): put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4) → [null, null, null, 1, null, -1, null, -1, 3, 4]. Original problem: neetcode.io/problems/lru-cache

Complexity

BestO(1)

AverageO(1)

WorstO(1)

SpaceO(capacity)

Map lookups and list relinking are both O(1).

Key idea

Map: key → node, for O(1) lookup.
Doubly linked list: O(1) removal from the middle and insertion at the front.
Dummy head and tail nodes remove all null checks.
On put, if the key is new and the cache is full, evict tail.prev.

Common mistakes

Forgetting to update recency on get.
Evicting before checking whether the key already exists.
Not removing the evicted key from the map.
LinkedHashMap(cap, 0.75f, true) with removeEldestEntry is a valid shortcut; know both.

Solution

Java

class LRUCache {
    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);

    LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        remove(node);
        addFront(node);
        return node.val;
    }

    void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.val = value;
            remove(node);
            addFront(node);
            return;
        }
        if (map.size() == capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        node = new Node(key, value);
        map.put(key, node);
        addFront(node);
    }

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

    private void addFront(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
}

Python

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node:
            node.val = value
            self._remove(node)
            self._add_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

    def _remove(self, n: Node) -> None:
        n.prev.next, n.next.prev = n.next, n.prev

    def _add_front(self, n: Node) -> None:
        n.next, n.prev = self.head.next, self.head
        self.head.next.prev = n
        self.head.next = n

C++

class LRUCache {
    struct Node {
        int key, val;
        Node *prev = nullptr, *next = nullptr;
        Node(int k, int v) : key(k), val(v) {}
    };

    int capacity;
    unordered_map<int, Node*> map;
    Node *head = new Node(0, 0), *tail = new Node(0, 0);

    void remove(Node* n) {
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }

    void addFront(Node* n) {
        n->next = head->next;
        n->prev = head;
        head->next->prev = n;
        head->next = n;
    }

public:
    LRUCache(int capacity) : capacity(capacity) {
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) {
            return -1;
        }
        remove(it->second);
        addFront(it->second);
        return it->second->val;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->val = value;
            remove(it->second);
            addFront(it->second);
            return;
        }
        if ((int)map.size() == capacity) {
            Node* lru = tail->prev;
            remove(lru);
            map.erase(lru->key);
            delete lru;
        }
        Node* node = new Node(key, value);
        map[key] = node;
        addFront(node);
    }
};

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Update an existing key Updating 1 makes it most recent, so 2 is evicted.	`LRUCache(2): put(1,1), put(2,2), put(1,10), put(3,3), get(1), get(2)`	`[null, null, null, null, null, 10, -1]`
Capacity 1 Each new key evicts the previous one.	`LRUCache(1): put(1,1), put(2,2), get(1), get(2)`	`[null, null, null, -1, 2]`
Get a missing key Missing keys return -1 without changing anything.	`LRUCache(2): get(5)`	`[null, -1]`