Optimal Hash Map + Doubly Linked List Approach:
- Combine a Hash Map (O(1) key-to-node lookup) with a Doubly Linked List (O(1) node removal and insertion at head/tail).
class DNode:
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {} # key -> DNode
self.head, self.tail = DNode(), DNode()
self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, node: DNode):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node: DNode):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_front(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = DNode(key, value)
self._add_to_front(node)
self.cache[key] = node
if len(self.cache) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
Complexity: O(1) for both get and put. Space O(capacity).