数据结构之循环链表

对于单链表,由于每个结点只存储了向后的指针,到了尾标志就停止了向后链的操作,这样,当中某一结点就无法找到它的前驱结点了。

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表(circular linked list)。
为了使空链表与非空链表处理一致,通常设一个头结点。

空循环链表

GWklxu3y9k.png!large

非空循环链表

3ukhWns9n7.png!large

其实循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断 p->next 是否为空,现在则是 p->next 不等于头结点,则循环结束。
在单链表中,有头结点时,可以用 O(1) 的时间访问第一个结点,但对于要访问到最后一个结点,却需要 O(n) 时间,因为需要将单链表全部扫描一遍。

用指向终端结点的尾指针来表示循环链表,此时查找开始结点和终端结点都很方便了。

lurC0Eq8mx.png!large

终端结点用尾指针 rear 指示,则查找终端结点是 O(1),而开始结点其实就是 rear->next->next,其时间复杂度也是 O(1)。

案例:将两个循环列表合并成一个表
JJfNv0GXfN.png!large
上图中,他们的尾指针分别是 rearA 和 rearB。
G4ItYZfovo.png!large
上图的步骤完成了两个表的合并。

ai
本作品采用《CC 协议》,转载必须注明作者和本文链接
不要试图用百米冲刺的方法完成马拉松比赛。
本帖由 Galois 于 1个月前 加精
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!