• 1 <= capacity <= 3000
• 0 <= key <= 10⁴
• 0 <= value <= 10⁵
• At most 2 × 10⁵ calls will be made to get and put

A cache is a small fast store with a fixed capacity. When it fills up and a new item arrives, something must be thrown out — and Least Recently Used is the eviction rule: kick out whatever hasn't been touched in the longest time. We need three things, all in O(1): get(key) returns a value (or -1) and marks that key as freshly used; put(key, value) inserts or updates and marks it fresh; and when we're over capacity, instantly find and drop the stalest key. The hard part is that "recently used" is an ordering that changes on every single access.

Think about what one structure alone gives you. A hash map finds any key in O(1) — but it has no notion of order, so it can't tell you which key is stalest without scanning all of them (O(N)). A list ordered by recency knows instantly who's stalest (it's at one end) — but finding a specific key inside it means a linear scan (O(N)). Either way, one of the two operations collapses to O(N). This is the same conflict you resolved in Insert Delete GetRandom: two operations demanding structures that pull apart. The resolution is the same — use both, and keep them in sync.

Keep the values in a doubly linked list ordered by recency: most-recently-used at the front, least-recently-used at the back. Alongside it, a hash map stores key → the node holding that key (not the value — the actual node object). Now a get is two O(1) steps: the map jumps straight to the node, and because it's a doubly linked list, that node knows both its neighbors, so we can splice it out and move it to the front without walking anything. Eviction is trivial: the stalest key is always the node just before the back.

Why doubly linked, not singly? To remove a node in O(1) you must rewire the node before it — and only a doubly linked list lets a node reach its predecessor directly via a prev pointer. A singly linked list would force an O(N) walk to find that predecessor, killing the whole point. (This is exactly the "hand me a node reference and I'll delete it cheaply" case flagged back in Design Linked List.)

Just like the dummy node in Design Linked List — but now two of them, a permanent head and tail that hold no data and never move. Real nodes always live between them. Because every real node is guaranteed a neighbor on both sides, splicing and inserting need no "is this the first/last node?" checks — the code is one uniform path.

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 = {}                     # key -> Node
        self.head, self.tail = Node(0, 0), Node(0, 0)   # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):              # unstitch from current position
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):           # insert right after head (most recent)
        first = self.head.next
        node.prev, node.next = self.head, first
        self.head.next = first.prev = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)                # pull it out...
        self._add_front(node)             # ...and mark it freshest
        return node.val

    def put(self, key, value):
        if key in self.map:               # update: refresh position
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:      # over capacity → evict stalest
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]         # map deletion needs the node's key

Both get and put are O(1): one map lookup plus a constant number of pointer rewires, and eviction reads a fixed position. Memory is O(capacity) for the map and the list together. The transferable move is the whole design: pair a hash map (find any item fast) with an ordered linked list (know the extreme fast), and let each node carry the key that ties them together. That template — fast lookup married to fast ordering — is the backbone of nearly every cache. The very next problem, LFU Cache, stretches it one dimension further: instead of a single recency list, a whole family of lists, one per access-frequency.