134. lru cache

// get, move the node to tail
// set add the node to tail, delete head
public class  {
    private class ListNode {
        int key;
        int val;
        ListNode prev;
        ListNode next;
        public ListNode(int key, int val) {
            this.key = key;// need key and val
            this.val = val;
        }
    }


    private HashMap<Integer, ListNode> map; // key, node
    private int capacity;
    private ListNode head;
    private ListNode tail;
    /*
    * @param capacity: An integer
    */public (int capacity) {
        // do intialization if necessary
        this.capacity = capacity;
        map = new HashMap<Integer, ListNode>();
        head = new ListNode(-1, -1);//建立挡板可以避免很多没有头尾的情况！！！
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    /*
     * @param key: An integer
     * @return: An integer
     */
    public int get(int key) {
        // write your code here
        if (!map.containsKey(key)) {
            return -1;
        }
        ListNode curt = map.get(key);

        moveToTail(curt);
        return curt.val;

    }
    private void moveToTail(ListNode node) {

        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = tail.prev;
        node.next = tail;
        node.prev.next = node;
        tail.prev = node;

    }

    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void set(int key, int value) {
        // write your code here
        if (get(key) != -1) { // 如果重复，移到后面，直接return
            map.get(key).val = value;
            return;
        }

        ListNode curt = new ListNode(key, value);
        if (map.size() >= capacity) {
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        map.put(key, curt);
        curt.prev = tail.prev;
        curt.next = tail;
        curt.prev.next = curt;
        tail.prev = curt;


    }
}