146. LRU Cache

class LRUCache {

    private static class Node {
        private final int key; // 淘汰元素时使用
        private int val;
        private Node prev;
        private Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node dummyHead;
    private final Node dummyTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.dummyHead = new Node(-1, -1);
        this.dummyTail = new Node(-1, -1);
        this.dummyHead.next = this.dummyTail;
        this.dummyTail.prev = this.dummyHead;
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }

        moveToHead(node);
        return node.val;
    }

    private void removeNode(Node node) {
        Node prev = node.prev, next = node.next;
        prev.next = next;
        next.prev = prev;
        node.prev = null;
        node.next = null;
    }

    private void addToHead(Node node) {
        Node head = dummyHead.next;
        dummyHead.next = node;
        head.prev = node;
        node.prev = dummyHead;
        node.next = head;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        Node node = cache.get(key);
        if (node != null) {
            node.val = value;
            moveToHead(node);
            return;
        }

        node = new Node(key, value);
        cache.put(key, node);
        addToHead(node);

        if (cache.size() > capacity) {
            Node tail = dummyTail.prev;
            cache.remove(tail.key);
            removeNode(tail);
        }
    }
}

注意是双向链表，移动节点时需要注意修改前后两个节点的指针，注意 map 与链表需要同步修改。

References

146. LRU Cache
面试题 16.25. LRU 缓存
剑指 Offer II 031. 最近最少使用缓存