对于单链表而言,最后一个结点的指针域是空指针。如果将该链表头指针置入该指针域,则使得链表头尾结点相连,就构成了循环单链表,如下图所示:
带头结点的循环单链表:
在循环单链表上的操作基本上与非循环链表相同,只是将原来判断指针是否为 NULL 变为是否是头指针,没有其他较大的变化。
对于单链表,只能从头结点开始遍历整个链表;而对于循环单链表,则可以从表中任意结点开始遍历整个链表。
不仅如此,有时对链表常做的操作是在表尾、表头之间进行。此时可以改变链表的标识方法,不用头指针而用一个指向尾结点的指针 R 来标识,可以使操作效率得以提高。
例如,对两个循环单链表 H1、H2 的连接操作,是将 H2 的第一个数据结点接到 H1 的尾结点。如用头指针标识,则需要找到第一个链表的尾结点,其时间复杂度为 O(n);而链表若用尾指针 R1、R2 标识,则时间复杂度为 O(1)。操作如下:
p = R1–>next; //保存 R1 的头结点指针
R1->next = R2->next->next; //头尾连接
delete R2->next; //释放第二个表的头结点
R2->next = p; //组成循环链表
这一操作过程如下图所示:
两个用尾指针标识的单循环链表的连接: