摘要：因?yàn)槭撬袃蓚€(gè)操作的時(shí)間復(fù)雜度都必須是。因?yàn)槭褂镁€性的數(shù)據(jù)結(jié)構(gòu)，并且表示操作的先后順序，這樣的結(jié)構(gòu)就是鏈表。我們發(fā)現(xiàn)，無(wú)論是還是都有兩個(gè)簡(jiǎn)單操作組成，從鏈表中移除，放到鏈表頭部。如果從尾部移除，將不會(huì)指向任何點(diǎn)。

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

這題需要我們?cè)O(shè)計(jì)一個(gè)cache, 有g(shù)et和set兩個(gè)操作。因?yàn)槭莄ache, 所有兩個(gè)操作的時(shí)間復(fù)雜度都必須是O(1)。
get(key) -- O(1) 很明顯，我們需要用一個(gè)hashmap來(lái)實(shí)現(xiàn)O(1)的操作。
set(key, value) -- O(1) 這里有兩種情況，key沒(méi)出現(xiàn)過(guò)，就直接加在head。這里出現(xiàn)一個(gè)關(guān)鍵詞head。
因?yàn)槭褂镁€性的數(shù)據(jù)結(jié)構(gòu)，并且表示操作的先后順序，這樣的結(jié)構(gòu)就是鏈表。是單鏈表還是雙鏈表？下面我們模擬一下：
capacity = 3
set(1, 100)
set(2, 200)
set(3, 300)
get(2)
如果是單鏈表，簡(jiǎn)單表示如下：
1 -> 2 -> 3 -> null
我們可以得到2并放在頭部。但是這里用的單鏈表，我們無(wú)法知道2的前面是什么，2前面的所有點(diǎn)都會(huì)脫離整體。所以需要一個(gè)雙鏈表。
1 <=> 3 <=> 2 <=> null
我們繼續(xù)操作，set(4, 400)，發(fā)現(xiàn)已經(jīng)達(dá)到LRU的容量，需要移除，這時(shí)候發(fā)現(xiàn)我們需要一個(gè)尾部來(lái)告訴我們需要移除哪個(gè)點(diǎn)。
我們發(fā)現(xiàn)，無(wú)論是get(key)還是set(key, value)都有兩個(gè)簡(jiǎn)單操作組成，從鏈表中移除，放到鏈表頭部。
可以定義兩個(gè)helper function： remove(node), setHead(node)。

代碼如下，帶注釋：

public class LRUCache {
    class Node{
        int key;
        int value;
        Node pre;       // point to tail direction
        Node next;      // point to head direction
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    
    int capacity;
    Map map = new HashMap<>();
    Node tail = null;
    Node head = null;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(map.containsKey(key)){       // remove from LRU and put it to head of LRU
            Node n = map.get(key);
            remove(n);
            setHead(n);
            return n.value;
        }
        return -1;
    }
    
    public void set(int key, int value) {
        if(map.containsKey(key)){           // change node value, remove from LRU and put it to head of LRU
            Node old = map.get(key);
            old.value = value;
            remove(old);
            setHead(old);
        } else {
            Node newNode = new Node(key, value);
            if(capacity == map.size()){     //  remove the tail
                map.remove(tail.key);
                remove(tail);
            }
            setHead(newNode);               // set newNode to head
            map.put(key, newNode);
        }
    }
    
    public void remove(Node n){
        if(n.pre != null) {         // change pre node connection
            n.pre.next = n.next;
        } else {                    // check if it is the tail
            tail = n.next;
        }
        
        if(n.next != null) {        // change next node connection
            n.next.pre = n.pre;
        } else {                    // check if it is the head
            head = n.pre;
        }
    }
    
    public void setHead(Node n){
        n.pre = head;
        n.next = null;
        
        if(head != null) {  // check head exist or Not ?
            head.next = n;
        }
        
        head = n;
        if(tail == null){    // empty LRU, intitailize tail node
            tail = head;
        }
    }
}

使用dummyEnd 和dummyHead可以簡(jiǎn)化代碼。

public class LRUCache {
    
    int capacity;
    Map map;
    Node dummyEnd;
    Node dummyHead;
    int count;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap();
        dummyEnd = new Node(0,0);
        dummyHead = new Node(0,0);
        dummyEnd.next = dummyHead;
        dummyHead.pre = dummyEnd;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if(node == null) {
            return -1;
        } else {
            remove(node);
            putToHead(node);
            return node.val;
        }
    }
    
    public void put(int key, int value) {
        Node oldNode = map.get(key);
        if(oldNode == null) {
            ++count;
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            putToHead(newNode);
            
            if(count > capacity){
                // 從LRU移除
                // 第一次在這里debug了好久，要先取出nextNode, 不然map里remove的就是錯(cuò)誤的點(diǎn)，即dummy.next.next。
                Node nextNode = dummyEnd.next;
                remove(nextNode);
                // 從map移除
                map.remove(nextNode.key);
                --count;
            }
            
        } else {
            // 改變值，先移除，再放入頭部
            oldNode.val = value;
            remove(oldNode);
            putToHead(oldNode);
        }
    }
    
    public void putToHead(Node node){
        // 加到頭和前一個(gè)點(diǎn)的中間
        Node preNode = dummyHead.pre;
        preNode.next = node;
        node.pre = preNode;
        dummyHead.pre = node;
        node.next = dummyHead;
    }
    
    public void remove(Node node){
        // 移除。
        node.next.pre = node.pre;
        node.pre.next = node.next;
        // node 如果從尾部移除，將不會(huì)指向任何點(diǎn)。
        node.pre = null;
        node.next = null;
    }
    
    class Node{
        int key, val;
        Node pre, next;
        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
}

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