[Python] Implementing LFU cache in python, issue with inserting

I know the way I am going about implementing this cache may not be the best, but I genuinley can not understand why this isnt working, I have tried stepping through my code and to how I understand it, it should work. The issue seems to lie in the insert function where the node is getting pushed to the beginning of the DLL (between self.left which will always point to the LFU node) and between the previous LFU node. For example, after adding print statements I saw that after 1 push, the DLL looked like 0 <-> 1 <-> 0 (expected). But after pushing 2, it looks like 0 <-> 2 <-> 0 (expected to be 0 <-> 2 <-> 1 <-> 0. Sorry if this is a bad question or a really simple issue, I just can not figure it out even after trying using ChatGPT.

Hers my code:

class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.reads = 1
self.next = None
self.prev = None
class LFUCache:

def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.left, self.right = Node(0,0), Node(0,0)
self.left.next = self.right
self.right.prev = self.left

def remove(self, node):
# only happens at beginning (self.left.next)
prev, nxt = self.left, node.next
prev.next = nxt
nxt.prev = prev

def insert(self, node):
prev, nxt = self.left, self.left.next
node.prev = prev
node.next = nxt
nxt.prev = node
self.left.next = node

def swapNodes(self, node1, node2):
node1Prev = node1.prev
node2Next = node2.next
# make node1Prev.next = node2
node1Prev.next = node2
# make node2.prev = node1.prev and make node2.next = node1
node2.prev = node1Prev
node2.next = node1
# make node1.next = node2.next, make node1.prev = node2
node1.next = node2Next
node1.prev = node2
# make node2Next.prev = node1
node2Next.prev = node1

def get(self, key: int) -> int:
if key in self.cache:
self.cache[key].reads += 1
if self.cache[key].next != self.right and self.cache[key].reads > self.cache[key].next.reads:
self.swapNodes(self.cache[key], self.cache[key].next)
return self.cache[key].value
return -1

def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache[key].reads += 1
self.cache[key].value = value
if self.cache[key].reads > self.cache[key].next.reads and self.cache[key].next != self.right:
self.swapNodes(self.cache[key], self.cache[key].next)
else:
node = Node(key,value)
self.cache[key] = node
if len(self.cache) == self.cap:
lru = self.left.next
self.remove(lru)
del self.cache[lru.key]
self.insert(node)
# print(f"{self.left.next.value},{self.right.prev.value}")


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Continue reading...