题目链接146.LRU缓存
请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。
实现LRUCache类：
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存
int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。
void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value
。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。
函数get和put必须以O(1)的平均时间复杂度运行。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10⁵
最多调用 2 * 10⁵次get和put

选用的数据结构

本题我们选用双向链表来存储数据，用哈希表来当缓存

为什么是双向链表？队列行不行？普通链表行不行？

队列为什么不行

题目中说，这个数据结构要能一端插入，一端能够在超过指定容量后删除。一端插入一端删除，而双端队列看似刚好满足这个条件。但是题目要求get和put的时间复杂度是
O(1)，如果我们要修改的数据在队列中部，双端队列随机访问的时间复杂度就会来到O(n)，显然不满足条件。

为什么是双端链表

单向链表在头插的复杂度为O(1)，但是在中间删除时的复杂度来到了O(n)，因为删除时必须得遍历到要删除节点的前一个节点。
双向链表很好的解决了上面的缺点，每个节点都存了prev和next指针，只要知道要删除的节点，就能直接删除，将复杂度降到了O(1)。
可以增加虚拟的头尾节点，方便对两端进行操作。

为什么要用哈希表

题目要求实现复杂度为O(1)的查询操作，哈希表随机访问的复杂度为O(1)，所以利用哈希表来充当查询的缓存。

如何实现LRUCache

class LRUCache {
	//双向链表结构
    class Node {
        int key, value;
        Node next, prev;
        Node() {
        }
        Node(int k, int v) {
            this.key = k;
            this.value = v;
        }
    }
    //哈希表实现缓存
    private Map<Integer, Node> cache = new HashMap<>();
    //链表大小
    private int size;
    //指定的容量
    private int capacity;
    //虚拟头尾
    private Node head, tail;
    //初始化
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

  
    //实现缓存查询。
    public int get(int key) {
        //先查询缓存
        Node node = cache.get(key);
        //缓存里无
        if (node == null) {
            return -1;
        }
        //查询后将查询的节点放到头部
        moveToHead(node);
        return node.value;
    }
  
    public void put(int key, int value) {
        //先查询缓存
        Node node = cache.get(key);
        //新建一个节点
        if (node == null) {
            Node newNode = new Node(key, value);
            //放入哈希表/缓存
            cache.put(key, newNode);
            //头部插入
            addToHead(newNode);
            size++;
            //超出容量时，删除末尾
            if (size > capacity) {
	        //要删除的尾部节点
                Node tail = removeTail();
                //根据key删除缓存
                cache.remove(tail.key);
                size--;
            }
        } else {
            //更新值
            node.value = value;
            //移动到最前
            moveToHead(node);
        }
    }

  
	//移动节点到头部
    private void moveToHead(Node node) {
	//先删除节点
        removeNode(node);
        //头插法插入节点
        addToHead(node);
    }

  
    //删除节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    //头插法具体实现
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    //移除尾部节点
    private Node removeTail() {
	//虚拟尾部的前一个节点(res是真实尾部节点)
        Node res = tail.prev;
        //删除尾部节点
        removeNode(res);
        //返回要删除的节点信息，因为缓存要通过res.key删除
        return res;
    }
}