数据结构与算法之链表
缓存淘汰策略：
- 先进先出策略FIFO
- 最少使用策略LFU
- 最近最少使用策略LRU
单链表：
- 非连续存储
- 指针串联
- 结点：内存块
- 后继指针next：记录下个结点地址的指针
- 头结点：第一个结点
- 尾结点：最后一个结点，指针指向空地址 NULL
- 时间复杂度
- 插入、删除O(1)
- 查询O(n)
循环链表：
- 特殊的单链表
- 尾结点指针指向链表头结点
- 适用于存储有循环特点的数据，如约瑟夫问题
双向链表：
- 每个结点有两个指针： 后继指针next 和 前驱指针prev
- 前驱指针prev：指向前面的结点
- 首结点的 prev和尾结点的 next 都指向 NULL
- 插入删除操作比单链表更高效
删除操作：
- 删除结点中给定值的结点
- 单链表和双链表都需要先遍历查找给定值结点O(n)，在删除O(1)，总时间复杂度O(n)
- 删除给定指针指向的结点
- 单链表删除结点需要知道前驱节点，需要在遍历一次O(n)
- 双链表结点中已经保存有前驱节点指针无需从新遍历O(1)
指针（引用）：
- 将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量
哨兵：
- 针对链表的插入、删除操作，需要对插入头结点和尾结点的情况进行特殊处理，而引入的结点。
- 不管链表是否为空，head 指针都会指向这个哨兵结点。
- 哨兵结点不存储数据
- 哨兵结点一直存在，所以插入、删除所有结点，都可以统一为相同的代码实现逻辑。
带头链表
- 有哨兵结点的链表
###如何写出优雅的链表代码？
- 深刻理解指针含义
- 警惕指针丢失与内存泄漏
P->next = x x->next = p->next - 巧用哨兵简化实现难度
- 留意边界条件处理，注意但不限于以下情况代码是否正常工作：
- 链表为空时
- 链表只包含一个结点
- 链表只包含2个结点
- 代码逻辑在处理头结点和尾结点的时候
- 不同场景可能还有不同的边界条件需考虑！
- 举例画图，辅助思考
- 多写多练，熟能生巧
- 单链表反转
- 链表中环的监测
- 两个有序的链表合并
- 删除链表中倒数第n个结点
- 求链表的中间集结点
本文为Larwas原创文章,转载无需和我联系,但请注明来自larwas博客 https://larwas.com
- 上一篇： 数据结构与算法之数组
- 下一篇： 主备切换之GTID
请先登录后发表评论
- latest comments
- 总共0条评论
最新评论