hello,everybody,今天我们来学习线性表的最后两种形式，循环链表、双向链表。这两种链表，是链式存储结构的不同形式。书归正传，我们先来看看循环链表吧。

大家思考一个问题，我们把线性表各个元素比作下图的路线图上的城市:

我们的线性表各个结点的指针，都是指向唯一的后继结点，线性表的终端结点的指针为空。这样的话，如果我们在南京，我们需要先访问南京右j边的城市，再访问南京左边的城市。根据线性表的结构，我们只能返回上海，从上海依次访问到北京。因为我们的终端结点的指针为空，如果直接访问南京右边的城市，那么到北京后，就断片儿了，也就不能访问南京左边的城市了。现实生活中，如果我们选择这样的路线的话，估计要被大家笑掉大牙了。

这时候，我们的循环链表就出世了。我们把北京与上海连起来，这样就Ok了。其实，就是把线性表的终端结点的指针指向线性表的第一个结点。让线性表，联通起来，成为循环的链表。

循环链表:将单链表中终端结点的指针端由空指针改为指向头结点，就使得整个单链表成为一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linked list).

从刚才的例子中，我们可以发现，循环链表解决了一个严重的问题。它的出现，使得我们可以从当中一个结点遍历整个线性表。

为了使空循环链表与非空循环链表操作一致，我们通常会在线性表中设立空结点。空结点对于循环链表不是必须的，它的出现只是为了统一操作。

空的带有头结点的循环链表。

非空的带有头结点的循环链表。

其实，单链表与循环链表的区别，在于判断上。单链表是判断p->next不为空，则说明遍历未结束。循环链表判断p->next为头结点，则循环未结束。

在单链表中，我们通过头指针可以花费O【1】的时间复杂度访问到第一个元素结点。但是需要遍历整个链表，花费O【n】的时间复杂度，才可以访问到终端结点。

现在我们可以修改一下链表，使得也可以花费O[1]的时间复杂度访问到终端结点。不同的之处在于，我们不用头指针，而用尾指针来指向终端结点。

从上图我们看以看出，通过尾指针rear，我们可以花费O【1】的时间复杂度访问到终端结点。而对于开始结点，其实就是rear->next->next.时间复杂度也为O【1】.

以上就是循环链表，它的出现就是为了解决从中间元素访问整个链表的问题。

我们来看一下双向链表:

还是刚才那幅图:

我们在北京开完会，需要走访北京左边的所有城市。根据我们学到的线性结构，只能先到上海， 在由上海开始依次到北京，再从北京到上海。此时，双向链表就诞生了。

单链表查找下个元素的时间复杂度为O【1】，查找上一个元素的时间时间复杂度为O【n】，因为需要我们遍历整个链表。为了克服这个弊端，设计了双向链表。双向链表（double linked list），是在单链表的每个结点中，再设置一个指向前驱结点的指针域。

我们看一下它的代码结构:

typedef struct DulNode

{

     ElemType data;

    struct DulNode *prior ; /*直接前驱指针*/

   struct  DulNode *next;  /*直接后继指针*/

}DulNode,*DuLinkList;

既然单链表有循环链表，那么双向链表也有循环链表。

双向链表的循环带头结点的空链表。

双向链表的循环带头结点的非空链表

关与它的一些操作，与之前的单链表很相似。

以上就是双向表的知识。

好了，让我们一起来总结一下线性表这章知识吧。

首先，我们先学习了线性表的概念，线性表就是零个或多个具有相同类型的数据元素的有限序列。接下来，我们从存储结构上，分别讲解了线性表的顺序存储，与线性表的链式存储。其中，链式存储结构中，我们又学习了循环链表与双向链表。另外，我们还学习了不用指针来描述链式存储的静态链表。

在学习总结线性表这张章时，发现了自己身上很多性格缺点。在写博客文章时，有些浮躁。好多东西，都是复制粘贴，不经过大脑思考。做人，学技术，一定要实在。不能贪图虚名，不能浮躁。

一定要有耐心，有毅力，有决心。在接下来的学习中，一定要锻炼自己这耐心、毅力、决心。