LRU缓存机制（链表实现）

// 首先构造一个链表节点类
class ListNode {
  constructor(key,value) {
    this.key = key;
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}
// 构造一个LRU缓存类
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.hash = {};
    this.count = 0;
    // 这里的head可以理解为最近使用过的，tail则可以理解为最久未使用的
    this.dummyHead = new ListNode();
    this.dummyTail = new ListNode();
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }
  // 实现get方法
  get(key) {
    // 首先取出hash对象中这个键对应的节点
    let node = this.hash[key];
    // 如果这个节点不存在，返回-1
    if (node === undefined) return -1;
    // 如果这个节点存在的话，从链表中移除已有节点，然后再添加到头部
    this.deleteFromList(node);
    this.addToHead(node);
    return node.value;
  }
  // 实现put方法
  put(key,value) {
    // 首先取出哈希对象中这个键对应的节点
    let node = this.hash[key];
    // 分存在和不存在两种情况进行讨论
    if (node === undefined) {
      // 如果LRU是满的
      if (this.count === this.capacity) {
        // 取出最久未使用的
        let tail = this.dummyTail.prev;
        // 从LRU中删除
        this.deleteFromList(tail);
        // 从hash对象中删除
        delete this.hash[tail.key];
        // LRU的数量-1
        this.count--;
      }
      // 创造一个新的节点
      let newNode = new ListNode(key,value);
      this.hash[key] = newNode;
      this.addToHead(newNode);
      this.count++;
    } else {
      // 更新value
      node.value = value;
      this.deleteFromList(node);
      this.addToHead(node);
    }
  }
  deleteFromList(node) {
    let temp1 = node.prev;
    let temp2 = node.next;
    temp1.next = temp2;
    temp2.prev = temp1;
  }
  addToHead(node) {
    node.prev = this.dummyHead;
    node.next = this.dummyHead.next;
    this.dummyHead.next.prev = node;
    this.dummyHead.next = node;
  }
}
复制代码