lru

class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None



class LRUCache:

    def __init__(self, capacity: int):
        self.dict = {}
        self.capacity = capacity
        self.head = ListNode(None, None)
        self.tail = ListNode(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head


    def get(self, key: int) -> int:
        if key not in self.dict:
            return -1
        node = self.dict[key]
        value = node.val
        self.remove(node)
        self.add(node)
        return value



    def put(self, key: int, value: int) -> None:
        if key in self.dict:
            old_node = self.dict[key]
            self.remove(old_node)

        node = ListNode(key, value)
        self.dict[key] = node
        self.add(node)
        if len(self.dict) > self.capacity:
            node_to_delete = self.head.next
            self.remove(node_to_delete)
            del self.dict[node_to_delete.key]

    def add(self, node):
        """
        h a  b 'c' t
        """
        prev_node = self.tail.prev
        node.prev = prev_node
        node.next = self.tail
        self.tail.prev = node
        prev_node.next = node




    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev




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