循环链表详解(循环单链表/循环双链表)
赞
踩
目录
一、循环单链表
循环单链表的表尾结点的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结点位于尾结点位置，双链表代码就会出错，而循环链表不会。
