146. LRU 缓存 - Java 双向链表+哈希表

原题地址：https://leetcode.cn/problems/lru-cache/

题解

LRU缓存本质上是手搓一个双向链表，并结合哈希表映射实现LRU的更新

当我们向双向链表中添加一个节点时，也创建一个<Integer,ListNode>的键值对，以便我们迅速地通过关键字在链表中找到对应节点

对于链表，我们规定越靠前的元素越少被使用

当一个Key被使用（包括查询和更新）时，我们需要进行一次操作：找到链表中Key对应的节点，并将其从链表中删除，然后重新添加到链表末尾

refresh操作：

• 找到链表中Key对应的节点，并将其从链表中删除，然后重新添加到链表末尾
• 用于指示该关键字是最近被使用

get操作：

• 在哈希表中查找是否存在关键字
• 若存在，则对关键字进行refresh操作，然后返回value值
• 若不存在，则返回-1

put操作：

• 在哈希表中查找是否存在关键字
  • 若存在，则对关键字指向节点的value进行更新，并对关键字进行refresh操作
• 若不存在，则检查双向链表的长度是否达到capacity
  • 若已达到容量，则删除表中的第一个元素，并移除哈希表中的键值对，指示该关键字已被删除
• 将新节点加入表尾，并添加关键字和节点的键值对

时间复杂度：O(1)

空间复杂度：O(N)

class LRUCache {
    class ListNode{
        int key;
        int val;
        ListNode next;
        ListNode last;
        ListNode(int k,int v){
            this.key=k;
            this.val=v;
        }
    }
    //哈希绑定Key和对应节点
    Map<Integer,ListNode> idx=new HashMap<>();
    //虚拟头节点，val记录链表长度
    ListNode head=new ListNode(0,0);
    ListNode tail=head;
    int capacity;
    void removeNode(ListNode node){
        if(node==tail){
            tail=node.last;
            tail.next=null;
        }else{
            node.last.next=node.next;
            node.next.last=node.last;
        }
        head.val--;
    }
    void addNode(ListNode node){
        tail.next=node;
        node.last=tail;
        tail=tail.next;
        tail.next=null;
        head.val++;
    }
    void refreshKey(int key){
        removeNode(idx.get(key));
        addNode(idx.get(key));
    }

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

    //如果找到则refresh关键字，然后返回val，找不到则返回-1
    public int get(int key) {
        if(idx.containsKey(key)){
            refreshKey(key);
            return idx.get(key).val;
        }
        else return -1;
    }

    public void put(int key, int value) {
        //如果存在节点则更新值并refresh关键字
        if(idx.containsKey(key)){
            idx.get(key).val=value;
            refreshKey(key);
        }else{
            //链表达到容量上限则删除表头元素，并移除哈希键值对
            if(head.val>=capacity){
                idx.remove(head.next.key);
                removeNode(head.next);
            }
            //添加新节点
            addNode(new ListNode(key,value));
            idx.put(key,tail);
        }
    }
}