146. LRU 缓存（算法200题-3）

一、使用双向链表

// 双向链表
class NodeList {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.prev = null
    this.next = null
  }
}
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.hasTable = {}
    this.count = 0
    this.dummyHead = new NodeList()
    this.dummyTail = new NodeList()
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }
  get(key) {
    const node = this.hasTable[key]
    if (node) {
      this.removeToHead(node)
      return node.value
    }
    return -1
  }
  put(key, value) {
    const node = this.hasTable[key]
    if (node) {
      node.value = value
      this.removeToHead(node)
    } else {
      const newNode = new NodeList(
        key,
        value
      )
      this.hasTable[key] = newNode
      this.count++
      // 溢出则删除最后一个旧节点
      if (this.count > this.capacity) {
        this.removeOldItem()
      }
      this.addToHead(newNode)
    }
  }
  // 移动节点到头部
  removeToHead(node) {
    this.removeToList(node)
    this.addToHead(node)
  }
  // 删除节点
  removeToList(node) {
    node.prev.next = node.next
    node.next.prev = node.prev
  }
  // 节点加到头部
  addToHead(node) {
    node.next = this.dummyHead.next
    this.dummyHead.next = node
    node.prev = this.dummyHead
    node.next.prev = node
  }
  // 删除最后一个旧节点
  removeOldItem() {
    const oldItem = this.dummyTail.prev
    delete this.hasTable[oldItem.key]
    this.count--
    oldItem.prev.next = this.dummyTail
    this.dummyTail.prev = oldItem.prev
  }
}

二、使用map + 迭代器

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.map = new Map()
  }
  get(key) {
    if (this.map.has(key)) {
      const value = this.map.get(key) 
      this.map.delete(key)
      this.map.set(key, value)
      return value
    }
    return -1
  }
  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key)
    } else {
      if(this.map.size >= this.capacity) {
        this.map.delete(this.map.keys().next().value)
      }
    }
    this.map.set(key, value)
  }
}