数据结构与算法-链表_存储在rom中的数据断电后不会丢失

一,前言

上一篇介绍了常用数据结构-数组
除了数组,还有一种常用的数据结构叫做链表
这一篇就来介绍一下链表
1
2
3

---

二,链表

数组需要一段连续的内存空间来存储
而链表不需要连续的内存空间，通过“指针”将一块一块零散的内存区块连接在一起
1
2

分析:

如果我们有50M的的可用内存空间,那么对于数组,由于这50M空间在内存中未必是连续的
所以申请50M大小的数组未必能成功,但是如果使用链表数据结构,就一定没有问题
1
2

// TODO 数组,链表的内存空间对比

链表有很多种数据结构,常见的有:

单链表
循环链表
双向链表
双向循环链表
1
2
3
4

---

三,单链表

最简单的链表结构就是单链表

// TODO 单链表图示

如图所示,链表中每一个内存区块都是链表的一个"节点"
头结构:第一个节点叫做头结构,记录链表的基地址,根据头节点记录的链表基地址,就可以遍历得到整条链表
尾节点:最后一个节点叫做尾节点,尾节点没有下一个节点,所以指向空地址null
链表的每个节点不仅要存储数据,还要有一个指针指向下一个节点,记录下一节点地址的指针叫做后继指针next
1
2
3
4

链表的插入和删除操作:

数组在进行插入和删除操作时,由于要保持内存数据的连续性,需要大量的数据搬移工作,所以时间复杂度为O(n)
而链表本身内存空间就不是连续的,所以进行插入和删除操作时不需要数据搬移,只需要考虑相邻节点的指针改变
所以链表的插入和删除操作的时间复杂度是O(1)
1
2
3

// TODO 链表插入,删除图示

链表的查找操作:

相反的,链表由于存储空间不是连续的,所以不能像数组一样通过寻址公式进行随机访问
要想访问链表的第k个元素,就只能从头节点开始,依次遍历在整条链表中进行查找
所以,链表的随机访问效率较低,时间复杂度为O(n)
1
2
3

---

四,循环链表

循环链表和单链表的区别

循环链表是一种特殊的单链表,和单链表唯一的区别就是尾节点
单链表的尾节点指针指向空地址,表示链表中的最后一个节点
循环链表的尾节点指针指向链表的头节点,使整个链表首尾相连
1
2
3

// TODO 循环链表图示

循环链表的优点:

和单链表相比,由于数据结构的特殊性,循环链表从链尾查找链头比较方便
1

循环链表的应用场景:

要处理的数据存在环形结构特点,适合采用循环链表数据结构
1

---

五,双向链表

单链表每个节点中有一个next指针指向后继结点,所以单链表只支持从前到后这一个方向
双向链表能够支持两个方向,每个节点不仅有一个next指针指向后继节点,还有一个前驱节点prev指向前面的节点
1
2

// TODO 双向链表图示

对比单链表和双向链表

如图所示,双向链表不仅要保存数据,还需要额外的两个内存空间来存储前驱节点和后继节点的地址
所以,存储相同数量数据,双向链表比单链表需要更多的内存空间
1
2

双向链表支持双向遍历

但即便双向链表消耗了更多的内存空间,也非常常用
因为每个节点都有两个方向的引用,这使双向链表支持双向遍历
双向链表查找前驱结点的时间复杂度是O(1)
1
2
3

双向链表的删除操作

单链表的删除操作时间复杂度是O(1),已经非常高效了,但是在某种情况下,双向链表更为高效:

从链表中删除一个数据有一下两种情况:
情况1:删除给定值的节点
情况2:删除特定指针指向的节点

情况1,单链表和双向链表都需要先找到指定值的节点,所以都需要从头节点依次遍历查找,然后再操作指针删除
在这个操作下,删除的时间复杂度是O(1),而查找过程的时间复杂度是O(n)
所以根据加法法则,删除给定值节点的链表操作总时间复杂度为O(n)

情况2,已知要删除的接单,需要将其从链表中删除,这样就需要先找到前驱节点
单链表由于只有next后继节点引用,只能从头节点遍历查找其前驱结点,再进行删除,时间复杂度为O(n)
而双向链表有prev前驱节点引用,不需要遍历链表就能直接获取到,删除的时间复杂度为O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13

双向链表的插入操作

同理,如果要在指定节点前插入一个节点,双向链表比单链表更高效
单链表需要O(n)时间复杂度,而双向链表只需要O(1)时间复杂度
1
2

双向链表的查找操作

如果链表的数据是有序的,那么由于双向链表支持两个方向进行遍历,查找效率表单链表更高效
在首次查找中,可以记录本次查找的位置X,每次查询前,将要查找的值与X进行比较,
先确定查找方向后,再进行查找,平均可以少查寻一半的数据
1
2
3

通过以上双向链表和单链表删除,插入,查寻操作的对比
在实际开发中,尽管双向链表比较耗费内存空间,但还是比单链表的应用广泛
实际上,双向链表相对于单链表是一种空间换时间的设计思想

---

六,双向循环链表

在了解了循环列表和双向链表的优势后,将两中优势结合起来,形成双向循环列表

// TODO 双向循环链表图示

---

七,数组VS链表

对比数组和链表两种数据结构可知,他们的插入,删除,随机访问的时间复杂度正好相反
1

// TODO 图示

数组需要使用连续的内存空间,这也使得数组对CPU缓存友好,提高访问效率
链表在内存中并不是连续存储的,所以对CPU不友好,无法有效预读

数组在声明时就要确定大小,所以当内存中没有足够大的连续内存空间时,会导致OOM
当数组使用时,超过申请容量时,只能重新申请更大的空间,并将原数组拷贝到新申请的数组,非常耗时

而链表无需使用连续的内存空间,支持动态扩容,但随机访问效率较低
但链表为了保存后继节点,每个节点都要消耗额外的存储空间存储指向下一个节点的指针,内存会翻倍
而且对链表进行频繁的插入,删除操作,会导致频繁的内存申请和释放,从而导致频繁的GC
1
2
3
4
5
6
7
8
9

---

八,链表实现LRU缓存算法

缓存淘汰策略

缓存是一种以空间换时间的设计思想
如果将数据存储在硬盘上,能节约内存空间,但每次查找数据都需要访问硬盘,效率极底
但如果将数据缓存在内存中,虽然耗费了内存空间,但每次查找数据的效率会大大提高
当缓存被占满时,释放哪些数据,保留哪些数据,这个策略就叫做缓存淘汰策略
1
2
3
4

常见的缓存淘汰策略有三种:

先进先出策略FIFO
最少使用策略LFU
最近最少使用策略LRU
1
2
3

链表实现LRU缓存淘汰算法:

使用链表存储访问记录,较旧的访问存放在靠近链表尾部,当出现新的访问时,从链表头节点遍历链表
如果新访问已经存在,找到它并将它移到链表的头节点(先将原位置删除,再插入链表头部)
如果新访问不存在链表中,需要看链表是否空间已满
如果缓存空间未满,直接插入链表头部
如果缓存空间已满,先删除尾节点(最旧的数据),再将新节点插入链表头部

不管缓存是否已满,都需要遍历链表进行查找,所以缓存访问的时间复杂度为O(n)
1
2
3
4
5
6
7

---

九,书写链表的注意事项

很多面试官喜欢考手写链表代码,例如链表反转等,
因为链表能反映出一个写代码的人是否细心,考虑问题是否全面

1,链表在内存结构上,需要保存其他节点的引用,所以这里需要掌握指针的概念

2,利用哨兵简化实现难度

针对链表的头节点和尾节点要进行特殊处理
利用哨兵,不管链表是否为空,head指针都指向哨兵结点
因为哨兵一直存在,所以插入第一个节点和其他节点,删除第一个节点和删除其他节点,代码实现相同

有哨兵的链表叫做带头链表,没有哨兵的链表叫做不带头链表
1
2
3
4
5

3,边界条件的处理

链表为空时
链表只有一个节点时
链表只有两个节点时
处理头节点和尾节点时
1
2
3
4

4,画图辅助分析

// TODO 画图辅助分析

---

十,结尾

本篇介绍了除数组外的一种基础数据结构-链表
包括单链表,循环链表,双向链表,双向循环链表
以及书写链表的一些注意事项
基于链表的存储结构,链表更适合插入,删除操作频繁的场景

对于执行较慢的程序,可以通过消耗更多的内存来进行优化
而消耗内存过多的程序,可以考虑消耗更多的时间来降低对内存的消耗

---

常见考题:

单链表反转
链表中环的检测
两个有序链表的合并
删除链表倒数第n个节点
求链表的中间节点
1
2
3
4
5