hashmap key: key, val: node node : key, value, prev, next;

class LRUCache {

    class Node {
        Node prev;
        Node next;
        int v;
        int k;

        Node(int k, int v) {
            this.k = k;
            this.v= v;
        }

    }

    Map<Integer, Node> map;
    Node dummy = new Node(-1, -1);
    final int capacity;

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

    public int get(int key) {
        if (map.containsKey(key)) {
            moveFront(map.get(key));
            return map.get(key).v;
        }
        return -1;
    }

    public void put(int key, int value) {
        var node = map.get(key);
        if (node != null) {
            moveFront(map.get(key));
            node.v = value;
        } else {
            Node newNode = new Node(key, value);
            if (map.size() >= capacity) {
                var last = dummy.prev;
                remove(last);
                map.remove(last.k);
            }
            map.put(key, newNode);
            addFirst(newNode);
        }
    }

    private void moveFront(Node node) {
        remove(node);
        addFirst(node);
    }

    private void addFirst(Node node) {
        node.prev = dummy;
        node.next = dummy.next;
        dummy.next.prev = node;
        dummy.next = node;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

/**
 * 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);
 */