链表（上）：如何实现LRU缓存淘汰算法？

我们都知道缓存可以提高数据读取的性能，但是缓存的大小有限，当缓存被填满时，哪些数据应该被清理出去？哪些数据应该被保留？这就需要缓存淘汰策略来决定。
常见的策略有三种（基本上见名知意了）：

• 先进先出策略 FIFO（First In，First Out）
• 最少使用策略 LFU （Least Frequently Used）
• 最近最少使用策略 LRU （Least Recently Used）

那么如何使用 链表 来实现LRU缓存淘汰算法呢？

1. 五花八门的链表结构

先来看看数组与链表的区别。

底层的存储结构的区别

image

注意数组需要的是一块 连续的内存空间，比如说数组需要 100m 的存储空间，而内存中的闲置空间可以达到 100m 但却不是连续的，那么就很尴尬了，此时数组申请内存会失败。

而链表并不需要一块连续的内存空间，它通过 指针 将一组 零散的内存块 串联起来使用，上述情况下使用链表就不会有问题。

常见的三种链表：单链表 循环链表 双向链表

2. 单链表

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

image

• 头结点：记录链表的基地址，通过它我们可以遍历得到整条链表
• 尾结点：后继指针指向一个 空地址 NULL ，表示这是链表上最后一个结点

链表也支持数据的查找、插入和删除操作。

在执行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度为：○(n)
在链表中插入或删除一个数据，并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。（所以才会说链表的插入或删除一个数据是非常快速的）

image

可以自己画一下删除是什么样的。

利弊皆存。链表要随机访问第 k 个元素，是没有数组那么高效的，因为 链表中的数据并非连续存储，所以无法像数组那样根据首地址和下标，通过寻址公式直接计算出对于元素的内存地址，而是需要根据指针一个结点一个结点地依次遍历，知道找到相应的结点。

因为单链表只有后继指针，都是一个接着一个的，也就是前一个能找到后一个，只有这么一个一个找下去，才能找到我们要的第 k 个值，所以链表的随机访问性能没有数组好，需要 ○(n) 复杂度。

3. 循环链表

循环链表是一种特殊的单链表。 它与单链表唯一的区别就在于，它的尾结点指针指向了它的头结点，如下图：

image

与单链表相比 循环链表 的优点是从链尾到链头比较方便，当要处理的数据具有环形结构特点时，就特别适合采用循环链表。比如注明的 维基百科：约瑟夫问题 百度百科：约瑟夫问题

4. 实际开发中最常用的链表：双向链表

双向链表，支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

image

从上图可以看到，双向链表需要两个空间来存储后继结点和前驱结点的地址。

所以，存储同样多的数据，双向链表要比单链表占用更多的内存空间。可因为双向链表支持双向遍历，提高了其灵活性。从结构上来看，双向链表可以支持 ○(1) 时间复杂度的情况下找到前驱结点（根据前驱指针 prev），这样的话，在某些情况下的插入、删除都会比单链表简单、高效。

删除操作

• 删除结点中 值等于某个给定值 的结点；①
• 删除给定指针指向的结点；②

对于 ① ，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个一次遍历对比。尽管单词的删除操作的时间复杂度是 ○(1)，但是遍历查找才是主要的耗时点，对应的时间复杂度为 ○(n)，（时间复杂度分析中的加法法则）总时间复杂度为 ○(n)

对于 ② ，已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接后去前驱结点，所以为了找到前驱结点，还是要从头开始遍历链表，知道 p 的 next 结点是 q ，说明 p 是 q 的前驱结点。
但是对于双向链表来说，就不需要像单链表那样遍历了，因为双向链表中的结点已经保存了前驱结点的指针 prev ，所以单链表删除操作需要 ○(n)，但是双向链表只需要在 ○(1) 的时间复杂度内就搞定了。

插入操作

同样的双向链表的插入操作需要 ○(1) 而单链表需要 ○(n)。

5. 双向链表比单链表应用更加广泛的原因

用空间换时间 的设计思想。当内存空间充足的时候，可以选择空间复杂度较高的，但时间复杂度相对很低的算法和数据结构来追求代码的执行速度。相反，如果内存空间比较紧缺，就要反过来使用 时间换空间 的设计思路。

双向链表比单链表每个结点多存储了一个 prev ，虽然所需存储空间增大了，但是效率可以提高很多。java 中的 LinkedHashMap 容器，其实现原理中就用到了 双向链表 这种数据结构。

6. 缓存就是一种以时间换空间的典型案例

如果把数据存储到硬盘上，会比较省农村，但是每次查找数据都要询问一次硬盘，会比较慢。但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但每次查询的书读就大大提高了。

将 循环链表 和 双向链表 合起来就是 双向循环链表：

image

7. 链表 VS 数组性能大比拼

数组和链表是两种截然不同的内存组织方式，因为内存存储的问题，他们插入、删除、随机访问操作的时间复杂度正好相反：

image

注意： 在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据！

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

数组的缺点是大小固定，一经声明就要占用整块连续内存空间，如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致 内存不足。而声明的数组过小，则不够用时只能再申请一个更大的内存空间，把原数组拷贝过去，非常费事。

链表本身没有大小的限制，支持动态扩容，这也是它与数组最大的区别。

image

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

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

• 如果此数据之前就已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。（表示这条数据是最近使用的）
• 如果此数据没有被缓存在链表中，又可以分为两种情况
  • 如果缓存未满，则将此数据直接插入到链表的头部。
  • 如果缓存已满，则删除链表的尾结点，将新的数据插入链表的头部。

计算一下时间复杂度：因为不管存不存在，都是一定要遍历一次链表的，所以时间复杂度为 ○(n)

可以使用散列表继续优化，以后会学到的

9. 如何使用数组实现 LRU 缓存淘汰策略？

• 遍历数组中是否含有该数据
  • 有：假设该数据所在下标为 x ，则将数组 从 0~(x-1) 的数据右移一位，将该数据放在 下标=0 的位置
  • 没有：则将数组 从 0~(n-1) 右移一位，将该元素放在 下标=0 的位置
• 数组的初始容量 n 就是该缓存的大小

计算一下时间复杂度：

• 最好时间复杂度：有该数据且该数据所在下标正好是 0：○(1)
• 最坏时间复杂度：无该数据或该数据的下标正好是 n：○(n)
• 平均时间复杂度： image

所以时间复杂度为：○(n)

10. 课后思考

如何判断一个字符串是否是回文字符串？

（回文串：正读反读都是一个意思：level，noon，12321等等）

思路：假设字符串长度为n，循环 n/2 次，i 初始为 0，每次判断 str[i] 与 str[n-i-1] 是否相等即可。
时间复杂度：○(n)

如果字符串是通过 单链表 来存储的，那该如何来判断是一个回文串呢？

我的思考：
将该链表遍历取值，反向取，从尾结点取值取到首结点。（需要双层循环，复杂度为 ○(n²)）
每次取到的值都放在一个新的链表中，按正常的先后顺序存放即可。

判断原链表的前一半与新链表的前一半是否都相等（复杂度为 ○(n)）

最后时间复杂度为 ○(n²)

看该文章下面的评论学习到的解决方式：

1. 通过快慢指针定位中间节点
2. 从中间节点对后半部分逆序
3. 前后半部分比较，判断是否为回文
4. 后半部分逆序复原

本篇篇幅过长，上述问题解析在下一篇中。