题目链接：
https://leetcode.cn/problems/lru-cache/solutions/259678/lruhuan-cun-ji-zhi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked
题目描述：
思路：
- 提到key-value一定有map；
- 要实现最近最少使用，最常见的一种思路就是使用flag，某一个数最近使用了，让其flag+1，这种方式比较麻烦，因为如果数据很多，每一个都需要flag，占用的空间变大；
- 另一种思路就是排序，如果这个数最近使用了，就让他排到前/后面，这就需要这些数可以随意的前后移动，可以使用链表；这里规定排在前面
- 如果超过容量，需要删除排在最后面的数并把新加的数放在最前面，
- 删除的操作比较麻烦，因为要找到要删除节点的前后节点，如果用单向链表，需要遍历才能找到他前面的，如果用双向链表就方便了
- 可以加入虚拟头和虚拟尾，这样就不需要对头结点和尾节点做特殊处理了
综上，需要使用map和双向链表完成
具体要怎么做：
数据存储方式：map里面存放key和node，所有的node组成一个双向链表，node是双向链表的节点，node里面存放他的前后节点，以及key、value这两个值，一般来说node里面只需要存放value就行，但是这里也要放key，因为后面会用到。
对于新增：要把key和node放入map里面；先看一下map里面有没有这个key，有的话就更新原有node的value值；没有的话就加到map里面，同时，node加入双向链表的最前面，新增后还要看链表的长度是否已经超过容量，超过的话就把最后一个node删除，注意也要把map里面的key删除，这个key在node里面有（这就是为什么node里面也要存key）。
对于获取：先看一下map里面有没有这个key，有的话返回这个node，并把这个node放到链表最前面
实现代码：
class LRUCache {class Dulinked{Dulinked prev;Dulinked next;int key;int value;public Dulinked(){};public Dulinked(int _key,int _value){key = _key;value = _value;}}private int size;private Map<Integer,Dulinked> table = new HashMap<Integer,Dulinked>();private int capacity;private Dulinked head,end;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new Dulinked();end = new Dulinked();head.next = end;end.prev = head;}public int get(int key) {Dulinked node = table.get(key);if(node == null){return -1;}moveToHead(node);return node.value;}public void put(int key, int value) {Dulinked node = table.get(key);if(node == null){Dulinked newNode = new Dulinked(key,value);table.put(key,newNode);addToHead(newNode);size++;if(size > capacity){Dulinked end = removeEnd();table.remove(end.key);size--;}}else{node.value = value;moveToHead(node);}}private void removeNode(Dulinked node){node.prev.next = node.next;node.next.prev = node.prev;}private void addToHead(Dulinked node){head.next.prev = node;node.next = head.next;node.prev = head;head.next = node;}private void moveToHead(Dulinked node){removeNode(node);addToHead(node);}private Dulinked removeEnd(){Dulinked res = end.prev;removeNode(res);return res;}}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/
