# LRU Cache Design — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/lru-cache

> Combine a hash map with a doubly linked list to get O(1) get/put with least-recently-used eviction.

## 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.

```python
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.

**Quiz:** Why does LRU cache need a doubly linked list instead of a singly linked list?

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

*Answer:* It allows O(1) removal of a node given only a pointer to it. With a prev pointer, a node can unlink itself in O(1); a singly linked list would need O(n) to find the previous node.