import java.util.HashMap;
import java.util.Map;

public class Cache<K, V> {
    private static int MAX = 100;

    private static class Node<V> {
        public V value;
        public Node<V> prev;
        public Node<V> next;

        public Node(V v, Node<V> p, Node<V> n) {
            this.value = v;
            this.next = n;
            this.prev = p;
        }

        public static <T> Node<T> of(T v, Node<T> p, Node<T> n) {
            return new Node<T>(v, p, n);
        }
    }

    private int capacity;

    private Map<K, Node<V>> cache;

    private Node<V> head, tail;

    public Cache() {
        this(MAX);
    }

    public Cache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    public V get(K key) {
        Node<V> node = cache.get(key);
        if( null == node) {
            return null;
        }

        // Now need to move the node to the head of the list
        removeNode(node);
        addNode(node);

        return node.value;
    }

    public void put(K k, V v) {
        // form new node
        Node<V> node = Node.of(v, null, null);

        // check if key is present
        if( cache.containsKey(k) ) {
            // just update the value
            cache.get(k).value = v;
            return;
        }

        // key is not present. need to insert into cache
        if( capacity == cache.size()) {
            // remove the tail node
            removeNode(tail);
        }

        // add node to head of list
        addNode(node);
        cache.put(k, node);
    }

    private void addNode(Node<V> node) {
        if( null == node) {
            return;
        }

        // now add node to the beginning of the list
        node.next = head;
        node.prev = null;
        head.prev = node;
        head = node;
        if( null == tail) {
            tail = node;
        }
    }

    private void removeNode(Node<V> node) {
        if( null == node ) {
            return;
        }

        if( head == tail) { // there is only the node
            // reset the list
            head = tail = null;
        } else if( head == node) { // check if head
            // just advance the head
            head = node.next;
        } else if( tail == node ) { // check if tail
            // point tail to prev
            tail = node.prev;
        } else { // node in middle.
            if( null != node.prev ) {
                node.prev.next = node.next;
            }

            if( null != node.next ) {
                node.next.prev = node.prev;
            }
        }
    }
}