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

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<Integer, CacheItem>();
        head = null;
        tail = null;
    }

    public int get(int key) {
        CacheItem item = map.get(key);
        if (item == null) return -1;

        use(item);

        return item.val;
    }

    private void use(CacheItem item) {
        if (head == tail) return;

        if (item.prev != null) {
            item.prev.linkNext(item.next);
        } else {
            head = item.next;
        }

        tail.linkNext(item);
        item.next = null;
    }

    public void put(int key, int value) {
        if (map.size() == capacity) {
            evict();
        }
        CacheItem item = new CacheItem();
        item.val = value;
        map.put(key, item);

        if (tail != null ) {
            tail.linkNext(item);
        }
        else {
            head = item;
            tail = item;
        }
    }

    private void evict() {
        map.remove(head.val);

        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
        }
    }

    class CacheItem {
        public int val;

        public CacheItem next;

        public CacheItem prev;

        public void linkNext(CacheItem n) {
            next = n;
            n.prev = this;
        }
    }
}

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