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

东方耀

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


缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常
见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要
缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使
用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）



单链表、双向链表和循环链表

在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬
移，所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据，我们并不需要为了保持内存
的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个
数据是非常快速的。
但是，有利就有弊。链表要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据
并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应
的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点
循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结
点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结
点指针是指向链表的头结点
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所
以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费
存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性


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

我的思路是这样的：我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有
一个新的数据被访问时，我们从链表头开始顺序遍历链表。
1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的
位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部；
如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
这样我们就用链表实现了一个 LRU 缓存



设计思想
时空替换思想：“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对
较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较
紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。

itismychat

好好学习天天向上