Will the Guru

class Node {
    int key;
    int value;
    Node prev;
    Node next;

    Node (int key, int value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    Map<Integer, Node> map;
    int capacity;
    Node head;
    Node tail;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.capacity = capacity;
        initialize();
    }

    private void initialize() {
        this.head = new Node(-1, -1); // Dummy Node
        this.tail = new Node(-1, -1); // Dummy Node
        
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            // Get node from map
            Node node = map.get(key);
            
            // Move node to the last
            removeNode(node);
            addLast(key, node);

            return node.value;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // Move node to the last
            Node node = map.get(key);
            removeNode(node);
            addLast(key, new Node(key, value));
        } else {
            if (map.keySet().size() == capacity) {
                // Remove head
                removeHead();
            } 
            // Add node to the last
            addLast(key, new Node(key, value));
        }
    }

    private void removeHead() {
        Node realHead = head.next;
        
        map.remove(realHead.key);
        head.next = realHead.next;
        realHead.next.prev = head;
    }

    private void removeNode(Node node) {
        map.remove(node.key);

        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addLast(int key, Node node) {
        map.put(key, node);

        Node realTail = tail.prev;
        realTail.next = node;
        node.prev = realTail;
        
        node.next = tail;
        tail.prev = node;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */