Difficulty Implementing LRU Cache with Python - Cache Misses Where There Shouldn't Be
I'm having trouble with my implementation of an LRU (Least Recently Used) Cache in Python using a dictionary and a doubly linked list. I've set up the doubly linked list to maintain the order of usage, but I'm working with unexpected cache misses when trying to access keys that should be present. Here's a simplified version of my 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.capacity = capacity self.cache = {} # key: Node self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head def _remove(self, node: Node): prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _add_to_head(self, node: Node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def get(self, key: int) -> int: if key in self.cache: node = self.cache[key] self._remove(node) self._add_to_head(node) return node.value return -1 def put(self, key: int, value: int): if key in self.cache: self._remove(self.cache[key]) node = Node(key, value) self.cache[key] = node self._add_to_head(node) if len(self.cache) > self.capacity: # Remove LRU from the tail lru = self.tail.prev self._remove(lru) del self.cache[lru.key] # Example usage cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) print(cache.get(1)) # returns 1 cache.put(3, 3) # evicts key 2 print(cache.get(2)) # returns -1 (not found) cache.put(4, 4) # evicts key 1 print(cache.get(1)) # returns -1 (not found) print(cache.get(3)) # returns 3 print(cache.get(4)) # returns 4 ``` In this example, the `put` and `get` methods work as expected, but I notice that I occasionally get `-1` for keys that I just put into the cache. My intuition tells me that the cache misses might be occurring due to an behavior in either removing the least recently used item or maybe something wrong with how I'm managing the order of nodes. I've debugged thoroughly, but I need to seem to pinpoint the scenario. Could there be a flaw in how I'm handling the linked list operations? Any insights would be greatly appreciated!