简单的说，就是用链表特性，表示顺序，1-2-3-4-5 如果6来了 就是 1-2-3-4-5-6 但是超过了，就 变成吗了2-3-4-5-6 然后 如果 4来了，2-3-5-6-4，就把原来的4 从 3-5 中指向修改一下
原理：
https://baijiahao.baidu.com/s?id=1633118537743651176&wfr=spider&for=pc
image.png
js实现算法：

  1. /**
  2.  * * 题目名称：实现lru算法
  3.  * * 题目地址：https://www.yuque.com/damowangdexiaogenban/geocaz/rmvnlx
  4.  * 
  5.  * 维护一个map，提供 get 和 put 方法，并且限定 max 数量。
  7.   使用时，get 可以标记某个元素是最新使用的，提升它去第一项。put 可以加入某个key-value，但需要判断是否已经到最大限制 max
  9.   若未到能直接往数组第一项里插入
  10.   若到了最大限制 max，则需要淘汰数据尾端一个元素。
  11.  */
  13. // * 思路： 时间复杂度 O(1)，那就不能数组遍历去查找 key 值。可以用 ES6 的 Map 来解了，因为 Map 既能保持键值对，还能记住插入顺序。
  15. class LRUCache {
  16.   constructor(capacity) {
  17.     this.capacity = capacity
  18.     this.cache = new Map()
  19.   }
  20.   get (key) {
  21.     // 如果存在值，就把原来的值取出来，在重新set一下就返回到了最后面
  22.     if (this.cache.has(key)) {
  23.       let temp = this.cache.get(key)
  24.       this.cache.delete(key)
  25.       this.cache.set(key, temp)
  26.       return temp
  27.     }
  28.     return -1
  29.   }
  30.   put (key, value) {
  31.     if (this.cache.has(key)) {
  32.       // 存在就先删除，在更新
  33.       this.cache.delete(key)
  34.     } else if (this.cache.size >= this.capacity) {
  35.       //缓存超过最大值就删除最近没使用的
  36.       // this.cache.keys().next().value 取出 map中的 第一个key
  37.       // map是由顺序的所以 就删除了最遥远的第一个
  38.       this.cache.delete(this.cache.keys().next().value)
  39.     }
  40.     // 设置值
  41.     this.cache.set(key, value)
  42.   }
  43. }
  45. // 测试用例
  46. let cache = new LRUCache(2 /* 缓存容量 */);
  48. cache.put(1, 1);
  49. cache.put(2, 2);
  50. console.log(cache.get(1));  // 返回  1
  51. cache.put(3, 3);    // 该操作会使得密钥 2 作废
  52. console.log(cache.get(2));     // 返回 -1 (未找到)
  53. cache.put(4, 4);    // 该操作会使得密钥 1 作废
  54. console.log(cache.get(1));      // 返回 -1 (未找到)
  55. console.log(cache.get(3));      // 返回  3
  56. console.log(cache.get(4));     // 返回  4

使用案例