LRU Cache Design

Two structures, one job

An LRU cache needs O(1) get, O(1) put, and O(1) eviction of the least-recently-used item. A hash map alone gives fast lookup but no ordering; a linked list alone gives ordering but slow lookup. Combining them gives both.

Doubly linked list + hash map

The hash map stores key -> node for O(1) lookup. The doubly linked list keeps nodes in use-order: move a node to the front (most recent) on access, and evict from the back (least recent) when full.

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head = Node(0, 0)   # dummy most-recent end
        self.tail = Node(0, 0)   # dummy least-recent end
        self.head.next, self.tail.prev = self.tail, self.head

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

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

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, val):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, val)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

Python shortcut

In interviews you build it by hand, but in real Python code collections.OrderedDict already does this — move_to_end() on access and popitem(last=False) to evict the oldest.

Quick check

Test your understanding of the design.

Quick check: Why does LRU cache need a doubly linked list instead of a singly linked list?

• It uses less memory
• It allows O(1) removal of a node given only a pointer to it
• It sorts keys alphabetically
• Hash maps require doubly linked lists