One post tagged with "Doubly-Linked List"

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