本文共 595 字，大约阅读时间需要 1 分钟。

（转自：）

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

一、循环链表（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. 双向循环链表（双向链表带有循环）   

 

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

转载地址：http://qyqkb.baihongyu.com/