LRU cache

實現 LRU 緩存，

支持 get(key), set(key, value) 操作，並且在 set 時把最近最不常用到的(least used)刪除

如果 set 時 key已經存在則覆蓋 value

這裡我們用雙向鏈表來連接 node，面試時問一下面試官要用什麼，也可以用 array

要注意的是，新進來的值就要是「hit」，所以新進來的值就要移到鏈表尾

當然， get 時如果 hit，就把這個 Node 擺到最後

public class LRUCache {

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

    public 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);

    /*
    * @param capacity: An integer
    */
    public LRUCache(int capacity) {
        // do intialization if necessary
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

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

        //remove current
        Node cur = hs.get(key);
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;

        move_to_tail(cur);
        return hs.get(key).value;
    }

    /*
     * @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) {   //hit
            hs.get(key).value = value;
            return;
        }

        //check if hs is at full capacity
        if (hs.size() == capacity) {
            hs.remove(head.next.key);    //注意是刪掉最不常用的，也就是 head.next!!!!
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node newNode = new Node(key, value);
        hs.put(key, newNode);
        move_to_tail(newNode);
    }

    //because cur is mostly used so move it to end
    private void move_to_tail(Node cur) {
        cur.prev = tail.prev;
        tail.prev = cur;
        cur.prev.next = cur;
        cur.next = tail;
    }
}