先讨论一个经典的链表应用场景 , 那就是LRU缓存淘汰算法.
缓存
缓存是一种高数据读取性能的技术,有着非常广泛的应用.
常见的: CPU缓存 数据库缓存 浏览器缓存
缓存大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留.
需要缓存淘汰策略来决定:
常见策略有:
- 先进先出策略FIFO
- 最少使用策略LFU
- 最近最少使用策略LRU
打个比方,比如买了一堆书,有一天发现书太多了,需要扔一部分.那么就可以选择上面的策略.
五花八门的链表结构
底层存储结构
数组:数组需要一块连续的内存空间来存储,对内存的要求是比较高.如果我们申请了一个100MBda大小的数组,当内存中没有连续的 足够的大的存储空间时候,即便内存的剩余总可用空间大于100MB,仍然会申请失败.
链表:不需要一块连续的内存空间,通过指针将一组零散的内存块串联起来使用,如果我们申请100MB大小的链表,根本不会有问题.
单链表 双链表 循环链表
单链表
链表通过指针将一组零散的内存块串联一起, 把内存块称之为链表的结点.
为了将所有的结点串起来, 每个链表的结点除了存储数据之外,还需要记录链上下一个结点的地址.如图所示, 我们把记录下一个结点地址的指针叫后继指针next.
上图有两个结点比较特殊,第一个结点(头结点)和最后一个结点(尾结点)
其中头结点为记录链表的基地址,有了它,就可以遍历整条结点.而尾结点是直接指向一个空地址NULL,表示这是链表上最后一个结点
单链表的插入 查找 删除
数组的插入和删除时,为了保持内存数据的连续性,需要做大量的数据搬移,此时时间复杂度为O(n).
链表的插入和删除时,只需要考虑相邻结点的指针改变,所以此时时间复杂度为O(1)
有利有弊,链表要随机访问第k个元素,就没有数组那么高效.链表中的数据并非连续存储,没有办法像数组那样根据首地址和下表,通过寻址公式就能直接计算出对应的内存地址,而是需要根据指针一个结点一个结点进行一次遍历,去找到相应的结点.
把链表想象成一个队伍,队伍中每个人都知道自己后面的人是谁,所以当我们希望指导排在第k个人是谁,就需要一个一个遍历. 需要O(n)时间复杂度.
循环链表
循环链表是一种特殊的单链表,唯一的区别是,循环链表的尾结点指向头结点.
有一个著名的约瑟夫问题
双向链表
支持两个方向,结点还有个前驱指针prev指向前面的结点
双向链表和单向链表的区别:
- 双向链表比单链表占用更多的内存空间,但可支持双向遍历,这样带来了双向链表操作的灵活性
- 从结构上来看双向链表支持O(1)时间复杂度的情况下找到前驱节点,使得某些情况下,插入 删除操作更高效 简单.
双向循环链表
链表/数组性能比拼
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 插入删除 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
解答开篇
基于链表实现LRU缓存淘汰算法?
思路: 维护一个有序的单链表,越靠近链表尾部的结点是越早之前访问的,当有新的数据被访问时,我们从链表头开始顺序遍历链表.
- 如果此数据之前已经存在链表中,我们遍历得到这个数据对应的结点,将其从原来的位置删除,再插入到链表头部.
- 如果此时数据没有在缓存链表中,分为两种情况
- 缓存未满,此结点插入到链表的头部
- 缓存已满,链表尾结点删除,将新的数据结点插入链表的头部.
时间复杂度: 无论缓存有没有满,都必须遍历一遍链表,所以这种基于链表实现的思路,时间复杂度为O(n)
实际上也可以用
散列表来记录每个数据的位置,将缓存访问的时间复杂度降到O(1).