146 - LRU Cache

Problem

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

• LRUCache(int capacity) initialises the cache with positive size capacity
• int get(int key) returns the value of the key if it exists, otherwise -1
• void put(int key, int value) updates the value of the key if it exists, otherwise adds the key-value pair. If the number of keys exceeds capacity, evict the least recently used key.

Both get and put must run in O(1) average time complexity.

["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

Output: [null,null,null,1,null,-1,null,-1,3,4]

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 10^4, 0 <= value <= 10^5
• At most 2 * 10^5 calls to get and put

Approach

Three things have to be O(1): look up a key, mark a key as just-used, and find the least recently used key to evict. No single structure does all three.

• A hash map gives O(1) lookup but has no notion of order, so it cannot tell you what to evict.
• A list keeps order but lookup is O(n).

So use both, pointing at the same nodes. A doubly linked list holds the entries in recency order — most recently used at the front, least recently used at the back — and the hash map maps each key to the node itself, not to the value.

map:  {1: •, 2: •, 3: •}
           |    |    |
           v    v    v
head <-> [3] <-> [2] <-> [1] <-> tail
         MRU              LRU

The map jumps you to any node in O(1), and once you are holding a node, the list unlinks and relinks it in O(1). Neither half works alone; together they cover everything.

Why doubly linked. Removing a node from the middle means rewiring the node before it. In a singly linked list you would have to walk from the head to find it, which is O(n) — the same wall that shows up in 237. The prev pointer is the entire reason promotion and eviction are constant time.

Why not a vector. Moving an element to the front shifts everything after it, O(n).

Why the node stores the key. On eviction you have the node and need to erase its entry from the map, which means you need its key. A node holding only the value would leave you searching the map for a matching pointer — O(n), and the whole design collapses.

Hand-rolled

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

    int cap;
    unordered_map<int, Node*> map;
    Node *head, *tail;                    // sentinels, never hold real data

    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) : cap(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        Node* n = it->second;
        remove(n);
        addFront(n);
        return n->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() == cap) {
            Node* lru = tail->prev;
            remove(lru);
            map.erase(lru->key);
            delete lru;
        }
        Node* n = new Node(key, value);
        addFront(n);
        map[key] = n;
    }
};

The two sentinels are the dummy-node trick from 24 and 86, applied at both ends at once. Because head and tail always exist, every real node is guaranteed a non-null prev and next, so remove is two unconditional writes and addFront is four — no null checks, no branch for an empty cache, no branch for the single-entry case where the node being promoted is also the one being evicted.

Without sentinels, remove needs if (n->prev) ... else head = n->next, and the same for the tail, and every one of those branches is a place to get it wrong.

With std::list

std::list is a doubly linked list, and splice is unlink-and-relink. Store the iterator in the map and the implementation collapses:

class LRUCache {
    int cap;
    list<pair<int,int>> lst;                               // {key, value}, front = MRU
    unordered_map<int, list<pair<int,int>>::iterator> map; // key -> its node
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        lst.splice(lst.begin(), lst, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->second = value;
            lst.splice(lst.begin(), lst, it->second);
            return;
        }
        if ((int)map.size() == cap) {
            map.erase(lst.back().first);
            lst.pop_back();
        }
        lst.emplace_front(key, value);
        map[key] = lst.begin();
    }
};

lst.splice(lst.begin(), lst, it->second) is the three-argument overload: move one element, from lst, to the front of lst. It rewires pointers — no copy, no allocation, O(1).

The property that makes this legal is that splice does not invalidate iterators. The iterator sitting in the map keeps pointing at the same element after it moves, so a get never touches the map beyond the initial lookup, and it->second->second on the line after the splice still reads the right value. A vector would invalidate on every insertion and the stored iterators would be garbage — this is a list-specific guarantee, not a general one.

The sentinels vanish because list maintains its own internal end node, so begin() and back() are always valid to name.

Complexity

	time	space
get	O(1)	—
put	O(1) amortised (hash map)	—
total		O(capacity)