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

王争 2019-08-23

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

取消

完成

0/1000字

划线

笔记

复制

该试读文章来自付费专栏《常用数据结构必知必会》，如需阅读全部文章，
请订阅文章所属专栏。

立即订阅

登录后留言

精选留言(8)

🎵Children乏

数组实现LRU：我们维护一个数组，越靠近数组尾部的元素是越早之前访问的。当有一个新的数据被访问时，我们从头遍历数组。

1. 如果此数据之前已经被缓存在数组中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，将其后面的所有元素向前移动一个节点，然后将此数据放入数组中最后一个元素的下一个位置

2. 如果此数据没有在缓存数组中，可以分为两种情况：
如果此时缓存未满，可直接放到数组中最后一个元素的下一个位置
如果此时缓存已满，则删除数组头第一个元素，将剩余数据向前移动一个元素，再将此结点直接插入到数组尾部

这样我们就用数组实现了一个 LRU 缓存

2019-08-29

 3

 1
ClassNotFoundException

循环遍历链表，比较第i位和length-i位的大小，循环length/2次或者(length-1)/2次，复杂度应该是O(n/2)

2019-08-27



 1
奈何*飘摇

再创建一个单链表，遍历原链表将元素往新链表头部追加，也就得到一个原链表的逆序链表，然后比较两个链表是否相同

2019-08-27



 1
static julia

通过双指针寻找中位节点，然后反转前半链表，对比和后半是否相等。

2019-09-03




灞水愚人

为什么双向链表不需要遍历呢？在链表不是有序的前提下，查询还是得遍历啊

作者回复: 你可以看看这篇文章：
https://mp.weixin.qq.com/s/Md8tprLiESR6oQKXs_Aihw

2019-08-28

 3


ZC叶😝

遍历链表到栈中，遍历到中间位置（奇数不如栈）时候做出栈处理，遍历到尾结点，如果栈为空则回文

2019-08-27




Tristan

我觉得用队列实现实现 LRU 缓存淘汰策略更贴切

2019-08-27




ZeroIce

LUR缓存缓存淘汰策略有没有相应的RFC？

作者回复: 好像没有

2019-08-26

 1



收起评论

8









下载
客户端

返回
顶部