目录
一、循环单链表
二、循环双链表
一、循环单链表
循环单链表的表尾结点的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,双链表的代码↓
文章来源:https://www.toymoban.com/news/detail-483928.html
q结点位于尾结点位置,双链表代码就会出错,而循环链表不会。文章来源地址https://www.toymoban.com/news/detail-483928.html
到了这里,关于循环链表详解(循环单链表/循环双链表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!