LRU缓存淘汰算法

LRU缓存淘汰算法是链表的经典的应用场景

缓存

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

链表

与数组相反,链表不需要一块连续的内存空间,而是通过“指针”将一组零散的内存块串联起来。其中,内存块称为链表的“结点”。每个结点除了存储数据data外,还记录链上的下一个结点的地址,我们把这个记录下个结点地址的指针叫作后续指针next

链表的优点:插入和删除一个数据非常快,时间复杂度是O(1)
链表的缺点:随机访问数据却没有数组好,时间复杂度是O(n)

注:在链表插入和删除一个数据这个动作是非常快,但要找到要插入的位置或要删除的数据就慢了

单链表

头结点:指第一个结点,用来记录链表的基地址
尾结点:指最后一个结点。不过这个结点的指针不是指下一个结点,而是指向一个空地址NULL,表示这是链表上最后一个结点

循环链表

与单链表的区别在于:循环链表的尾结点指针指向链表的头结点

像是把一条绳子的头尾相连,变成一个环

与单链表相比,循环链表的优点是从链尾到链头比较方便。
循环链表适合处理具有环型结构的数据

双向链表

单链表只有一个方向,结点只有一个后续指针next指向后面的结点。而双向链表支持两个方向,每个结点除了有后续指针next指向后面的结点,还有一个前驱指针prev指向前面的结点。

双向链表的优点:
1.在某些情况下的插入、删除等操作比单链表简单高效。如果单链表要删除两个相邻的数据时,需要遍历两次链表。而双向链表因为保存了前面和后面的结点,只需遍历一次就可以删除两个相邻的数据。

2.对于一个有序链表,双向链表的按值查询的效率比单链表高。因为我们可以记录上次查找的位置p,每次查询时,根据要找的值与p的大小关系,决定是往前还是往后查找,所以平均只需查找一半的数据

双向循环链表

循环链表+双向链表

设计思想

空间换时间的设计思想

当内存空间充足时,我们可以选择空间复杂度相对较高,单时间复杂度相对很低的算法或数据结构,来提高代码的执行速度。

缓存就是利用空间换时间的设计思想,将数据加载在内存中来提高数据查询的速度。

时间换空间的设计思想

当内存比较紧缺时,需要反过来,用时间换空间

解答开篇

(原文摘抄)

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

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

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

2.如果此数据没有在缓存链表中,又可以分为两种情况:

  • 如果此时缓存未满,则将此结点直接插入到链表的头部;

  • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部

课后思考

Q:如果字符串是通过单链表来存储的,那如何判断是一个回文串?相应的时间空间复杂度是多少?