004-链表补充之循环链表

循环链表

引言

学校展开了一场夺宝活动,谁获得胜利,就可以得到麦当劳早餐券3个月,大家纷纷参与了进来,一些卡片从校门分别依次放置在下面的建筑中,最快找到的人就赢了,我现在我的宿舍楼下,但是总有想坑你的哥们,他非和你强调卡片是从校门开始放置的,所以我们应该从起点出发,然后逐个找下去,但是我一想,学校是一个环形的,先找哪个不是找,于是我先从宿舍楼开始,接着从食堂开始顺着环形路找下去,很快我就找全了需要的卡片

看似一个很普通的环,却解决了一个大问题,那就是从任意一个节点出发,如何访问到链表的全部节点,这也就是我们今天想要讲的循环链表问题

单向循环链表

单循环链表就是在链表的基础上,通过修改指针域,使得链表的首尾相连,也就是尾节点的指针域指向头结点,形成一个环形的结构

在之前的单链表中,我们所拥有的是头指针,所以我们分别访问头结点和尾节点的时间复杂度为 O(1) 和 O(n) ,那么能不能将访问尾节点的时间复杂度也变为O(1)呢,那么我们就可以这样做:不设置头指针,设置一个指向为节点的尾指针,这样我们对于头尾节点的查找就很方便了,

双向循环链表

同样的,双向循环链表是在双链表的基础上进行改造的,我们将尾节点的后继next指向头结点,而头结点的前驱指向到尾节点,这样一个双联报表的循环状表示就出来了

结尾:

如果文章中有什么不足,或者错误的地方,欢迎大家留言分享想法,感谢朋友们的支持!

如果能帮到你的话,那就来关注我吧!如果您更喜欢微信文章的阅读方式,可以关注我的公众号

在这里的我们素不相识,却都在为了自己的梦而努力 ❤

一个坚持推送原创开发技术文章的公众号:理想二旬不止


   转载规则


《004-链表补充之循环链表》 BWH_Steven 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录