LRU Cache

摘要：因为是所有两个操作的时间复杂度都必须是。因为使用线性的数据结构，并且表示操作的先后顺序，这样的结构就是链表。我们发现，无论是还是都有两个简单操作组成，从链表中移除，放到链表头部。如果从尾部移除，将不会指向任何点。

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.

这题需要我们设计一个cache, 有get和set两个操作。因为是cache, 所有两个操作的时间复杂度都必须是O(1)。
get(key) -- O(1) 很明显，我们需要用一个hashmap来实现O(1)的操作。
set(key, value) -- O(1) 这里有两种情况，key没出现过，就直接加在head。这里出现一个关键词head。
因为使用线性的数据结构，并且表示操作的先后顺序，这样的结构就是链表。是单链表还是双链表？下面我们模拟一下：
capacity = 3
set(1, 100)
set(2, 200)
set(3, 300)
get(2)
如果是单链表，简单表示如下：
1 -> 2 -> 3 -> null
我们可以得到2并放在头部。但是这里用的单链表，我们无法知道2的前面是什么，2前面的所有点都会脱离整体。所以需要一个双链表。
1 <=> 3 <=> 2 <=> null
我们继续操作，set(4, 400)，发现已经达到LRU的容量，需要移除，这时候发现我们需要一个尾部来告诉我们需要移除哪个点。
我们发现，无论是get(key)还是set(key, value)都有两个简单操作组成，从链表中移除，放到链表头部。
可以定义两个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可以简化代码。

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的就是错误的点，即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){
        // 加到头和前一个点的中间
        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 如果从尾部移除，将不会指向任何点。
        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);
 */