这篇文章开启线性表的大版本更新2.0----循环链表
单循环链表
由前面关于单链表的介绍我们知道，在单链表中每个结点都只存储了下一个结点的存储地址，直到尾结点为 NULL，我们很容易地找到当前结点的后继结点，但是我们无法找到某一结点的前驱结点
我们先来看看循环链表的定义：
将单链表中尾结点的指针由空指针改为指向头结点，使整个链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
循环链表的出现解决了一个问题：如何从单链表的某一个结点出发访问到整个链表的全部结点
为了使空链表和非空链表处理一致，通常我们会设置一个头结点，循环链表带有头结点的空链表如下：
QQ20200704-170130@2x.png
对于非空的循环链表如下图所示：
QQ20200704-172002@2x.png
循环链表和单链表的主要差异在于循环的判断上，原来是判断 p->next 是否为空，现在则是判断 p->next 不等于头结点，则循环未结束
在单链表中，如果我们要想访问到最后一个结点，则需要 O(n) 的时间，因为我们需要把整个链表循环一遍
有没有可能在 O(1) 的时间由链表指针访问到最后一个结点?
这里需要改造一下循环链表，我们不再使用头指针表示链表，改用指向链表尾部结点的尾指针来表示循环链表，如下图所示：
QQ20200704-175030@2x.png
从上图可以看出，尾部结点用尾指针 rear 表示，则查找尾结点是 O(1)，而开始结点，其实就是 rear->next->next，时间复杂度也是 O(1)
下面有两个循环链表 A、B，要将两个循环链表合并成一个链表，这两个循环链表的尾指针分别是 rearA 和 rearB，如下图所示：
QQ20200704-180357@2x.png
要想把 A、B 合并，只需要执行下面的操作即可：
QQ20200704-180502@2x.png
p = rearA->next; // 保存 A 表的头结点
rearA->next = rearB->next->next;// 将 B 表的第一个结点(不是头结点) 变成 A 表尾指针的后继结点
rearB->next = p;// 将 A 表的第一个结点变成 B 表尾指针的后继结点
双循环链表
在单链表中，有了 next 指针，使得我们查找下一个结点的时间复杂度为 O(1)，如果要想查找上一个结点，那么最坏的时间复杂度是 O(n)，因为我们需要从头开始遍历查找
，那么如果更加高效的查找某一结点的前驱结点呢?在这里我们引入 双向链表 的概念
双向链表是在单链表的每个结点中再设置一个指向其前驱结点的指针域
所以，在双向链表中的结点都有两个指针域，一个指向其直接后继，另一个指向其直接前驱，双向链表结构使用 C 语言结构体指针表达如下：
typedef struct DulNode
{
ElemeType data;
struct DulNode *prior;// 直接前驱结点指针
struct DulNode *next;// 直接后继结点指针
}DulNode, *DulLinkList;
单链表可以有循环链表，那么双向链表也可以是循环链表
双向链表的循环带有头结点的空链表如下图所示：
QQ20200704-192931@2x.png
双向链表的循环带有头结点的非空链表如下图所示：
QQ20200704-193218@2x.png
由于这是双向链表，那么对于链表中的某一个结点 p，它后继的前驱 和 它前驱的后继自然都是它自身
p->next->prior = p = p->prior->next;
下面我们看下双向链表比着单链表在插入和删除结点方面的不同
插入
假设存储数据元素 e 的结点为 s，现在要实现把结点 s 插入到结点 p 和 p->next 之间，如下图所示：
QQ20200704-200310@2x.png
先看下如果是单链表情况下如何实现：
s->next = p->next;// 结点 p 的后继结点变成结点 s 的后继结点
p->next = s;// 结点 s 变成 p 的后继结点
下面看看双向链表如何实现：
s->prior = p;// 将结点 p 变成结点 s 的前驱
s->next = p->next;// 将结点 p 的后继结点变成结点 s 的后继结点
p->next->prior = s;//将结点 p 的后继结点的前驱变成结点 s
p->next = s;//将结点 s 变成结点 p 的后继结点
一定要注意上面的执行顺序，如果执行完第一步后就执行第四步，那么 p->next 提前变成了结点 s，这个时候插入操作就不能完成了
删除
如下图所示，实现删除结点 p：
QQ20200704-201332@2x.png
先看下单链表如何实现：
p->prior->next = p->next;// 将结点 p 的后继结点变成结点 p 前驱的后继结点
下面看看如果是双向表如何实现：
p->prior->next = p->next;// 将结点 p 的后继结点变成结点 p 前驱的后继结点
p->next->prior = p->prior;//将结点 p 前驱变成结点 p 后继结点的前驱
free(p);释放结点 p
总结
双向链表相对单链表来说更加复杂一些，毕竟多了一个前驱指针，尤其是在插入和删除操作时主要多注意执行顺序，另外由于其每个结点包含两个指针，所以在空间上占用多一些。不过由于双向表的对称性，使得对某个结点的前后结点操作比较方便，提高了算法的时间性能，其实就是用空间换时间
网友评论