快速上手 C++ 数据结构与算法
王健伟
《C++ 新经典》系列作者,资深 C++ 讲师
3224 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 55 讲
结束语 (1讲)
快速上手 C++ 数据结构与算法
15
15
1.0x
00:00/00:00
登录|注册

06|循环链表:如何更方便地寻找数据?

你好,我是王健伟。
今天我要和你分享的主题是“循环链表”。循环链表可以分为单(单向)循环链表和双(双向)循环链表,只需要在原有单链表或者双链表基础之上做一些比较小的改动即可。
那么,为什么一定要在单链表或者双链表基础上引入循环链表呢?接下来,我们就从它们面临的主要问题出发,分别探讨单循环链表以及双循环链表的相关内容。

单循环链表

这里我们把单循环链表分为两种情况来讨论,第一种情况是传统的单循环链表,第二种情况是改进的单循环链表。它们有什么不同呢?

传统单循环链表

我们说过,单链表的每个节点只有一个后继指针,用于指向后继节点,而最后一个节点的后继指针指向 nullptr(空),想一想,这会有什么不足呢?
没错,如果我们想找某个节点的前趋节点,除非拿到头节点的指针,否则是找不到的。
那么为了解决这个问题,我们就可以引入单循环链表了,它也被称为循环单链表。单循环链表,是在单链表的基础上,将链表中最后一个节点的后继指针由指向 nullptr 修改为指向头节点,从而整个单链表就构成了一个头尾相接的环,这种单链表称为单循环链表。
单循环链表的引入,实现了给定任意一个节点,都可以访问到链表中的所有节点,也就是遍历整个链表的可能。这样,我们就可以从遍历中找到指定节点的前趋节点了。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

循环链表是一种在单向或双向链表基础上引入的数据结构,通过将链表的尾节点指针指向头节点,形成一个头尾相接的环。文章介绍了传统单循环链表和改进的单循环链表两种情况。传统单循环链表解决了在单链表中找到指定节点的前趋节点的问题,而改进的单循环链表则将链表的头指针修改为尾指针,提高了在链表头部和尾部进行数据操作的效率。此外,引入尾指针还可以快速连接两个单循环链表形成更大的链表。文章详细介绍了单循环链表的初始化、判空、遍历、插入、删除等操作的实现方法,并提供了相关代码示例。双循环链表在双链表的基础上引入了环形结构,解决了在双链表中寻找节点的效率问题。文章还提到了链表的实现方法非常多样且非常灵活,需要根据具体的应用场景来决定使用哪种类型的链表来保存数据。总的来说,循环链表的引入可以更方便地寻找数据,提高链表操作的效率。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《快速上手 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归属地:上海
收起评论
显示
设置
留言
3
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部