LRU缓存淘汰算法
LRU缓存淘汰算法是链表的经典的应用场景
缓存
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
链表
与数组相反,链表不需要一块连续的内存空间,而是通过“指针”将一组零散的内存块串联起来。其中,内存块称为链表的“结点”。每个结点除了存储数据data外,还记录链上的下一个结点的地址,我们把这个记录下个结点地址的指针叫作后续指针next
链表的优点:插入和删除一个数据非常快,时间复杂度是O(1)
链表的缺点:随机访问数据却没有数组好,时间复杂度是O(n)
注:在链表插入和删除一个数据这个动作是非常快,但要找到要插入的位置或要删除的数据就慢了
单链表
头结点:指第一个结点,用来记录链表的基地址
尾结点:指最后一个结点。不过这个结点的指针不是指下一个结点,而是指向一个空地址NULL,表示这是链表上最后一个结点
循环链表
与单链表的区别在于:循环链表的尾结点指针指向链表的头结点
像是把一条绳子的头尾相连,变成一个环
与单链表相比,循环链表的优点是从链尾到链头比较方便。
循环链表适合处理具有环型结构的数据
双向链表
单链表只有一个方向,结点只有一个后续指针next指向后面的结点。而双向链表支持两个方向,每个结点除了有后续指针next指向后面的结点,还有一个前驱指针prev指向前面的结点。
双向链表的优点:
1.在某些情况下的插入、删除等操作比单链表简单高效。如果单链表要删除两个相邻的数据时,需要遍历两次链表。而双向链表因为保存了前面和后面的结点,只需遍历一次就可以删除两个相邻的数据。
2.对于一个有序链表,双向链表的按值查询的效率比单链表高。因为我们可以记录上次查找的位置p,每次查询时,根据要找的值与p的大小关系,决定是往前还是往后查找,所以平均只需查找一半的数据
双向循环链表
循环链表+双向链表
设计思想
空间换时间的设计思想
当内存空间充足时,我们可以选择空间复杂度相对较高,单时间复杂度相对很低的算法或数据结构,来提高代码的执行速度。
缓存就是利用空间换时间的设计思想,将数据加载在内存中来提高数据查询的速度。
时间换空间的设计思想
当内存比较紧缺时,需要反过来,用时间换空间
解答开篇
(原文摘抄)
如何基于链表实现LRU缓存淘汰算法?
我们思路
思路:我们维护一个有序单链表,越靠近链表尾部的结点时越早之前访问的。当一个新的数据被访问时,我们从链表头开始顺序遍历链表。
1.如果此数据之前已经被缓存在链表中来,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部
2.如果此数据没有在缓存链表中,又可以分为两种情况:
如果此时缓存未满,则将此结点直接插入到链表的头部;
如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部
课后思考
Q:如果字符串是通过单链表来存储的,那如何判断是一个回文串?相应的时间空间复杂度是多少?