如何用链表实现LRU 缓存淘汰策略？

今天学习了链表（linked list）这个数据结构。学习链表有啥用呢？如何用链表来实现“LRU缓存淘汰算法”呢？思路是啥呢？。
LRU 是啥？？
LRU（Least Recently Used）最近最少使用策略。缓存的容量是有限的
当缓存容量不足以存放需要缓存的新数据时，必须丢掉最不常用的缓存数据。

先来看看链表是啥吧

链表结构

以前因为好奇， 我跟着豆豆一起学过一些链表的基本概念，大概理解为：链表像是一个铁链子，一环扣一环。每一环也只知道自己的前后是谁。链表用一个next连接这自己的下一个元素。

好像这个概念和我们之前说的数组很像呢，确实很像，那有什么不一样的地方呢？
数组是可以任意访问的，但是链表要访问其中的第n 个元素的时候，只能从头开始找。这样，时间复杂度一直都是O(n) 链表不需要一个连续的存储空间，他的每个元素可以是零散的。如果内存不足的时候，申请一个超过内存的链表也是可以成功的，但是数组就不得行了。

• 单链表
  我比较喜欢单链表，人家多单纯啊，只是单向的用next连接着自己的下一个元素。最后一个结点的 next指向null 就好了, 如果想给里面插入或者删掉数据的时候，很简单的做法就是直接改变相应的next 指针指向就好了。

• 循环链表
  循环链表和单链表的区别就是最后一个next 指针指向第一个，这样就能形成一个单项的环。

• 双向链表
  前面的单链表和循环链表都只是单向的，那么双向链接的区别就是除了有next,还会定义prev。这样每个item 不仅仅需要存储next ，还需要存储prev，这样肯定会更多的消耗空间，那它相对于单向的好处是什么呢？
  ``

• 双向循环链表
  双向循环链表 就是双向链表 + 循环链表。两个特性的结合
  ``

从结构上来看，双向链表可以在O（1）的时间复杂度里面，找到前一个item。但是在单链表里面，需要重新再循环一次整个链表，时间复杂度就是O（n）

在实际的开发中，指定新增和指定删除的时候，双向链表的性能都要高于单向链表
相对于数组，链表更适用于更加频繁的插入，删除，和复杂度更高的场景。

如何基于链表实现 LRU 缓存淘汰算法？

基础思路是：

维护一个单向链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。  
if 这个链表里，本身有这个item，那么就把这个item 从原来的位置删掉，然后插入到链表头的位置 
else 直接插入到头部（可能还需要兼容考虑此时缓存是否满）

我感觉用数组应该也是这个思路。只是实现方式不一样而已

今天又是学习理论知识的一天，期待实践s。