LRU

class Node:
    def __init__(self, key=0, val=0, previous=None, next=None):
        self.key = key
        self.val = val
        self.previous = previous
        self.next = next

class LRUCache:

    def __init__(self, capacity: int):
        self.n = 0
        self.capacity = capacity
        self.mapa = {}
        self.left = Node()
        self.right = Node()
        self.left.next = self.right
        self.right.previous = self.left

    def get(self, key: int) -> int:
        if key in self.mapa:
            node = self.mapa[key]
            if node.previous != self.right.previous:
                previous = node.previous
                next = node.next
                previous.next = next
                next.previous = previous
                last = self.right.previous
                last.next = node
                node.next = self.right
                node.previous = last
                self.right.previous = node
            return self.mapa[key].val
        else:
            return -1
        
    def put(self, key: int, value: int) -> None:
        new_node = Node(key, value)
        if self.n == self.capacity and key not in self.mapa:
            node = self.left.next
            if self.left.next == node and self.right.previous == node:
                self.left.next = new_node
                self.right.previous = new_node
                new_node.previous = self.left
                new_node.next = self.right
            else:
                left.next = node.next
                node.next.previous = self.left
                self.mapa[key] = new_node
            del self.mapa[node.key]
        else:
            if key not in self.mapa:
                self.n += 1
                self.mapa[key] = new_node
                if self.left.next == self.right.previous:
                    self.left.next = new_node
                    self.right.previous = new_node
                    new_node.previous = self.left
                    new_node.next = self.right
                else:
                    last = self.right.previous
                    last.next = new_node
                    new_node.next = self.right
                    new_node.previous = last
                    self.right.previous = new_node
            else:
                node = self.mapa[key]
                if self.left.next != node and self.right.previous != node:
                    previous = node.previous
                    next = node.next
                    previous.next = next
                    next.previous = previous
                    last = self.right.previous
                    last.next = node
                    node.next = self.right
                    node.previous = last
                    self.right.previous = node
                elif self.left.next == node:
                    self.left.next = node.next
                    node.next.previous = self.left
                    last = self.right.previous
                    last.next = node
                    node.next = self.right
                    self.right.previous = node