来练习：LRU 缓存算法

背景

算法题目可见： Leetcode - LRU 缓存
基本了解可见：
- LRU Wiki
- 百度百科

个人笔记

一道中等难度的题目，吾辈也是看了题解后能勉强书写，是按着这个题解实现，其中的关于书本抽取的比喻非常形象，方便记忆，所以推荐。

一摞书的抽取

当然，更直观的例子就是我们的手机系统中当切换到后台 App 管理的界面效果，最近打开的 App 总是排列在最前。

总之，LRU 应用到实际，你可以了解的关键词比如有： “缺页中断”， “页面置换算法”

代码组织

参考（前文外链的）题解的思路，对 LRU 功能简单认识后，功能实现需要一个链表（双向循环链表）和一个映射表结构（Map<key, Node>），可见 #get, #put 功能函数都涉及到对某个可能（已存在）节点的更新操作（将该节点从原位置“抽出”，并且放置到“最前”），——如此的逻辑单独封装，就是下面代码中，单独声明的功能函数 #getNode 。

另外，对于链表的指针操作，即声明为 #remove 和 #pushFront

拢共五个功能函数：

对外暴露两个： #get #put；
操作指针，增删节点： #remove, #pushFront
将“抽出”、“放置最前”的逻辑封装，获取节点： #getNode

代码

TS 实现

LRUCache.ts

class Nodex {
  public prev: Nodex | null;
  public next: Nodex | null;

  constructor(public key = 0, public value = 0) {
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {

  public key2Node: Map<number, Nodex>;
  public pivotNode: Nodex;

  constructor(public capacity: number) {
    this.key2Node = new Map();

    const pivotNode = new Nodex()
    pivotNode.prev = pivotNode;
    pivotNode.next = pivotNode;
    this.pivotNode = pivotNode;
  }

  get(key: number): number {
    const node = this.getNode(key);
    return node ? node.value : -1;
  }

  put(key: number, value: number) {
    let node = this.getNode(key);
    if (node) {
      node.value = value;
      return;
    }
    node = new Nodex(key, value);
    this.pushFront(node);
    this.key2Node.set(key, node);

    if (this.key2Node.size > this.capacity) {
      const tailNode = this.pivotNode.prev!;
      this.remove(tailNode);
      this.key2Node.delete(tailNode.key)
    }
  }

  private getNode(key: number): Nodex | null {
    if (!this.key2Node.has(key)) return null;

    const node = this.key2Node.get(key)!;
    this.remove(node);
    this.pushFront(node);
    return node;
  }

  private pushFront(node: Nodex) {
    node.prev = this.pivotNode;
    node.next = this.pivotNode.next;
    node.prev.next = node;
    node.next!.prev = node;
  }

  private remove(node: Nodex) {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
}

JS 实现

LRUCache.js

function Node(key = 0, value = 0) {
  this.key = key;
  this.value = value;
  this.next = null;
  this.prev = null;
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.key2Node = new Map();

    const pivot = new Node();
    pivot.next = pivot;
    pivot.prev = pivot;
    this.pivot = pivot;
  }

  #getNode(key) {
    if (!this.key2Node.has(key)) return null;

    const node = this.key2Node.get(key);
    this.#remove(node);
    this.#pushFront(node);
    return node;
  }

  #remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  #pushFront(node) {
    node.prev = this.pivot;
    node.next = this.pivot.next;
    node.prev.next = node;
    node.next.prev = node;
  }

  get(key) {
    const node = this.#getNode(key);
    return node ? node.value : -1;
  }

  put(key, value) {
    let node = this.#getNode(key);
    if (node) {
      node.value = value;
      return;
    }

    node = new Node(key, value);
    this.#pushFront(node);
    this.key2Node.set(key, node);

    if (this.key2Node.size > this.capacity) {
      const tailNode = this.pivot.prev;
      this.#remove(tailNode);
      this.key2Node.delete(tailNode.key);
    }
  }
}