今天学习了链表（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。
