12.YA

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

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        self.lru = LinkedList()
        self.mru = LinkedList()
        self.lru.next = self.mru
        self.mru.prev = self.lru

    def add_node(self, node):
        self.mru.prev.next = node
        node.next = self.mru
        node.prev = self.mru.prev
        self.mru.prev = node

    def delete_node(self, node):
        prev_node = node.prev
        next_node = node.next

        prev_node.next = next_node
        next_node.prev = prev_node

        node.next = None
        node.prev = None


    def get(self, key: int) -> int:
        if key in self.hashmap:
            # update mru
            node = self.hashmap[key]
            self.delete_node(node)
            self.add_node(node)
            return self.hashmap[key].val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        # Case 1: update
        if key in self.hashmap:
            node = self.hashmap[key]
            node.val = value
            self.delete_node(node)
            self.add_node(node)
        # Case 2: add, update mru, no deletion
        elif len(self.hashmap) < self.capacity:
            node = LinkedList(key = key, val = value)
            self.hashmap[key] = node
            self.add_node(node)
        # Case 3: add, update mru, delete, update lru
        else:
            node = LinkedList(key = key, val = value)
            self.hashmap[key] = node
            self.add_node(node)

            node_to_del = self.lru.next
            del self.hashmap[node_to_del.key]
            self.delete_node(node_to_del)




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