0146-lru-cache.py

classNode:
def__init__(self, key, val):
self.key, self.val=key, val
self.prev=self.next=None


classLRUCache:
def__init__(self, capacity: int):
self.cap=capacity
self.cache= {} # map key to node

self.left, self.right=Node(0, 0), Node(0, 0)
self.left.next, self.right.prev=self.right, self.left

# remove node from list
defremove(self, node):
prev, nxt=node.prev, node.next
prev.next, nxt.prev=nxt, prev

# insert node at right
definsert(self, node):
prev, nxt=self.right.prev, self.right
prev.next=nxt.prev=node
node.next, node.prev=nxt, prev

defget(self, key: int) ->int:
ifkeyinself.cache:
self.remove(self.cache[key])
self.insert(self.cache[key])
returnself.cache[key].val
return-1

defput(self, key: int, value: int) ->None:
ifkeyinself.cache:
self.remove(self.cache[key])
self.cache[key] =Node(key, value)
self.insert(self.cache[key])

iflen(self.cache) >self.cap:
# remove from the list and delete the LRU from hashmap
lru=self.left.next
self.remove(lru)
delself.cache[lru.key]