Designing an LRU Cache

An LRU (Least Recently Used) cache evicts the element that has gone unused the longest when it is full. The idea is simple: something used recently will likely be used again. The practical requirement is that both get(key) and put(key, value) run in O(1). For the ready-made function cache see memoization and lru_cache; here we build the cache itself.

Why one structure is not enough

• A dict finds by key in O(1) but does not know which element is "the oldest".
• A list keeps the order but finding a key in it is O(n).

The solution: a dict + a doubly linked list (doubly linked list).

• dict: key → list node.
• List: the head side holds the "most recent", the tail side the "least recent" element.
• get: finds the node and moves it to the front of the list.
• put: puts the node at the front and drops the tail node if the capacity is exceeded.

The list must be doubly linked: to remove a node from the middle in O(1) we need its prev pointer. Sentinel nodes (head, tail) remove edge cases: the list never meets a "null pointer" (the dummy idea).

Implementation

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

class LRUCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev