力扣——146.LRU缓存

题目链接：

https://leetcode.cn/problems/lru-cache/solutions/259678/lruhuan-cun-ji-zhi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked

题目描述：

思路：

1. 提到key-value一定有map；
2. 要实现最近最少使用，最常见的一种思路就是使用flag，某一个数最近使用了，让其flag+1，这种方式比较麻烦，因为如果数据很多，每一个都需要flag，占用的空间变大；
3. 另一种思路就是排序，如果这个数最近使用了，就让他排到前/后面，这就需要这些数可以随意的前后移动，可以使用链表；这里规定排在前面
4. 如果超过容量，需要删除排在最后面的数并把新加的数放在最前面，
5. 删除的操作比较麻烦，因为要找到要删除节点的前后节点，如果用单向链表，需要遍历才能找到他前面的，如果用双向链表就方便了
6. 可以加入虚拟头和虚拟尾，这样就不需要对头结点和尾节点做特殊处理了

综上，需要使用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);
 */