146.LRU

链接：https://leetcode.cn/problems/lru-cache/description/

这道题其实很长，但是理解了还是很好写的。

首先，要确定如何存储这些值。大小确定，每次调用就要调用的值移动到最前面（即要维护顺序）。每次可以根据key去获取值。根据这两条，确定使用链表来维护。

但是这里没有直接可用的链表，于是自己定义：

public static class Node{
        int key;
        int value;
        Node prev;
        Node next;
        Node(int k,int v){
            key = k;
            value = v;
        }
    }

这里除了正常的节点外，还定义了前驱节点，在把节点移动到头部时，我们需要把前面节点的下一个节点改成当前节点的下一个节点，所以需要一个prev。

之后，我们要通过key查找值，这里就在类里定义一个哈希表，这样好维护也好查找

    private final Map<Integer,Node> map = new HashMap<>();

其次，这里还规定了LRU的大小，我们用capacity记录

    private final int capacity;

除了上面的这两个定义，还需要一个虚拟头节点，以便对头节点进行操作，并且还能通过dummy.prev找到尾部节点，便于淘汰删除。（这里我不是很理解为什么它指向了尾部节点，好像虚拟节点前驱默认？？？）

    private final Node dummy = new Node(0,0);

之后，依照函数初始化

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }

初始化大小以及虚拟头节点的位置

之后要注意的是两个点

1.获取节点之后要把它移动到最前面

这个过程很简单，但是涉及两个额外的方法

    private void remove(Node node){
        //把节点从当前位置移除，需要把前面节点的next和后面节点的prev修改
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void pushTop(Node node){
        //把节点放到最前面，直接把dummy的next赋成自己的next
        node.next = dummy.next;
        //把前驱定成dummy
        node.prev = dummy;
        //剩下的就是告诉前后自己来了
        node.next.prev = node;
        node.prev.next = node;
    }

获取节点就可以通过map，直接用key获取，如果map中没有就返回null

2.新加入的节点

两个注意点：

1. 要先判断是否已经存在这个值，如果存在，直接修改value

2. put之后判断map的大小是否超过capacity（判断map的大小也比判断链表的长度简单的多，所以这里又是用map的好处），如果超过，就同时在map和链表中删除对应的数据

完整代码：

class LRUCache {
    public static class Node{
        int key;
        int value;
        Node prev;
        Node next;
        Node(int k,int v){
            key = k;
            value = v;
        }
    }
​
    private final int capacity;
    private final Map<Integer,Node> map = new HashMap<>();
    private final Node dummy = new Node(0,0);
​
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }
    
    public int get(int key) {
        Node node = getNode(key);
        return node != null ? node.value : -1;
    }
    
    public void put(int key, int value) {
        Node node = getNode(key);
        if(node != null){
            node.value = value;
            return;
        }
        node =  new Node(key,value);
        map.put(key,node);
        pushTop(node);
        if(map.size() > capacity){
            Node bottomNode = dummy.prev;
            map.remove(bottomNode.key);
            remove(bottomNode);
        }        
    }
    private Node getNode(int key){
        if(!map.containsKey(key)){
            return null;
        }
        Node node = map.get(key);
        remove(node);
        pushTop(node);
        return node;
    }
    private void remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void pushTop(Node node){
        node.next = dummy.next;
        node.prev = dummy;
        node.next.prev = node;
        node.prev.next = node;
    }
}
​
/**
 * 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);
 */