循环链表结构

对于单链表而言,最后一个结点的指针域是空指针。如果将该链表头指针置入该指针域,则使得链表头尾结点相连,就构成了循环单链表,如下图所示:

带头结点的循环单链表:
带头结点的循环单链表

在循环单链表上的操作基本上与非循环链表相同,只是将原来判断指针是否为 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;     //组成循环链表

这一操作过程如下图所示:

两个用尾指针标识的单循环链表的连接:
两个用尾指针标识的单循环链表的连接

用户头像
登录后发表评论