LRU算法

// 定义双向链表节点
class Node {
  constructor(key, val) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

// 定义双向链表
class DoubleList {
  constructor() {

    // 初始化头尾节点
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    // 连接头尾节点
    this.head.next = this.tail;
    this.tail.prev = this.head;
    // 链表元素数
    this.size = 0;
  }

  // 在链表头部添加节点x
  addFirst(x) {
    x.next = this.head.next;
    x.prev = this.head;
    this.head.next.prev = x;
    this.head.next = x;
    this.size++;
  }

  // 删除链表中的节点x（x一定存在）
  remove(x) {
    x.prev.next = x.next;
    x.next.prev = x.prev;
    this.size--;
  }

  // 删除链表中最后一个节点，并返回该节点
  removeLast() {
    if (this.tail.prev == this.head) return null; // 链表为空
    let last = this.tail.prev; // 最后一个节点
    this.remove(last); // 删除最后一个节点
    return last; // 返回最后一个节点
  }

  // 返回链表长度
  getSize() {
      return this.size;
   }
}

// 定义LRU缓存类

class LRUCache {
   constructor(capacity) {

     // 缓存容量
     this.capacity=capacity;
     this.map=new Map();
     this.cache=new DoubleList();
   }

   get(key) {
     if (!this.map.has(key)) {
       return -1;
     } else {
       let val=this.map.get(key).val;
       this.put(key,val);
       return val;
     }
   }

  // 关键
  // 1) (隐藏：长度符合要求）如果存在key，删除已存在节点，把新值添加在最上头
  // 2） 不存在key
  //    2.1 如果满了，移除最末尾元素
  //  新值元素到最开头
   put(key,val) {
     let node=new Node(key,val);
     if (this.map.has(key)) {
       this.cache.remove(this.map.get(key));
       this.cache.addFirst(node);
       this.map.set(key,node);
     } else {
       if (this.capacity==this.cache.getSize()) {
         let last=this.cache.removeLast();
         this.map.delete(last.key);
       }
       this.cache.addFirst(node);
       this.map.set(key,node);
      }
   }
}