06|循环链表:如何更方便地寻找数据?
王健伟
你好,我是王健伟。
今天我要和你分享的主题是“循环链表”。循环链表可以分为单(单向)循环链表和双(双向)循环链表,只需要在原有单链表或者双链表基础之上做一些比较小的改动即可。
那么,为什么一定要在单链表或者双链表基础上引入循环链表呢?接下来,我们就从它们面临的主要问题出发,分别探讨单循环链表以及双循环链表的相关内容。
单循环链表
这里我们把单循环链表分为两种情况来讨论,第一种情况是传统的单循环链表,第二种情况是改进的单循环链表。它们有什么不同呢?
传统单循环链表
我们说过,单链表的每个节点只有一个后继指针,用于指向后继节点,而最后一个节点的后继指针指向 nullptr(空),想一想,这会有什么不足呢?
没错,如果我们想找某个节点的前趋节点,除非拿到头节点的指针,否则是找不到的。
那么为了解决这个问题,我们就可以引入单循环链表了,它也被称为循环单链表。单循环链表,是在单链表的基础上,将链表中最后一个节点的后继指针由指向 nullptr 修改为指向头节点,从而整个单链表就构成了一个头尾相接的环,这种单链表称为单循环链表。
单循环链表的引入,实现了给定任意一个节点,都可以访问到链表中的所有节点,也就是遍历整个链表的可能。这样,我们就可以从遍历中找到指定节点的前趋节点了。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
循环链表是一种在单向或双向链表基础上引入的数据结构,通过将链表的尾节点指针指向头节点,形成一个头尾相接的环。文章介绍了传统单循环链表和改进的单循环链表两种情况。传统单循环链表解决了在单链表中找到指定节点的前趋节点的问题,而改进的单循环链表则将链表的头指针修改为尾指针,提高了在链表头部和尾部进行数据操作的效率。此外,引入尾指针还可以快速连接两个单循环链表形成更大的链表。文章详细介绍了单循环链表的初始化、判空、遍历、插入、删除等操作的实现方法,并提供了相关代码示例。双循环链表在双链表的基础上引入了环形结构,解决了在双链表中寻找节点的效率问题。文章还提到了链表的实现方法非常多样且非常灵活,需要根据具体的应用场景来决定使用哪种类型的链表来保存数据。总的来说,循环链表的引入可以更方便地寻找数据,提高链表操作的效率。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(3)
- 最新
- 精选
- 阿阳老师好,请问能拓展一些关于“C++ 标准库中提供的容器”的知识吗?比如在这节课的链表,在标准库中的相关的知识的运用。
作者回复: 标准库中的list就是链表啦😁😁
2023-05-16归属地:江苏 - Tokamak老师,文章中介绍的尾指针循环链表感觉怎么和头指针的循环链表一样呢?只是把 m_head 换成了 m_tail, 不是很理解,望老师解惑;
作者回复: 往尾部插入一个节点,如果你用的是头指针,你尝试写段代码实现该功能(你是不是得先想办法找到尾部啊),时间复杂度是多少?如果你用的是尾指针,你同样尝试写段代码实现该功能,时间复杂度又是多少?
2023-03-20归属地:上海 - Sam Jiang老师,在实现尾指针单循环链表的时候,感觉需要同时定义m_tail和m_head,否则头结点不能初始化。但文稿中说的是用m_tail取代m_head,不知道应该如何实现呢?2024-01-01归属地:上海
收起评论