题解 | #设计LRU缓存结构#

JavaScript代码，使用单链表数据结构模拟。
参考文章：https://juejin.cn/post/6844903855726002189
并没有像LRU描述的那样真的“删除节点”，只是在链表中进行了移除操作。

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
function LRU(operators, limit) {
    // 定义链表数据结构
    class Node {
        constructor(key, value, next = null) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    // head不计入链表总个数，其next指向第一个node
    let head = new Node(Number.MIN_VALUE, Number.MIN_VALUE);
    const resArr = [];
    for (const [op, k, v] of operators) {
        let temp = head.next;
        let pre = head;
        if (v) { // put
            while (temp) {
                // key已经存在
                if (temp.key === k) {
                    let node = new Node(k, v);
                    // 删除此节点
                    pre.next = temp.next;
                    // 插入新节点
                    let t = head.next;
                    head.next = node;
                    node.next = t;
                    break;
                }
                pre = pre.next;
                temp = temp.next;
            }

            if (temp === null) {  // key 不存在，插入含有key的节点
                let node = new Node(k, v);
                let t = head.next;
                head.next = node;
                node.next = t;
            }
        } else { // get操作
            while (temp) {
                // key存在
                if (temp.key === k) {
                    // console.log(temp.value);
                    resArr.push(temp.value);
                    let node = new Node(k, temp.value);
                    // 删除此节点
                    pre.next = temp.next;
                    // 插入新节点
                    let t = head.next;
                    head.next = node;
                    node.next = t;
                    break;
                }
                pre = pre.next;
                temp = temp.next;
            }
            // 没找到，返回-1
            if (temp === null) {
                // console.log(-1);
                resArr.push(-1);
            }
        }

        // 截断链表，在limit长度截断
        let i = 1;
        temp = head;
        while (i <= limit && temp) {
            temp = temp.next;
            i += 1;
        }
        if (temp) {
            temp.next = null;
        }
    }

    return resArr;
}


module.exports = {
    LRU : LRU
};