实现 LRU

class LRUCache {
 
/**
 * Node 中需要包含 key 和 value
 */
    class Node {
        int key;
        int val;
        Node prev;
        Node next;
 
        Node (int key, int val) {
            this.key = key;
            this.val = val;
        }
 
        Node (int key, int val, Node prev, Node next) {
            this.key = key;
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
 
    Map<Integer, Node> map;
    Node sentinel;
    Node tail;
    // 需要用于判断map是否已经满了
    int capacity;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(this.capacity);
        sentinel = new Node(-1, -1);
        tail = new Node(-1, -1, sentinel, sentinel);
        sentinel.prev = tail;
        sentinel.next = tail;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node res = map.get(key);
        moveToHead(res);
        return res.val;
    }
	// map存在，更新值之后移动到开头
	// 不存在，先判断是否要移除最后一个节点（map和链表都需要移除）
	// 之后再创建新节点，加入链表
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node res = map.get(key);
            res.val = value;
            moveToHead(res);
        } else { // put a new pair
            if (map.size() == this.capacity) {
                Node toRemove = tail.prev;
                map.remove(toRemove.key);
                removeNode(toRemove);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);
        }
    }
	// 注意该方法的节点一定是已经存在在链表中了
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
	// 新创建的节点，加入到链表开头
    private void addToHead(Node node) {
        node.next = sentinel.next;
        sentinel.next.prev = node;
        sentinel.next = node;
        node.prev = sentinel;
    }
	// 将一个节点从链表中去除
    private void removeNode(Node node) {
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
        node.next = null;
        node.prev = null;
    }
}