循环列表和双向列表

本文围绕以下两个部分展开：

一、循环链表（circular linked list）
二、双向链表（double linked list）






一、循环链表（circular linked list）

        1. 概念

        将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

        2. 与单链表比较

        （1）单链表，每个元素只存储了向后的指针，到了尾标志就停止了向后链的操作。这样，当中某一结点就无法找到它的前驱结点。

        循环链表可以从当中一个结点出发，访问到链表的全部结点。

        （2）循环的判断条件上有差别：单链表：判断p->next是否为空；循环链表：判断p->next是否等于头结点。


        3. 改造：不用头指针，用尾指针好。

        （1）用头指针：可以用O(1)的时间访问开始结点，但访问终端结点由于需要将链表全部扫描一遍，因此需要O(n)的时间。

        而用尾指针访问开始结点和终端结点都用O(1)的时间。

        （2）要将两个循环链表合并为一个表时，有了尾指针就非常简单了。

二、双向链表（double linked list）

        1. 概念

        双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。


        2. 双向链表存储结构

        3. 插入

        4. 删除

        5. 双向循环链表（双向链表带有循环）

整理时重点参考：《大话数据结构》程杰著