[数据结构与算法]LeetCode146 LRU 缓存机制

题目

解题：双向链表+散列表

// javascript
var DoubleLinkedListNode = function(key, value) {
    this.key = key;    // 记录 key
    this.val = value;
    this.prev = null;
    this.next = null;
};

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.cap = capacity;
    this.usedSpace = 0;
    this.cache = new Map();
    this.head = new DoubleLinkedListNode(undefined, undefined); // 伪头节点
    this.tail = new DoubleLinkedListNode(undefined, undefined); // 伪尾节点
    this.head.next = this.tail;
    this.tail.prev = this.head;
};

LRUCache.prototype.removeNode = function(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
};

LRUCache.prototype.addToTail = function(node) {
    this.tail.prev.next = node;
    node.prev = this.tail.prev;
    this.tail.prev = node;
    node.next = this.tail;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (this.cache.has(key) === true) {
        let node = this.cache.get(key);
        // 把该节点移动到双向链表的末端
        this.removeNode(node);
        this.addToTail(node);
        return node.val;
    }
    return -1;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
	// 如果存在，调用 get 将该节点移动到双向链表末端
    if (this.get(key) !== -1) {
        (this.cache.get(key)).val = value;
    } else {
    	// 如果双向链表已满，要先把最前面的节点删除
        if (this.usedSpace >= this.cap) {
            let delNode = this.head.next;
            this.removeNode(delNode);
            this.usedSpace--;
            this.cache.delete(delNode.key);
        }
        // 在双向链表的末端插入节点，cache 记录节点的地址
        let newNode = new DoubleLinkedListNode(key, value);
        this.addToTail(newNode);
        this.usedSpace++;
        this.cache.set(key, newNode);
    }
};

时间复杂度：对于 put 和 get 都是 $O(1)$。

空间复杂度：$O(capacity)$。