Designing an LRU cache

A cache holds a limited number of items so repeated requests are fast. When it is full and a new item arrives, it must evict something. LRU (least recently used) evicts the item that has gone unused the longest, betting that recently used items will be used again soon.

To make get and put O(1), you need two structures working together. A hash map finds the node for a key in O(1). A doubly linked list keeps nodes in order of use: the most recent at the front, the least recent at the back. Because each node knows its prev and next, it can be unlinked from anywhere and moved to the front in O(1), and the back node is the eviction candidate.

Each node stores its key as well as its value, so that when the back node is evicted, you know which map entry to delete.

1. 1Keep capacity, a dict key -> node, and a doubly linked list with dummy head and tail sentinels. head.next is the most recently used node; tail.prev is the least recently used.
2. 2get(key): if the key is missing return -1. Otherwise look up the node, unlink it, insert it right after head (it is now the most recent) and return its value.
3. 3put(key, value): if the key exists, unlink its old node. Create a node, store it in the map and insert it after head.
4. 4If the map size now exceeds capacity, take tail.prev (the least recently used), unlink it, and delete its key from the map.
5. 5Unlink is two pointer updates (node.prev.next = node.next, node.next.prev = node.prev); insert after head is four. With sentinels there are never null checks.
6. 6Every operation does O(1) map work and O(1) pointer work, so get and put are O(1); space is O(capacity).

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                              # key -> Node
        self.head, self.tail = Node(), Node()      # dummies; head.next is most recent
        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.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
        node = self.map[key]
        self._remove(node)                         # mark as most recently used
        self._add_front(node)
        return node.val
    def put(self, key, value):
        if key in self.map:
            self._remove(self.map.pop(key))
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:               # evict least recently used
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

Dummy head and tail mean every real node always has neighbours, so _remove and _add_front never check for None. The node stores its key so eviction can delete the map entry. get and put are O(1) time; space is O(capacity).

Cost: get and put O(1) time; O(capacity) space, with two pointers plus a map entry per item.