题解 | Java 实现 LRU 缓存，超详细注释

思路：自己手写一个双向链表 DoubleLinkedNode，配合 HashMap 实现 LRU 缓存

时间复杂度和空间复杂度都是 O(1)

import java.util.*;

public class Solution {
	// 手写一个双向链表的类，包含 key, value, 前后指针 prev, next，无参/有参的构造方法
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    // 成员变量
    int size;
    int capacity;
    DLinkedNode head;
    DLinkedNode tail;
    // 建一个哈希表，value 为 DLinkedNode，方便取 node 进行操作
    Map<Integer, DLinkedNode> map = new HashMap<>();
    
    public Solution(int capacity) {
    // 初始化
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
	//  初始化 ，head & tail 双向链表头尾相连
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
    	// 找不到就直接返回 -1
        if (!map.containsKey(key)) {
            return -1;
        } else { // 找到了就取值返回，注意要把这个热数据移到双向链表的开头
            DLinkedNode node = map.get(key);
            moveToHead(node);
            return node.value;
        }
    }

    public void set(int key, int value) {
    	// 有这个key的话就修改value值，然后移到最前面
        if (map.containsKey(key)) {
            DLinkedNode node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else { 
        // 没有的话就新建结点，头插，map 中也添加这对新值
        // 判断容量超了就删除尾节点，并且删除尾节点对应的map里的值
            DLinkedNode node = new DLinkedNode(key, value);
            map.put(key, node);
            addToHead(node);
            size++;
            if (size > capacity) {
                int tmpKey = deleteTail();
                size--;
                map.remove(tmpKey);
            }
        }
    }
    // 移到开头分两步：1、删除这个结点 2、头插
    public void moveToHead(DLinkedNode node){
        deleteNode(node);
        addToHead(node);
    }
    // 删除节点，很简单
    public void deleteNode(DLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    // 头插，注意步骤顺序,不要弄丢 head.next
    public void addToHead(DLinkedNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    // 删除尾节点，先保存一下，注意把删除节点的 key 返回给map，以便 map.remove(key)
    public int deleteTail() {
        DLinkedNode node = tail.prev;
        deleteNode(node);
        return node.key;
    }
}