前几节学习了「链表」、「时间与空间复杂度」的概念，本节将结合「循环链表」、我的真实献妻经历「双向链表」与 「用空间换时间的设计思想」来设计一个很有意思的缓存淘汰策略：LRU缓存淘汰算法。
如上图所示：单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。
因此循环链表是一种特殊的单链表。它跟单链表唯一的区别就在于尾结点。它像一个环一样首尾相连，所以叫作「循环链表」。
和单链表相比，循环链表的优点是从链尾到链头比较方便，当要处理的数据具有环型结构特点时，适合采用循环链表。
双向链表也叫双链表，是链表的一种，它的链接方向是双向的，它的每个数据结点中都包含有两个指针，分别指向直接后继和直接前驱。
与单向链表相对比双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。
头插法：将链表的左边称为链表头部，右边称为链表尾部。头插法是将右边固定，每次新增的元素都在左边头部增加。
尾插法：将链表的左边称为链表头部，右边称为链表尾部。尾插法是将左边固定，每次新增都在链表的右边最尾部。
双向链表的灵活处就是知道链表中的一个元素结构就可以向左或者向右开始遍历查找需要的元素结构。因此对于一个有序链表，双向链表的按值查询的效率比单链表高一些。因为，我们可以记录上次查找的 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
对于双向链表来说，双向链表中的结点已经保存了前驱结点的指针，删除时不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度。
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
在各个语言的第三方框架中都大量使用到了 LRU 缓存策略。程序员小吴接触到的有Java中的 「 Mybatis 」，iOS中的 「YYCache」与「Lottie」等。
LRU是最近最少使用策略的缩写，是根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
将Cache的所有都用双链表连接起来，当一个被命中之后，通过调整链表的指向，将该调整到链表头的，新加入的Cache直接加到链表头中。
这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。
通过动图可以发现，如果缓存空间足够大，那么存储的数据也就足够多，通过缓存中命中数据的概率就越大，也就提高了代码的执行速度。这就是空间换时间的设计思想。
网友评论 ()条 查看