146. LRU Cache

答疑问：需要几个哨兵节点？

答：一个就够了。一开始哨兵节点 dummy 的 prev 和 next 都指向 dummy。随着节点的插入，dummy 的 next 指向链表的第一个节点（最上面的书），prev 指向链表的最后一个节点（最下面的书）。

问：为什么节点要把 key 也存下来？

答：在删除链表末尾节点时，也要删除哈希表中的记录，这需要知道末尾节点的 key。

阅读建议：先看写法二，理解核心思路；再看写法一，理解链表细节。

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 对应的节点，同时把该节点移到链表头部
  #getNode(key) {
    if (!this.keyToNode.has(key)) {
      // 没有这本书
      return null
    }
    const node = this.keyToNode.get(key) // 有这本书
    this.#remove(node) // 把这本书抽出来
    this.#pushFront(node) // 放到最上面
    return node
  }

  get(key) {
    const node = this.#getNode(key) // getNode 会把对应节点移到链表头部
    return node ? node.value : -1
  }

  put(key, value) {
    let node = this.#getNode(key) // getNode 会把对应节点移到链表头部
    if (node) {
      // 有这本书
      node.value = value // 更新 value
      return
    }
    node = new Node(key, value) // 新书
    this.keyToNode.set(key, node)
    this.#pushFront(node) // 放到最上面
    if (this.keyToNode.size > this.capacity) {
      // 书太多了
      const backNode = this.dummy.prev
      this.keyToNode.delete(backNode.key)
      this.#remove(backNode) // 去掉最后一本书
    }
  }

  // 删除一个节点（抽出一本书）
  #remove(x) {
    x.prev.next = x.next
    x.next.prev = x.prev
  }

  // 在链表头添加一个节点（把一本书放到最上面）
  #pushFront(x) {
    x.prev = this.dummy
    x.next = this.dummy.next
    x.prev.next = x
    x.next.prev = x
  }
}

作者：灵茶山艾府链接：https://leetcode.cn/problems/lru-cache/solutions/2456294/tu-jie-yi-zhang-tu-miao-dong-lrupythonja-czgt/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。