06|链表(上)

如何实现LRU缓冲淘汰算法？

引子

学习链表由什么用呢？为了回答这个问题，文明讨论一个经典链表应用场景，那就是LRU缓存淘汰算法。
缓存是一种提高数据读取性能的技术，在硬件设计，软件开发中都有着广泛的应用，比如常见的CPU缓存，数据库缓存，浏览器缓存等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
这些策略你不用死记，我打个比方你很容易就明白了。假如说，你买了很多本技术书，但有一天你发现，这些书太多了，太占书房空间了，你要做个大扫除，扔掉一些书籍。那这个时候，你会选择扔掉哪些书呢？对应一下，你的选择标准是不是和上面的三种策略神似呢？好了，回到正题，我们今天的开篇问题就是：如何用链表来实现 LRU 缓存淘汰策略呢？ 带着这个问题，我们开始今天的内容吧！

五花八门的链表结构

数组链表比较

相比数组，链表是个稍微复杂的结构，我们比较一下，两者有什么区别。
从底层存储结构看
为了直观对比，在图上，数组需要一块连续的内存空间来存储，对内存要求较高。如果申请一个100MB大小的数组，当内存中没有连续，足够大的存储空间时，即便内存的剩余总可用空间大于100MB，仍会申请失败。（因为要求连续）
而链表相反，不需要一块连续的内存空间，通过指针将一组零散的内存块串联起来使用，如果申请100MB大小的链表，根本不会有问题。

3种常见链表结构-单链表，双向链表，循环链表

最常见的单链表

链表通过指针将一组零散的内存块串联一起。其中，内存块称为链表的“结点”。为了将所有结点穿起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，将记录下一个结点地址的指针叫后继指针next。

单链表两个特殊的结点，第一个结点-头结点，最后一个结点-尾结点。头结点记录链表的基地址，用于遍历整条链表。尾结点的下一个结点是空地址NULL。
在链表种，插入与删除只需要考虑相邻节点的指针改变，对应时间复杂度O（1），不需要数组进行数据的搬移。

但链表要想访问第k个元素，就没有数组那么高效。因为链表种数据非连续存储只能一个结点一个结点的遍历，直到找到相应结点。所以链表的随机访问性能时间复杂度为O（n）。

循环链表

循环链表是一种特殊的单链表。循环链表的尾结点指针指向链表的头结点，像一个环首尾相连。

与单链表相比，循环链表的优点从链尾到链头比较方便。当要处理的数据具有环形结构特点时，就适合使用循环链表。比如约瑟夫问题。

双向链表

双向链表不止有一个后继指针next，还有一个前驱指针prev。

从结构上看，双向链表可以支持O（1）时间复杂度情况下找到前驱结点，这使双向链表在某些情况下的插入，删除，都比单链表简单，高效。但单链表的插入，删除操作的时间复杂度是O(1)，还能怎么高效呢？

看删除操作。
在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：
删除结点中“值等于某个给定值”的结点；
删除给定指针指向的结点。
对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过我前面讲的指针操作将其删除。
尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。
对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。
但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！
同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。
在实际开发中，双向链表使用更加广泛。例如JAVA语言中的LinkedHashMao这个容器的实现原理就用到了双向链表。
实际上这里采用了用空间换时间的设计思想。开篇缓存的例子也是使用空间换时间。
将循环链表，双向链表整合一起可以形成双向循环链表。

链表vs数组性能比拼

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

Java 中的 ArrayList 容器虽然支持动态扩容。但当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。

一个稍微极端的例子。如果我们用 ArrayList 存储了了 1GB 大小的数据，这个时候已经没有空闲空间了，当我们再插入数据的时候，ArrayList 会申请一个 1.5GB 大小的存储空间，并且把原来那 1GB 的数据拷贝到新申请的空间上。会更加耗时。

除此之外，如果代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

解答开篇

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

我的思路是这样的：我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。

2. 如果此数据没有在缓存链表中，又可以分为两种情况：
   如果此时缓存未满，则将此结点直接插入到链表的头部；
   如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

这样就用链表实现了一个LRU缓存。

缓存访问的时间复杂度是多少。因为不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度为 O(n)。

实际上，我们可以继续优化这个实现思路，比如引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。因为要涉及我们还没有讲到的数据结构，所以这个优化方案，我现在就不详细说了，等讲到散列表的时候，我会再拿出来讲。

除了基于链表的实现思路，实际上还可以用数组来实现 LRU 缓存淘汰策略。如何利用数组实现 LRU 缓存淘汰策略呢？

内容小结

今天我们讲了一种跟数组“相反”的数据结构，链表。它跟数组一样，也是非常基础、非常常用的数据结构。不过链表要比数组稍微复杂，从普通的单链表衍生出来好几种链表结构，比如双向链表、循环链表、双向循环链表。

和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。不过，在具体软件开发中，要对数组和链表的各种性能进行对比，综合来选择使用两者中的哪一个。

课后思考

如何判断一个字符串是否是回文字符串的问题。如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？相应的时间空间复杂度又是多少呢？

1.快慢指针定位中间结点
2.从中间结点对后半部分逆序
3.前后半部分比较，判断是否为回文
4.后半部分逆序复原
时间复杂度O(n) 空间复杂度O(n)

Disruptor 一个开源项目 硬件用到极致。