public class LRUCache {

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

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


    }

    //this part is only for delcare new object!!!!!!
    //no logic should be defined here, logic should be declared at the constructer!!!

    private int capacity;
    private HashMap<Integer,Node> hs= new HashMap<Integer,Node>();
    private Node head = new Node(-1,-1);
    private Node tail = new Node(-1,-1);


    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev= head;

    }

    public int get(int key) {
        if (!hs.containsKey(key)) {
            return -1;
        }

        //if hs contains key, then we need to update the key.value's postion, 
        //append it to the end of the doubly linked list
        Node curNode = hs.get(key);
        curNode.prev.next = curNode.next;
        curNode.next.prev = curNode.prev;

        moveToEnd(curNode);
        return hs.get(key).value;

    }

    public void put(int key, int value) {
        //if the LRU cache contains the key, update the key's value with this value, 
        //REMEMBER to stop the program immediately, just return, since you do not need to do anything further!
        if (get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        //later on, if the hs.size() bigger than capacity, we need to first, 
        //get the least recent used ele from link list, remove it from hashmap and linked list and append the new key and value node to the end of our linked list
        if (hs.size()>=capacity) {
            hs.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }


        //for the initial state
        Node curNode = new Node(key,value);
        hs.put(key,curNode);
        moveToEnd(curNode);

    }

    private void moveToEnd(Node thisNode) {
        thisNode.prev = tail.prev;
        tail.prev = thisNode;
        thisNode.prev.next = thisNode;
        thisNode.next = tail;

    }
}

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