<aside> 💡 LRU 缓存机制可以通过哈希表+双向链表实现，用一个哈希表和一个双向链表维护所有在缓存中的键值对。

• 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。 • 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

这样以来，首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1)O(1) 的时间内完成 get 或者 put 操作。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/ 来源：力扣（LeetCode）

</aside>

class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
        }

        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    // 最大容量
    private int capacity;
    // 当前容量
    private int size;
    // 伪节点
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 删除node
     */
    private void removeNode(DLinkedNode node) {
        // 把前节点的next指向后节点
        node.prev.next = node.next;
        // 把后节点的prev指向前节点
        node.next.prev = node.prev;
        // 把当前节点的prev和next置空
        node.prev = null;
        node.next = null;
    }

    /**
     * 把node添加到头部
     */
    private void addToHead(DLinkedNode node) {
        // 把node prev 与 next 挂到双链表上
        node.prev = head;
        node.next = head.next;
        // 修改head的next为node
        this.head.next = node;
        // 修改后节点的prev为node
        node.next.prev = node;
    }

    /**
     * 把node移动到头部
     */
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 删除链表最后一个节点
     */
    private DLinkedNode removeTail() {
        DLinkedNode node = tail.prev;
        if (node == head) {
            return null;
        }
        removeNode(node);
        return node;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果存在, 则移动到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        // 如果存在, 则修改value并移动到头部
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }
        // 如果不存在, 则新增node
        DLinkedNode newNode = new DLinkedNode(key, value);
        // 添加进hash表
        cache.put(key, newNode);
        // 添加进链表
        addToHead(newNode);
        size++;
        // 如果超出容量, 则删除尾部节点
        if (size > capacity) {
            DLinkedNode tail = removeTail();
            if (tail == null) {
                return;
            }
            // 删除hash表中node
            cache.remove(tail.key);
            size--;
        }
    }
}