DSA LRU Cache

The problem: the cache spec

An LRU cache is a fixed-size store that drops its least recently used entry when space runs out. LRU stands for least recently used. The store supports two operations, get and put.

A get returns the value stored under a key, or -1 when the key is absent. A put stores a value under a key, updating it when the key already exists. Reading or writing an entry makes it the most recently used entry.

script = [
    ("put(1, 10)", None),
    ("put(2, 20)", None),
    ("get(1)", 10),
    ("put(3, 30) evicts 2", None),
    ("get(2)", -1),
    ("put(4, 40) evicts 1", None),
    ("get(1)", -1),
    ("get(3)", 30),
    ("get(4)", 40),
]
print("capacity: 2")
for action, expected in script:
    if expected is None:
        print(action)
    else:
        print(action, "expected:", expected)

The capacity here is 2, so the store holds at most two entries. The third put must evict something. The script says what it evicts, and later sections run the script in full.

Intuition: keep entries in a list, freshest first

The first design keeps the entries in one plain list. The front of the list is the most recently used end. A get scans the list for its key, then moves that entry to the front.

A put on a full list drops the last entry. The design is correct. Its cost is the scan, and the scan grows with the capacity.

entries = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50)]
target = 5
scanned = 0
found = None
for key, value in entries:
    scanned += 1
    if key == target:
        found = value
        break
print("value:", found, "entries scanned:", scanned, "of", len(entries))

The wanted entry sat at the back, so the scan paid full price. A busier cache repeats that price on many operations. The real design removes the scan.

Brute force: the naive list cache, counted

The naive design is the intuition, written as a class. Every get and put scans the list by key. A counter records each entry inspected.

class ListCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.entries = []
        self.scans = 0

    def _find(self, key):
        for i in range(len(self.entries)):
            self.scans += 1
            if self.entries[i][0] == key:
                return i
        return -1

    def get(self, key):
        self.scans = 0
        i = self._find(key)
        if i == -1:
            return -1
        pair = self.entries.pop(i)
        self.entries.insert(0, pair)
        return pair[1]

    def put(self, key, value):
        self.scans = 0
        i = self._find(key)
        if i != -1:
            self.entries.pop(i)
        self.entries.insert(0, (key, value))
        if len(self.entries) > self.capacity:
            self.entries.pop()

    def order(self):
        return [key for key, value in self.entries]

cache = ListCache(2)
cache.put(1, 10)
print("put(1, 10) -> cache", cache.order(), "| scanned", cache.scans)
cache.put(2, 20)
print("put(2, 20) -> cache", cache.order(), "| scanned", cache.scans)
print("get(1) =", cache.get(1), "-> cache", cache.order(), "| scanned", cache.scans)
cache.put(3, 30)
print("put(3, 30) -> cache", cache.order(), "| scanned", cache.scans)
print("get(2) =", cache.get(2), "-> cache", cache.order(), "| scanned", cache.scans)

The script answers match the spec at capacity 2. The scans stay small only because the capacity is small. At capacity 100 a back entry costs about 100 inspections per operation.

The optimal solution: a dict plus a doubly linked list

The real design pairs a dict with a doubly linked list, where the dict finds each entry's node at once and the list keeps the nodes in recency order. That one pairing is the whole design.

A doubly linked list node links to a previous node and a next node. Dummy head and tail nodes, called sentinels, frame the list and never hold data. The front node is the most recently used entry, and the node before the tail sentinel is the eviction target.

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.steps = 0

    def _link_front(self, node):
        node.prev = self.head
        self.steps += 1
        node.next = self.head.next
        self.steps += 1
        self.head.next.prev = node
        self.steps += 1
        self.head.next = node
        self.steps += 1

    def _unlink(self, node):
        node.prev.next = node.next
        self.steps += 1
        node.next.prev = node.prev
        self.steps += 1

    def _touch(self, node):
        self._unlink(node)
        self._link_front(node)

    def get(self, key):
        self.steps = 0
        node = self.store.get(key)
        self.steps += 1
        if node is None:
            return -1
        self._touch(node)
        return node.value

    def put(self, key, value):
        self.steps = 0
        node = self.store.get(key)
        self.steps += 1
        if node is not None:
            node.value = value
            self._touch(node)
            return
        node = Node(key, value)
        self.store[key] = node
        self.steps += 1
        self._link_front(node)
        if len(self.store) > self.capacity:
            victim = self.tail.prev
            self._unlink(victim)
            del self.store[victim.key]
            self.steps += 1

    def order(self):
        keys = []
        node = self.head.next
        while node is not self.tail:
            keys.append(node.key)
            node = node.next
        return keys

cache = LRUCache(2)
def show(action, result=None):
    if result is None:
        print(action, "-> cache", cache.order(), "| steps", cache.steps)
    else:
        print(action, "=", result, "-> cache", cache.order(), "| steps", cache.steps)

cache.put(1, 10)
show("put(1, 10)")
cache.put(2, 20)
show("put(2, 20)")
show("get(1)", cache.get(1))
cache.put(3, 30)
show("put(3, 30) evicts 2")
show("get(2)", cache.get(2))
cache.put(4, 40)
show("put(4, 40) evicts 1")
show("get(1)", cache.get(1))
show("get(3)", cache.get(3))
show("get(4)", cache.get(4))

Every line matches the script from the first section. The get for 1 returns 10 and moves 1 to the front. That move is why put(3, 30) evicts 2 instead of 1.

Walkthrough: the script, step by step

The walk reruns the script up to the second get(1). Each row states the recency order after the operation and the steps it took.

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.steps = 0

    def _link_front(self, node):
        node.prev = self.head
        self.steps += 1
        node.next = self.head.next
        self.steps += 1
        self.head.next.prev = node
        self.steps += 1
        self.head.next = node
        self.steps += 1

    def _unlink(self, node):
        node.prev.next = node.next
        self.steps += 1
        node.next.prev = node.prev
        self.steps += 1

    def _touch(self, node):
        self._unlink(node)
        self._link_front(node)

    def get(self, key):
        self.steps = 0
        node = self.store.get(key)
        self.steps += 1
        if node is None:
            return -1
        self._touch(node)
        return node.value

    def put(self, key, value):
        self.steps = 0
        node = self.store.get(key)
        self.steps += 1
        if node is not None:
            node.value = value
            self._touch(node)
            return
        node = Node(key, value)
        self.store[key] = node
        self.steps += 1
        self._link_front(node)
        if len(self.store) > self.capacity:
            victim = self.tail.prev
            self._unlink(victim)
            del self.store[victim.key]
            self.steps += 1

    def order(self):
        keys = []
        node = self.head.next
        while node is not self.tail:
            keys.append(node.key)
            node = node.next
        return keys

cache = LRUCache(2)
def show(action, result=None):
    if result is None:
        print(action, "-> cache", cache.order(), "| steps", cache.steps)
    else:
        print(action, "=", result, "-> cache", cache.order(), "| steps", cache.steps)

cache.put(1, 10)
show("put(1, 10)")
cache.put(2, 20)
show("put(2, 20)")
show("get(1)", cache.get(1))
cache.put(3, 30)
show("put(3, 30) evicts 2")
show("get(2)", cache.get(2))
cache.put(4, 40)
show("put(4, 40) evicts 1")
show("get(1)", cache.get(1))
print("next eviction would take:", cache.order()[-1])

After get(1) the order is 1 then 2, so 2 is least recent. The next put evicts exactly that entry. Recency order, read front to back, is the whole state the design maintains.

Complexity

Each get and put does one dict access and a fixed set of pointer assignments, so its time is O(1), a constant count at any capacity. The store holds at most one node per key up to the capacity, so its space is O(capacity).

A step in this article means one dict access or one pointer assignment, as in the source lesson. The counted steps stay in single digits in the script output above.

class ListCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.entries = []
        self.scans = 0

    def get_last(self):
        target = self.entries[-1][0]
        self.scans = 0
        for key, value in self.entries:
            self.scans += 1
            if key == target:
                return value

for cap in [10, 50, 100]:
    cache = ListCache(cap)
    for key in range(1, cap + 1):
        cache.entries.append((key, key * 10))
    cache.get_last()
    print("capacity", cap, "- naive scans for the back entry:", cache.scans, " real design steps for a get: 7")

The naive scan grows with the capacity. The real step count does not move. That flat count is what O(1) means in this design, shown in numbers.

Edge cases and pitfalls

A get for a missing key returns -1 and changes nothing. A put on an existing key updates its value and its recency, and it evicts nothing. A capacity 1 cache evicts on every new key.

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.steps = 0

    def _link_front(self, node):
        node.prev = self.head
        self.steps += 1
        node.next = self.head.next
        self.steps += 1
        self.head.next.prev = node
        self.steps += 1
        self.head.next = node
        self.steps += 1

    def _unlink(self, node):
        node.prev.next = node.next
        self.steps += 1
        node.next.prev = node.prev
        self.steps += 1

    def _touch(self, node):
        self._unlink(node)
        self._link_front(node)

    def get(self, key):
        self.steps = 0
        node = self.store.get(key)
        self.steps += 1
        if node is None:
            return -1
        self._touch(node)
        return node.value

    def put(self, key, value):
        self.steps = 0
        node = self.store.get(key)
        self.steps += 1
        if node is not None:
            node.value = value
            self._touch(node)
            return
        node = Node(key, value)
        self.store[key] = node
        self.steps += 1
        self._link_front(node)
        if len(self.store) > self.capacity:
            victim = self.tail.prev
            self._unlink(victim)
            del self.store[victim.key]
            self.steps += 1

    def order(self):
        keys = []
        node = self.head.next
        while node is not self.tail:
            keys.append(node.key)
            node = node.next
        return keys

cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
print("missing get:", cache.get(9), "order:", cache.order())
cache.put(1, 111)
print("after update put(1, 111): order", cache.order(), "size", len(cache.store))
print("updated value:", cache.get(1))
tiny = LRUCache(1)
tiny.put(1, 10)
tiny.put(2, 20)
print("capacity 1 holds:", tiny.order(), "get(1):", tiny.get(1), "get(2):", tiny.get(2))
cache.put(3, 30)
print("after put(3, 30): order", cache.order())

The pitfall is forgetting to move a node on a hit. A get that leaves recency untouched evicts entries that were just read. The update row shows the other common slip, growing the store on a repeated key instead of updating in place.