力扣146

#数据结构/哈希表 #数据结构/链表

class Node {
    constructor(key = 0, value = 0) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.dummy = new Node();
        this.dummy.prev = this.dummy;
        this.dummy.next = this.dummy;
        this.keyToNode = new Map(); // 映射 key 与 Node 的 map
    }
    // 如果已经有这个 key 则更新 value
    put(key, value) {
        let node = this.getNode(key);
        if (node) {
            // 如果key存在，更新value
            node.value = value;
            return;
        }
        // 如果 key 不存在，新建键值对
        let newNode = new Node(key, value);
        this.keyToNode.set(key, newNode);
        // 将新 node 放到链表头部
        this.moveToHead(newNode);
        // 当超过 capacity 的时候，去掉最后一个
        if (this.keyToNode.size > this.capacity) {
            const lastNode = this.dummy.prev;
            this.keyToNode.delete(lastNode.key);
            this.removeNode(lastNode);
        }
    }
    get(key) {
        const node = this.getNode(key);
        return node ? node.value : -1;
    }
    // 获取对应 key 的 node
    getNode(key) {
        if (!this.keyToNode.has(key)) {
            return null;
        }
        const node = this.keyToNode.get(key);
        this.removeNode(node);
        this.moveToHead(node);
        return node;
    }
    // 将一个节点放到链表头部
    moveToHead(node) {
        node.prev = this.dummy;
        node.next = this.dummy.next;
        node.prev.next = node;
        node.next.prev = node;
    }
    // 删除一个节点
    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}