Skip to main content

146. LRU Cache - LeetCode

ยท One min read
from typing import Optional


class Node:
def __init__(
self,
value=0,
key=0, # for eviction
left: Optional['Node'] = None,
right: Optional['Node'] = None,
):
self.key = key
self.value = value
self.left = left
self.right = right

def append(self, node: 'Node'):
node.left = self
node.right = self.right
if self.right:
self.right.left = node
self.right = node

def isolate(self):
if self.left:
self.left.right = self.right
if self.right:
self.right.left = self.left


class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dict: dict[int, Node] = {}
self.fresh = Node()
self.stale = Node()
self.fresh.right = self.stale
self.stale.left = self.fresh
self.amount = 0

def get(self, key: int) -> int:
node = self.dict.get(key, Node(-1))
if key in self.dict:
node.isolate()
self.fresh.append(node)
return node.value

def put(self, key: int, value: int) -> None:
if key in self.dict:
self.dict[key].isolate()
else:
if self.amount == self.capacity:
evicted = self.stale.left
if evicted:
evicted.isolate()
self.dict.pop(evicted.key)
else:
self.amount += 1
node = self.dict.setdefault(key, Node(key=key))
self.fresh.append(node)
node.value = value