数据结构：循环\双向链表

一、回顾

单链表 是由 一段 连续或不连续 的物理地址来 存储元素 的。通过存储指针的方式，链表的每个结点中都储存了下一个结点元素的地址。另外， 单链表 可以快速的采用 头插法 或 尾插法 来增加新元素。亦可通过交换指针的方式去变更元素的顺序，以及删除一个元素。所以单链表不再需要动用其他元素即可完成以上操作。

二、什么是循环链表

所谓 循环链表 ，就是将单链表的表尾指针从null 指向了表头的地址。从而实现了一个环的形状。其特性仍然和单链表相似，加了这一点点小变动，则称为循环链表。

单链表的表尾指向null，而循环链表的表尾指向表头。

• 单链表判断是否循环完，则判断单链表的指针是否指向null。

• 循环链表判断是否循环完，则判断表尾指向的指针是否是表头的地址。

三、循环链表解决了什么问题

如果要将两个单链表拼接成一个链表会有哪些动作呢？

首先是通过其中一个链表的头指针，逐个循环整个链表的元素，直到取出最后一个元素。 再将其最后一个元素的指针指向另 外一个链表的第一个结点地址即可完成链表的拼接。最后在将第二个链表的表头释放掉。 所以整个拼接的时间是O(n) 。 而这个时间却用在了寻找最后一个元素的结点上。

如果拿到最后一个元素的时间为O(1) 那整个流程的操作效率上来了。所以通过稍加修改单链表成为一个循环链表即可快速实现两个链表的拼接。

p = endA->next; #A的表头地址

endA->next = endB->next->next; # A 和 B 尾首相连

Q = endB->next; #两表相连释放B的头结点地址

endB->next = p; #B的表尾指针指向A的表头地址

free(Q); #释放Q内存

• 将A循环链表的最后一个结点存储的指针给 P。（即A的表头地址）

• 将B循环链表第一个结点的地址 给 A循环链表的最后一个元素的指针 (即尾首相连）

• 将B循环链表的最后一个元素存储的指针头给 Q (即两表相连释放B的头结点地址)

• 将P (A的表头地址) 给 B的循环链表的最后一个结点指针

• 释放Q内存

四、什么是双向链表

已经知道，线性表包含 顺序存储结构 和 链式存储结构 ，其中链式存储结构包含 动态链表 ，和 静态链表 ，以及上文中提到的 循环链表 。在链表的数据结构中目前都是存储了一个指针域。所以对于链表目前只能单方向的向下寻找元素。如果要寻找上一个结点就需要重新循环链表。可见效率是非常低了。所以后面又诞生了一个 双向链表 。

双向链表 是基于单链表的基础上，在每一个结点上扩展了一个 指向前驱结点的指针域。

#线性表的双向链表的存储结构

typedef struct DulNode {

ElemType data;

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

struct DulNode *next; #直接后驱指针

} DulNode, *DuLinkList;

上文说了单链表的循环链表，那么双向链表其实也是可以做双向循环链表的。如下图一个非空的双向循环链表结构图。

双向链表是基于单链表扩展出来的。所以双向链表的创建，插入和删除操作，都类似于单链表。唯一多了一个前驱指针的维护工作和消耗内存的成本。

4.1 双向循环链表插入

举例子，如果需要将a3元素插入在a1 和 a2 两个元素直接，需要做哪些动作呢？

a3->prios = a1; # a3 的前驱指针指向了 a1

a3->next = a1->next; # a3 的下一个指针指向了 a2

a1->next->prios = a3; # a2 的前驱指针指向了 a3

a1->next = a3; # a1 的下一个指针指向了 a3

从上图中可以看到 a1 和 a2 原本由实线连接的需要断开使用了虚线连接。即a1 和 a2 直接插入了一个实线连接的 a3。 整个插入的过程只需要变更结点的前驱指针和后继指针的地址即可。

4.2 双向循环链表删除

举例子，如果需要将a1 和 a3 两个元素之间的 a2 元素删除掉 ，需要做哪些动作呢？

分析，如果要删除a2 元素，就需要修改 a1 的后继地址和 a3 的前驱地址即可

a2->prior->next = a2->next; # 将 a2 的直接前驱结点的 a1 的后继指针指向 a3

a2->next->prior = a2->prior; # 将 a2 的直接后继结点的 a3 的前驱指针指向 a1

free(a2);

总结，双向链表的操作相对单链表的操作要复杂一点，但是都不难。只要在操作的过程中细心一点即可。

另外双向链表所支持的查询结构是比单链表要多些，这也是它拿空间换时间所得来的。

写在最后，目前线性表的这一节到此就结束了，后面将继续跟进数据结构的其他章节。

六、参考文献

《大话数据结构》