循环链表详解(循环单链表/循环双链表)

这篇具有很好参考价值的文章主要介绍了循环链表详解(循环单链表/循环双链表)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、循环单链表

二、循环双链表


一、循环单链表

循环单链表的表尾结点的next指针总是指向头结点。 

循环链表详解(循环单链表/循环双链表)

所以在初始化循环单链表的时候,需要记得将头结点的next指针指向头结点自己:

循环链表详解(循环单链表/循环双链表)

 

判断循环单链表是否为空,只要判断头结点的next指针是否指向自己就可以了,因为循环链表的最后一个结点的next指针总是指向头结点的,如果为空,那就只能是头结点的next指针指向自己了:

循环链表详解(循环单链表/循环双链表)

判断结点是否是循环单链表的表尾结点,只需判断该结点的next指针是否指向头结点即可,因为循环链表的最后一个结点的next指针总是指向头结点的:

循环链表详解(循环单链表/循环双链表)

 

循环单链表有一些重要的性质:1、从一个结点出发,无论这个结点位于链表的哪里,都可以找到其他任何一个结点,而单链表不行。

2、在一些情况下,我们需要频繁对链表的头部和尾部进行操作,此时使用循环单链表就很有用,原因是对于单链表,已知头结点,想找到最后一个结点的话,时间复杂度是O(n);但是对于循环单链表,我们可以一开始就把头指针指向尾结点,这样找到尾结点所需时间复杂度是O(1),因为尾结点的next指针总是指向头结点,所以找到头结点的时间复杂度也是O(1)。因此,循环单链表在这种情况下的表现明显优于普通的单链表。

二、循环双链表

先拿双链表和循环双链表做个对比:

双链表:

循环链表详解(循环单链表/循环双链表)

 循环双链表:循环链表详解(循环单链表/循环双链表)

 

在初始化循环双链表的时候,需要记得将头结点的前指针和后指针都指向头结点自己:

循环链表详解(循环单链表/循环双链表)

 像这样↓

循环链表详解(循环单链表/循环双链表)

 

根据以上性质,所以在判断循环双链表是否为空时,只需判断头指针的next指针是否指向头结点自身即可:

循环链表详解(循环单链表/循环双链表)

 

判断当前结点时都是循环双链表的表尾结点,只要判断当前节点的next指针是否指向头结点即可:

循环链表详解(循环单链表/循环双链表)

 

下面来看一下双链表和循环双链表在插入与删除上的区别:

p结点之后插入s结点,双链表的代码是这样的:

循环链表详解(循环单链表/循环双链表)

有一个明显的缺陷,即当p结点正好是尾结点的话,代码的第二句"p->next->piror=s"会出错,因为p->next指向NULL; 但是如果是循环双链表的话,上述代码就是正确的,因为循环双链表中,即使p是尾结点,它的next指针的指向也是非空的,因此就不会出错了。

同理当删除p的后继节点q,双链表的代码↓

循环链表详解(循环单链表/循环双链表)

 q结点位于尾结点位置,双链表代码就会出错,而循环链表不会。文章来源地址https://www.toymoban.com/news/detail-483928.html

到了这里,关于循环链表详解(循环单链表/循环双链表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-单链表-双链表

    “收藏从未停止,练习从未开始”,或许有那么一些好题好方法,在被你选中收藏后却遗忘在收藏夹里积起了灰?今天请务必打开你沉甸甸的收藏重新回顾,分享一下那些曾让你拍案叫绝的好东西吧! H x ,表示向链表头插入一个数 x。 D k ,表示删除第 k 个插入的数后面的数

    2024年02月15日
    浏览(54)
  • 【数据结构】单链表 && 双链表(链式和数组实现)

           🔥🔥 欢迎来到小林的博客!!       🛰️博客主页:✈️小林爱敲代码       🛰️博客专栏:✈️ 数据结构与算法       🛰️社区 :✈️ 进步学堂       🛰️欢迎关注:👍点赞🙌收藏✍️留言 今天给大家带来四个内容,一个

    2024年02月01日
    浏览(52)
  • 【算法基础】数据结构| 单链表+双链表 代码实现+图解+原理

    博主简介: 努力学习的预备程序媛一枚~ 博主主页: @是瑶瑶子啦 所属专栏: Java岛冒险记【从小白到大佬之路】 因为瑶瑶子正在备战蓝桥杯和校内ACM选拔赛,最近在学习算法相关的知识。我是借助 AcWing网站 来学习的,这篇文章是我学习就我学习内容的一个笔记,其中的一些

    2024年02月01日
    浏览(57)
  • 【数据结构】链表(单链表与双链表实现+原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月24日
    浏览(123)
  • 【玩转408数据结构】线性表——双链表、循环链表和静态链表(线性表的链式表示 下)

            在前面的学习中,我们已经了解到了链表(线性表的链式存储)的一些基本特点,并且深入的研究探讨了单链表的一些特性,我们知道,单链表在实现插入删除上,是要比顺序表方便的,但是,单链表中每个结点仅存在一个指针指向其后续结点,那么如果我们想要找

    2024年04月10日
    浏览(57)
  • 单链表与循环链表创建

    单链表 实现 错例 在使用malloc函数开辟的空间中,不要进行指针的移动, 因为一旦移动之后可能出现申请的空间和释放空间大小的不匹配 循环链表 单独创建 实现方式一: 实现方式二:

    2024年01月18日
    浏览(29)
  • 单向-->不带头-->非循环链表(简称:单链表)

    目录 一、链表的介绍 1.链表的概念 2.单链表的节点类型 3.单链表简图 二、单链表的增删查改 1.单链表的头插 2.单链表的尾插 3.单链表的头删 4.单链表的尾删 5.单链表pos位置之后插入一个节点 6.单链表删除pos位置后的一个节点         链表是一种物理存储结构上非连续、非顺

    2024年02月13日
    浏览(40)
  • 当我与单链表分手后,在酒吧邂逅了双向循环链表.....

    链表的种类有8种,但我们最常用的为 无头单向非循环链表 和 带头双向循环链表 。 带头双向循环链表  当带头双向循环链表只有 哨兵位头 的时候,双向链表的指向如下图。 head-pre和head-next都是指向自己,这个是有巨大优势的,代码实现会很方便。  1. 无头单向非循环链表

    2024年02月05日
    浏览(30)
  • [C语言实现]带你手撕带头循环双链表

    目录 什么是双链表? 带头结点的优势: 双链表的实现: 众所周知,顺序表的插入和删除有时候需要大量移动数据,并且每次开辟空间都可能会浪费大量内存和CPU资源,于是我们有了链表,我们之前已经实现了单链表,我们可以发现单链表的一个劣势——每次查找都必须从头结

    2024年02月06日
    浏览(40)
  • 【数据结构】 循环双链表的基本操作 (C语言版)

    目录 一、循环双链表 1、循环双链表的定义: 2、循环双链表的优缺点: 二、循环双链表的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、循环双链表的初始化  4、循环双链表按位查找 5、循环双链表插入 6、循环双链表查找 7、循环双链表删除 8、求循环双链表长

    2024年01月22日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包