# LRU Cache Design — डेटा स्ट्रक्चर और एल्गोरिदम

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

> O(1) get/put और least-recently-used eviction के लिए hash map को doubly linked list के साथ मिलाएँ।

## दो structures, एक काम

LRU cache को `O(1)` **get**, `O(1)` **put**, और least-recently-used item का `O(1)` eviction चाहिए। अकेला hash map तेज़ lookup देता है पर कोई क्रम नहीं; अकेली linked list क्रम देती है पर धीमी lookup। दोनों मिलाने से दोनों मिलते हैं।

## Doubly linked list + hash map

Hash map `key -> node` को `O(1)` lookup के लिए रखता है। Doubly linked list nodes को उपयोग-क्रम में रखती है: access पर node को आगे (सबसे हाल का) ले जाएँ, और भरने पर पीछे (सबसे पुराना) से हटाएँ।

```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 का शॉर्टकट

Interviews में इसे हाथ से बनाया जाता है, पर असली Python code में `collections.OrderedDict` यह पहले से करता है — access पर `move_to_end()` और सबसे पुराना हटाने के लिए `popitem(last=False)`।

## त्वरित जांच

Design की समझ परखें।

**Quiz:** LRU cache को singly linked list के बजाय doubly linked list की ज़रूरत क्यों है?

- [ ] यह कम memory इस्तेमाल करती है
- [x] यह किसी node को केवल उसका pointer देकर O(1) में हटाने देती है
- [ ] यह keys को वर्णानुक्रम में क्रमबद्ध करती है
- [ ] Hash maps को doubly linked lists चाहिए ही होती हैं

*Answer:* यह किसी node को केवल उसका pointer देकर O(1) में हटाने देती है. prev pointer के साथ, एक node खुद को O(1) में unlink कर सकता है; singly linked list में पिछला node खोजने में O(n) लगेगा।