LRU缓存(超详细注释)

/**
 * 表示双向链表中的节点。
 */
class Node {
    constructor(key = 0, value = 0) {
        this.key = key; // 缓存条目的唯一标识符。
        this.value = value; // 与键关联的值。
        this.prev = null; // 引用列表中的上一个节点。
        this.next = null; // 引用列表中的下一个节点。
    }
}

/**
 * 表示 LRU（最近最少使用）缓存。
 */
class LRUCache {
    /**
     * 初始化具有指定容量的 LRUCache。
     * @param {number} capacity - 缓存可以容纳的最大条目数。
     */
    constructor(capacity) {
        this.capacity = capacity; // 缓存的最大容量。
        this.dummy = new Node(); // 双向链表的哨兵节点。
        this.dummy.prev = this.dummy; // 初始化指向自身的上一个指针和下一个指针。
        this.dummy.next = this.dummy;
        this.keyToNode = new Map(); // 映射以存储密钥到节点的映射。
    }

    /**
     * 从缓存中检索与给定密钥关联的节点。
     * 将访问的节点移动到列表的前面。
     * @param {number} key - 在缓存中查找的键。
     * @returns {Node|null} - 具有指定键的节点，如果未找到，则为 null。
     */
    getNode(key) {
        if (!this.keyToNode.has(key)) {
            return null; // 在缓存中找不到密钥。
        }
        const node = this.keyToNode.get(key);
        this.remove(node); //将节点从其当前位置移除。
        this.pushFront(node); // 将节点移动到列表的前面。
        return node;
    }

    /**
     * 从缓存中检索与给定键关联的值。
     * @param {number} key - 在缓存中查找的键。
     * @returns {number} - 与键关联的值，如果未找到，则为 -1。
     */
    get(key) {
        const node = this.getNode(key);
        return node ? node.value : -1;
    }

    /**
     * 将新的键值对添加到缓存中。
     * 如果密钥已存在，请更新值并将节点移动到前面。
     * 如果缓存已满，则删除最近使用最少的节点。
     * @param {number} key - 新条目的键。
     * @param {number} value - 与键关联的值。
     */
    put(key, value) {
        let node = this.getNode(key);
        if (node) {
            // 键已存在，请更新值。
            node.value = value;
            return;
        }
        node = new Node(key, value);
        this.keyToNode.set(key, node); // 将新节点添加到map中。
        this.pushFront(node); // 将新节点移到前面。
        if (this.keyToNode.size > this.capacity) {
            // 缓存已满，删除最近使用最少的节点。
            const backNode = this.dummy.prev;
            this.keyToNode.delete(backNode.key); // 从map中移除。
            this.remove(backNode); // 从列表中删除。
        }
    }

    /**
     * 从列表中删除节点。
     * @param {Node} x - 要删除的节点。
     */
    remove(x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    /**
     * 将节点添加到列表的前面。
     * @param {Node} x - 要添加的节点。
     */
    pushFront(x) {
        x.prev = this.dummy;
        x.next = this.dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}