数据结构之循环链表

循环链表

一、什么是循环链表

循环链表：是一种头尾相接的链表（即：表中的最后一个结点的指针域指向头结点，整个链表形成一个环）。

优点:从表中的任意结点出发均可找到表中的其他结点。
注：循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断它们是否等于头指针。


头指针表示单循环链表：
找a1的时间复杂度：O(1)
找an的时间复杂度：O(n)
尾指针表示单循环链表：
a1的存储位置是：R->next->next
an的存储位置是：R
时间复杂度均为O(1)

二、如何将带尾指针的单循环链表合并

操作：

• 将Tb合并在Ta之后
• Tb表头连接到Ta表尾，释放Tb表头结点
• 修改指针
  代码如下：

p=Ta->next;
Ta->next=Tb->next->next;
delete Tb->next;
Tb->next=p;
1
2
3
4

三、双向循环链表

和单链的循环链表类似，双向链表也可以有循环链表。

• 让头结点的前驱指针指向链表的最后一个结点
• 让最后一个结点的后继指针指向头结点。
  
  与非循环双链表相比，循环双链表：
• 链表中没有空指针域
• p所指结点为尾结点的条件：p->next=L
• 一步操作即L->prior可以找到尾结点。