LRU Cache (Hash Map + Doubly Linked List)

What is an LRU cache?

A cache keeps a small number of items close at hand: web pages in a browser, database rows in memory, results of expensive function calls. When it is full and a new item arrives, something must go. LRU (least recently used) evicts the item that has gone unused for the longest time, betting that recently used items will be used again soon. The same idea appears in page replacement and in CPU caches.

The challenge is to make both operations O(1):

• get(key): return the value (or −1 if absent) and mark the key as just used.
• put(key, value): insert or update, and if the cache is over capacity, evict the least recently used key.

Two structures working together

HEAD ⇄ [MRU] ⇄ … ⇄ [LRU] ⇄ TAIL          map: key → its node in the list

HEAD and TAIL are sentinel (dummy) nodes, so a real node always has neighbours on both sides and no special cases are needed.

• get(key): look up the node in the map; unlink it; push it to the front; return its value.
• put(key, value): if the key exists, update and move to the front. Otherwise, if the cache is full, remove tail.prev (the LRU node) from the list and from the map; then create a node, add it to the map and push it to the front.

Why doubly linked?

Moving a node to the front means unlinking it from the middle: its previous node must point past it. A doubly linked node knows its previous node, so that is O(1). In a singly linked list you would have to walk from the head to find the previous node, which is O(n).

The classic example (capacity 2)

The gets return 1, −1, −1, 3, 4.

Variations

Code

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

class LRUCache:
    """Hash map (key -> node) + doubly linked list (most recent at the front)."""
    def __init__(self, capacity):
        self.capacity, self.map = capacity, {}
        self.head, self.tail = Node(), Node()          # sentinels: no special cases at the ends
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):                           # O(1): the node knows both neighbours
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1                                  # miss
        node = self.map[key]
        self._unlink(node)                             # hit: it is now the most recently used
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:                            # update: change the value, move to the front
            node = self.map[key]
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.capacity:             # full: evict the least recently used (back)
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

    def keys_by_recency(self):
        out, n = [], self.head.next
        while n is not self.tail:
            out.append(n.key)
            n = n.next
        return out

cache = LRUCache(2)
results = []
for op in [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)]:
    if op[0] == 'put':
        cache.put(op[1], op[2])
    else:
        results.append(cache.get(op[1]))
print(results, cache.keys_by_recency())
# [1, -1, -1, 3, 4] [4, 3]

In real Python code, collections.OrderedDict (with move_to_end and popitem(last=False)) does the same in a few lines, and the decorator functools.lru_cache(maxsize=…) caches function results with LRU eviction. The class above was checked against an OrderedDict version on 300 random sequences of operations.

Common mistakes

• Forgetting to update the order on get. A read counts as a use; the key must move to the front.
• Evicting from the wrong end. New and recently used items go to the front, so the victim is at the back (tail.prev).
• Removing the node from the list but not from the map (or the other way round). Both must stay in sync.
• Evicting before checking whether the key already exists. Updating an existing key must never evict anything.
• Using a singly linked list. Then unlinking a middle node is O(n).