LRU

LRU，Least Recently Used，最少最近使用，淘汰策略是最久没用的
想象有一摞书，用的时候抽出来，放在最上面
淘汰的时候把最下面的移除
整一个双向链表，每次都淘汰最后一个，插入的时候插入到头（哨兵后面）

class LRUCache {
    private static class Node{
        int key, value;
        Node pre, next;
        Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    private Node dummy = new Node(0, 0);  // 哨兵节点
    // 存储 key 和 Node 的关系，方便检索
    private Map<Integer, Node> key2Node = new HashMap(); 
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.pre = dummy;
        dummy.next = dummy;
    }
    // 移除某一个节点（抽出一本书）
    private void remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    // 把节点添加到链表头（把一本书放到最上面）
    private void pushFront(Node node){
        node.pre = dummy;
        node.next = dummy.next;
        node.pre.next = node;
        node.next.pre = node;
    }

    private Node getNode(int key){
        if (!key2Node.containsKey(key)) return null;

        Node node = key2Node.get(key);  // 如果有的话，最近使用过
        // 要把它放到最上面，也就是先移除再插入
        remove(node);
        pushFront(node);
        return node;
    }
    
    public int get(int key) {
        Node node = getNode(key);
        return node == null ? -1 : node.value;
    }
    
    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null){  // 有这本书
            node.value = value;  // 更新 value
            return;
        }
        node = new Node(key, value);  // 新书
        key2Node.put(key, node);
        pushFront(node);  // 放到最上面
        if (key2Node.size() > capacity){  // 淘汰策略
            Node backNode = dummy.pre;
            key2Node.remove(backNode.key);
            remove(backNode);  // 移除最后一个
        }
    }
}