public class LRU<K, V> {

    Node head;
    Node tail;
    Map<K, Node<K, V>> hm = new HashMap<>();
    int capacity;
    int size;
    public LRU(int cap) {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
        this.capacity = cap;
    }

    public V get(K k) {
        Node<K, V> node = hm.get(k);
        if (node == null) return null;
        this.moveToTail(node);
        return node.val;
    }

    public void put(K k, V v) {
        Node node = hm.get(k);
        if (node == null) {
            node = new Node(k, v);
            hm.put(k, node);
            this.addTail(node);
            size++;
            if (size > capacity) this.removeHead();
        } else {
            node.val = v;
            this.moveToTail(node);
        }
    }

    private void moveToTail(Node node) {
        Node before = node.prev;
        Node after = node.next;
        before.next = after;
        after.prev = before;
        this.addTail(node);
    }

    private void addTail(Node node) {
        Node pre = tail.prev;
        node.next = tail;
        node.prev = pre;
        pre.next = node;
        tail.prev = node;
    }

    private void removeHead() {
        Node node = head.next;
        Node nx = node.next;
        node.next = null;
        node.prev = null;
        head.next = nx;
        nx.prev = head;
        hm.remove(node.key);
    }

    @Override
    public String toString() {
        return hm.toString();
    }

    static class Node<K, V> {
        K key;
        V val;
        Node prev;
        Node next;
        public Node() {

        }

        public Node(K k, V v) {
            this.key = k;
            this.val = v;
        }

        @Override
        public String toString() {
            return "<" + key.toString() + ", " + val.toString() + ">";
        }
    }
}