lru-cacheV1.py (1463B)
1 class Node: 2 def __init__(self, key, val): 3 self.key = key 4 self.val = val 5 self.left = None 6 self.right = None 7 8 9 class LRUCache: 10 11 def __init__(self, capacity: int): 12 self.capacity = capacity 13 self.tracking = {} 14 self.head = None 15 self.tail = None 16 17 def _remove(self, node): 18 if node.left: 19 node.left.right = node.right 20 else: 21 self.head = node.right 22 if node.right: 23 node.right.left = node.left 24 else: 25 self.tail = node.left 26 27 def _append(self, node): 28 node.right = None 29 node.left = self.tail 30 if self.tail: 31 self.tail.right = node 32 else: 33 self.head = node 34 self.tail = node 35 36 def get(self, key: int) -> int: 37 if key in self.tracking: 38 node = self.tracking[key] 39 self._remove(node) 40 self._append(node) 41 return node.val 42 return -1 43 44 def put(self, key: int, value: int) -> None: 45 if key in self.tracking: 46 node = self.tracking[key] 47 node.val = value 48 self._remove(node) 49 self._append(node) 50 else: 51 if len(self.tracking) >= self.capacity: 52 del self.tracking[self.head.key] 53 self._remove(self.head) 54 node = Node(key, value) 55 self.tracking[key] = node 56 self._append(node)