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

A cache needs to be two things: fast at finding data and strict about throwing it away. The challenge of an LRU (Least Recently Used) cache is that we need to perform three operations in constant time: finding an existing item, updating its "freshness," and evicting the oldest item when full.

If we use a Hash Map, we get O(1) lookups, but we have no way of knowing which item is the "oldest" without scanning everything. If we use an Array or a Linked List, we can maintain order, but finding a specific key in the middle requires a linear scan.

# Naive approach using a simple list
cache = [] # List of [key, value]
def get(key):
    for i, (k, v) in enumerate(cache):
        if k == key:
            # Move to front (MRU)
            item = cache.pop(i)
            cache.insert(0, item)
            return v
    return -1 # O(N) scan

To get the best of both worlds, we combine them. We use a Hash Map to store key -> node pointers and a Doubly Linked List (DLL) to store the actual data.
- The Map gives us instant O(1) access to any node in the DLL.
- The DLL allows us to "splice" a node out of its current position and move it to the front in O(1) time, because we have direct access to its prev and next neighbors.

To avoid messy "null" checks (e.g., when the cache is empty or has one item), we use Dummy Head and Dummy Tail nodes.
- Head.next always points to the Most Recently Used (MRU) item.
- Tail.prev always points to the Least Recently Used (LRU) item.
These sentinels never move, acting as permanent anchors for our "line" of data.

Every time a key is accessed (get) or updated (put), we perform "surgery" on the DLL:
1. Remove: We disconnect the node from its neighbors (node.prev.next = node.next).
2. Promote: We insert it immediately after the Dummy Head.
3. Evict: If we exceed capacity, we remove the node at Tail.prev and delete its key from the Map.

def _remove(node):
    # Surgery: stitch the neighbors together
    p, n = node.prev, node.next
    p.next, n.prev = n, p

def _add_to_head(node):
    # Insert between Dummy Head and the old first node
    first = head.next
    head.next = node
    node.prev = head
    node.next = first
    first.prev = node

def get(key):
    if key not in cache_map: return -1
    node = cache_map[key]
    _remove(node)      # Take it out
    _add_to_head(node) # Put it at the front
    return node.val