An LRU Cache is a data structure that removes the least recently used items first when it reaches its capacity. To achieve $O(1)$ time complexity for both get and put operations, we combine a Hash Map (for fast lookups) with a Doubly Linked List (to maintain usage order).

The Logic

1. Hash Map: Stores keys and pointers to their corresponding nodes in the linked list.
2. Doubly Linked List:
3. Head (Most Recent): Newly added or accessed items are moved here.
4. Tail (Least Recent): Items at this end are evicted when capacity is exceeded.

The Code

```python
class Node:
def init(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None

class LRUCache:
def init(self, capacity: int):
self.cap = capacity
self.cache = {} # Map key to node

    # Dummy nodes for boundary ease
    self.head = Node(0, 0)
    self.tail = Node(0, 0)
    self.head.next = self.tail
    self.tail.prev = self.head

def _remove(self, node):
    """Remove an existing node from the linked list."""
    prev_node = node.prev
    next_node = node.next
    prev_node.next = next_node
    next_node.prev = prev_node

def _add(self, node):
    """Add new node right after the head (most recent)."""
    temp = self.head.next
    self.head.next = node
    node.prev = self.head
    node.next = temp
    temp.prev = node

def get(self, key: int) -> int:
    if key in self.cache:
        node = self.cache[key]
        self._remove(node)
        self._add(node)
        return node.value
    return -1

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        self._remove(self.cache[key])

    new_node = Node(key, value)
    self.cache[key] = new_node
    self._add(new_node)

    if len(self.cache) > self.cap:
        # Evict the least recently used (node before tail)
        lru = self.tail.prev
        self._remove(lru)
        del self.cache[lru.key]

Example Usage:

lru = LRUCache(2)

lru.put(1, 1)

lru.put(2, 2)

print(lru.get(1)) # returns 1

lru.put(3, 3) # evicts key 2

print(lru.get(2)) # returns -1 (not found)