LRU CacheStep 1 of 5

The Doubly Linked List

12345

Step 1 — The Doubly Linked List

An LRU cache needs to answer two questions in O(1): "what's the value for this key?" and "what was used least recently?". A hash map handles the first; a doubly linked list ordered by recency handles the second — most-recently-used at the front, least-recently-used at the back.

Start with the list plumbing. Two sentinel nodes (_head and _tail) bookend the list so you never touch None. Implement:

  • _remove(node) — unlink a node from wherever it is
  • _add_front(node) — insert a node right after _head (the most-recent position)

order() (given) walks the list front-to-back so you can check your work.

Hints
Starter code
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):
        self.capacity = capacity
        self._map = {}                 # key -> Node
        self._head = Node()            # sentinel: most-recent side
        self._tail = Node()            # sentinel: least-recent side
        self._head.next = self._tail
        self._tail.prev = self._head

    def _remove(self, node):
        """Unlink node from the list."""
        # TODO: connect node.prev directly to node.next (both directions)
        pass

    def _add_front(self, node):
        """Insert node just after _head (the most-recently-used spot)."""
        # TODO: splice node between _head and _head.next (fix all four links)
        pass

    def order(self):
        """Keys from most-recent (front) to least-recent (back)."""
        out = []
        n = self._head.next
        while n is not self._tail:
            out.append(n.key)
            n = n.next
        return out
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

OverviewNext step