leetcode

commit fd4f7a82f5ff55496da9bea2c5b4e7fce736a2a6
parent 58adb3a8e7e008cb69e0a55e05b8831ec93b42dc
Author: Andrew Laack <andrew@laack.co>
Date:   Mon,  7 Jul 2025 09:52:56 -0500

Completed lru cache

Diffstat:
A
lru-cache/lru-cacheV1.py
 | 
56
++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 56 insertions(+), 0 deletions(-)
diff --git a/lru-cache/lru-cacheV1.py b/lru-cache/lru-cacheV1.py
@@ -0,0 +1,56 @@
+class Node:
+    def __init__(self, key, val):
+        self.key = key
+        self.val = val
+        self.left = None
+        self.right = None
+
+
+class LRUCache:
+
+    def __init__(self, capacity: int):
+        self.capacity = capacity
+        self.tracking = {}
+        self.head = None
+        self.tail = None
+
+    def _remove(self, node):
+        if node.left:
+            node.left.right = node.right
+        else:
+            self.head = node.right
+        if node.right:
+            node.right.left = node.left
+        else:
+            self.tail = node.left
+
+    def _append(self, node):
+        node.right = None
+        node.left = self.tail
+        if self.tail:
+            self.tail.right = node
+        else:
+            self.head = node
+        self.tail = node
+
+    def get(self, key: int) -> int:
+        if key in self.tracking:
+            node = self.tracking[key]
+            self._remove(node)
+            self._append(node)
+            return node.val
+        return -1
+
+    def put(self, key: int, value: int) -> None:
+        if key in self.tracking:
+            node = self.tracking[key]
+            node.val = value
+            self._remove(node)
+            self._append(node)
+        else:
+            if len(self.tracking) >= self.capacity:
+                del self.tracking[self.head.key]
+                self._remove(self.head)
+            node = Node(key, value)
+            self.tracking[key] = node
+            self._append(node)