LRU Cache

How it works

Many languages provide a built-in ordered map / dictionary that:

• Stores key–value pairs
• Keeps track of the order in which keys were inserted or recently updated

This is perfect for an LRU cache:

• When we access a key (get or put), we mark it as most recently used by moving it to the "end" of the order.
• When the cache exceeds capacity, we remove the key that is at the front of the order (the least recently used).

So the ordered map itself handles:

• Fast lookups (like a normal hash map)
• Fast updates of usage order (moving keys to the end)
• Fast removal of the least recently used key (from the front)

This gives a clean and concise LRU implementation using library support.

Steps

1. Initialization

   • Create an ordered map cache.
   • Store the maximum capacity cap.

2. get(key)

   • If key is not in cache, return -1.
   • Otherwise:
     • Move key to the "most recent" position in the ordered map.
     • Return the associated value.

3. put(key, value)

   • If key is already in cache:
     • Update its value.
     • Move key to the "most recent" position.
   • If key is not in cache:
     • Insert (key, value) into cache at the "most recent" position.
   • If the size of cache is now greater than cap:
     • Remove the least recently used key (the one at the "oldest" position in the ordered map).

This uses the built-in ordered map to achieve LRU behavior with O(1) average time for both get and put.

Complexity

• Time complexity: O(1) for each put() and get() operation.
• Space complexity: O(n)

Things to watch for

Forgetting to Update on Get Operations

A critical LRU requirement is that get() operations also update recency. Many implementations correctly update order on put() but forget that accessing a key via get() should also move it to the most recently used position. This breaks the LRU invariant and causes wrong evictions.

Incorrect Doubly Linked List Pointer Updates

When implementing the doubly linked list approach, pointer manipulation errors are common. When removing a node, you must update both prev.next and next.prev. When inserting, you must update four pointers: the new node's prev and next, plus the adjacent nodes' pointers. Missing any of these updates corrupts the list structure.

Not Storing Keys in List Nodes

When evicting the least recently used item, you need to remove it from both the linked list and the hash map. If your list nodes only store values (not keys), you cannot efficiently find and remove the corresponding hash map entry. Always store the key in each list node to enable O(1) eviction.

from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.cap = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value

        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

class LRUCache {
private:
    unordered_map<int, pair<int, list<int>::iterator>> cache;
    list<int> order;
    int capacity;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1;
        order.erase(cache[key].second);
        order.push_back(key);
        cache[key].second = --order.end();
        return cache[key].first;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            order.erase(cache[key].second);
        } else if (cache.size() == capacity) {
            int lru = order.front();
            order.pop_front();
            cache.erase(lru);
        }
        order.push_back(key);
        cache[key] = {value, --order.end()};
    }
};