一、单链表的缺陷以及双向链表的引入
1.单链表的缺陷
在我们上一节内容中，我们已经学会了单链表的一些基本操作，但是呢其实我们也发现了单链表有很大的缺陷，我们在实现尾插，尾删，在pos前一个位置进行插入，删除pos位置，这几个接口的实现都需要找到前一个结点，而我们找到前一个结点的方法只能是遍历，而且还得分情况，看看空链表会出现什么情况，只有一个结点的链表又会是什么情况。总之很麻烦
如上图所示，无论是PopBack、Insert、还是Erase时间复杂度都达到了O(N)，效率不高。
究其根本原因是因为，无法实现从后找前，找不到前驱，必须从头开始遍历寻找
2.双向链表的引入
那么如何解决这种现象呢？答案是采取双向的链表，让它可以从后找到前一个结点。
这样的话，那么我们链表的声明就应该是这样的
代码为
typedef int LTDateType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDateType date; }ListNode;
3.八大链表结构
在这里就不得不提一下链表的种类了，链表共有八种。而八种是由三种属性来排列组合形成的
1.单向 双向
2.不带头 带头
3.不循环 循环
如上的三种属性，经过排列组合后刚好可以形成八种结构，而我们上节所说的正是单向不带头不循环链表
（1）单向和双向
单向和双向其实在前面已经说过了。就是一个双向弥补了单向找前一个结点比较麻烦的现象
（2）带头和不带头
什么是带头什么又是不带头呢？我们看下面的图就知道了
这就是两个最明显的区别了，带头的链表比不带头的链表多一个结点，而这个结点其实是不存储有效数据的，它是一个哨兵位
带头结点的好处：
不需要改变传过来的指针，也就是意味着不需要传二级指针
为什么步不需要传二级指针呢，我们可以画图来理解一下
这是普通的不带头链表传参图，我们其实可以看出来，其实plist传参的时候会拷贝成phead，然后我们改变的连接都是phead和newnode的结构，而非plist，因为plist和phead是两个不同的变量，他们的地址都不一样
而如果是带头结点的，我们也画图来理解一下
这样形参和实参即便不一样也无所谓了，因为是我们的哨兵位来控制我们的链表的，plist和phead仅仅只是为了找到这个哨兵位。
哨兵位不存储有效数据的的原因：
我们有时候会在书上看到哨兵位存储一个数据，这个数据是代表着有几个结点了。其实这是经典的错误标准的零分，这里是绝对不可以存储这个链表有几个有效数据了，因为假如说我们链表的数据是char类型，那么它最大就是127啊。假如说链表的长度是129呢？显然着哨兵位就不可以存储数据
（3）循环和不循环
这个就比较简单了，不循环的链表最终指向NULL，而循环的链表最后一个结点又指向了头节点
（4）八种链表结构
三大属性我们都有所了解了，那么它的链表就可由这三种排列组合形成八种链表结构。
单向不带头不循环链表 单向不带头循环链表
单向带头不循环链表 单向带头循环链表
双向不带头不循环链表 双向不带头循环链表
双向带头不循环链表 双向带头循环链表
但是我们常用的就两种链表：
1.单向不带头不循环链表：（在上一篇文章中已经实现了）
结构简单，一般不会单独用来存储数据。实际中更多的是作为其他数据结构的子结构。如哈希桶，图的邻接表等
2.双向带头循环链表：
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。
当然，我们本节也就是来实现这个双向带头循环链表了，它的图示应该是这样的
二、带头双向循环链表的实现
1.链表创建
这个就很简单了，我们直接定义一个结点指针让他指向空即可
2.链表的初始化
我们先来声明一下这两个函数
我们先来实现初始化函数，销毁链表的函数在后面实现
我们想一下，这个带头的循环双向链表初始化后应该是什么样子呢？
它应该是这样的，它只有一个结点，而这个结点就是哨兵位，这个哨兵位的prev和next还得自己指向自己，而且plist还得指向这个哨兵位
那么我们现在就来实现它吧，我们会发现，我们想要初始化，那么必须得需要创建一个新的结点出来，但是我们知道后面还有尾插，头插等都需要创建新的结点，不妨我们直接将创建结点写成一个函数
//创建一个新结点 ListNode* BuyListNode(LTDateType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->date = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
这样我们的结点就创建好了，那么我们接下来就是来完善这个初始化，如下图所示
当然，细心的人已经发现问题了，这里肯定是行不通的，因为phead是形参，最终的结果是让phead给初始化了，而plist没有被初始化，所以我们这里应该传二级指针。而之前所说的双向循环带头链表不需要二级指针指的是除过哨兵位以外的结点，因为哨兵位还是需要和plist连接起来的，而其他的操作只需要能找到这个哨兵位就可以了
当然我们也可以不通过修改二级指针的方法来完成这个代码，我们可以这样做，我们也不进行传参了，我们初始化好这个链表之后将这个结点的地址给返回去，然后赋值给plist
这样的话我们的声明也会被改变了
代码为
//创建一个新结点 ListNode* BuyListNode(LTDateType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->date = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //初始化链表 ListNode* ListInit() { ListNode* phead; phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }
2.尾插
对于尾插我们先声明它的函数
//链表的尾插 void ListPushBack(ListNode* phead, LTDateType x);
我们这这样想的，假设原来的是我们下图的连接
我们现在想要尾插一个4过去，那么我们首先要创建这个4的这个结点
然后我们需要的是连接这些点，我们现在有的是4的地址newnode，和哨兵位的地址phead
而我们想要找到尾的话也很简单，因为我们现在是双向的，所以tail=phead->prev
有了这三个地址，接下来就是连接了
我们先让tail->next=newnode
然后让newnode->prev=tail
这样tail和newnode的连接就完成了
然后是newnode和phead的连接，我们先让newnode->next=phead
接下来是phead->prev=newnode
当然我们里面创建结点的时候，不要忘记把4改成了x
我们发现这个代码其实比单链表的尾插要简单了许多，虽然结构复杂了，但是实现变得简单了。而且这个也不用判断为空链表会怎么样。
当然在这里，我们也知道phead是一定不为空的，所以我们也可以加上一句断言
//链表的尾插 void ListPushBack(ListNode* phead, LTDateType x) { assert(phead); //创建一个新的结点 ListNode* newnode = BuyListNode(x); //寻找末尾结点 ListNode* tail = phead->prev; //连接 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
3.打印链表
我们已经写完了尾插，那么我们肯定希望能够测试一下，那么我们不得不先写一个打印链表的功能来测试一下了
打印的功能也很简单，我们定义一个cur，并让他一开始指向phead->next，也就是第一个结点，然后只要此时的cur和phead不一样，那么我们就可以继续打印。这也是利用了循环的特性
这样的话我们的代码实现如下
代码如下
//链表的打印 void ListPrint(ListNode* phead) { //当前的要指向链表的第一个结点，也就是哨兵位的下一个结点 ListNode* cur = phead->next; //判断cur是否为哨兵位，如果不是哨兵位，则打印，是哨兵位 //则说明循环已经遍历完了 while (cur != phead) { printf("%d ", cur->date); cur = cur->next; } printf("\n"); }
而且这个代码即便是空链表，也没有任何问题的。因为如果没有有效结点的话，那么phead->next还是phead，所以根本不会打印的
那么我们现在来测试一下尾插和打印吧，圆满的完成了我们的需求
4.实现头插
我们现在来实现一下头插吧，下面是函数的声明
//链表的头插 void ListPushFront(ListNode* phead, LTDateType x);
然后我们来用这个图来演示一下，我们想要在这里面插入0这个结点
那么首先我们肯定得为0创建它的结点
然后就是开始连接了
我们先记录下来原来的第一个结点
然后我们开始连接
对于这个连接其实对于顺序没有什么要求
我们先连接这两个
然后连接这两个
然后连接这两个
最后连接这两个
最后在加上断言
我们这里刚刚写错了，下面红圈已经改为正确了
我们测试一下
符合我们的逻辑，而且这个函数对于空的链表也是可以连接起来的
代码为
//链表的头插 void ListPushFront(ListNode* phead, LTDateType x) { assert(phead); //为x创建一个结点 ListNode* newnode = BuyListNode(x); //先记录一下原来的第一个结点 ListNode* first = phead->next; //连接 phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
然后再这里我们在上面说了，那个是我们定义了first去记录了之前的第一个结点，然后才会使得连接顺序可以无所谓的。但是万一我们要是没有定义这个first的话，我们再去连接就必须得注意一下顺序，否则会出问题的，在这里给出顺序的图解和代码
然后我们测试运行一下
结果是正确的
要考虑顺序的代码为
//链表的头插(需要考虑顺序的话) void ListPushFront(ListNode* phead, LTDateType x) { assert(phead); ListNode* newnode = BuyListNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; }
其实就是先连接后面的，然后连接前面的，因为如果先连前面的话，就会找不到后面的结点
5.链表的头删
先写出函数声明
//链表的头删 void ListPopFront(ListNode* phead);
我们接下来来实现，对于这个图而言，我们想要删掉头节点，那么其实就相当于将第一个结点给销毁掉，连接起来phead和第二个结点
如下所示就是头删代码的实现，当然也要为了防止链表没有数据的时候删除掉哨兵位。
测试如下
代码为
//链表的头删 void ListPopFront(ListNode* phead) { assert(phead); //这是避免删掉我的哨兵位 assert(phead->next != phead); //第一个结点的地址 ListNode* first = phead->next; //第二个结点的地址 ListNode* second = first->next; //连接 phead->next = second; second->prev = phead; //释放第一个结点 free(first); first = NULL; }
6.链表的尾删
其实链表的尾删和头删除基本一致
下面是函数的声明
//链表的尾删 void ListPopBack(ListNode* phead);
测试结果为
代码为
//链表的尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); //定义倒数第一个结点 ListNode* tail = phead->prev; //定义倒数第二个结点 ListNode* prev = tail->prev; //连接 phead->prev = prev; prev->next = phead; //销毁原来的结点 free(tail); tail = NULL; }
7.链表的查找与修改
我们接下来先来实现链表的查找
下面是函数的声明
//查找某一个值的结点地址 ListNode* ListFind(ListNode* phead, LTDateType x);
然后我们是这样思考的，我们定义一个cur指针，让它一开始指向phead->next，也就是第一个结点，让cur一直往下走，当cur不等于phead的时候，让他继续遍历，一旦找到则返回cur，否则就是没找到，返回NULL
代码如下
//查找某一个值的结点地址 ListNode* ListFind(ListNode* phead,LTDateType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->date == x) { return cur; } cur = cur->next; } return NULL; }
我们来测试一下
符合我们的预期，那么如果我们想要修改我们找到的这个数据该如何做的？其实很简单，因为已经有这个指针了，直接修改就可以了
也就是说，查找功能附带着修改功能
8.在pos之前插入一个数据
这个其实也是与查找函数紧密相连，先用查找找到pos，然后才能进行修改
而它的实现其实与头插，尾插基本一致
它的声明为
//在pos之前插入一个值 void ListInsert(ListNode* pos, LTDateType x);
它的实现为
//在pos之前插入一个值 void ListInsert(ListNode* pos, LTDateType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); newnode->next = pos; pos->prev = newnode; prev->next = newnode; newnode->prev = prev; }
测试为
9.删除pos位置的值
这个也与尾删头删基本一致
下面是函数的声明
//删除pos处的值 void ListErase(ListNode* pos);
函数的实现为
//删除pos处的值 void ListErase(ListNode* pos) { assert(pos); ListNode* next = pos->next; ListNode* prev = pos->prev; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
测试为
在这里我们其实也能发现，其实Insert和Erase完全可以替代头插尾插头删尾删
10.链表的销毁
这是最后一个接口，我们直接销毁掉整个链表即可
函数声明为
//链表的销毁 void ListDestory(ListNode* phead);
思想是，设置一个cur，让他去遍历整个链表，只要cur！=phead，那么就销毁这个空间。
代码为
//链表的销毁 void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; }
三、双向带头循环链表的完整代码
我们现在所有的接口都已经实现了，那么其实我们也能发现这个双向带头循环链表的时间复杂度都是O(1)，（除过查找以外，查找后续会有更优的写法）
完整代码如下：
test.c文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" void TestList1() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 5); ListPushFront(plist, 6); ListPushFront(plist, 7); ListPushFront(plist, 8); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListPopBack(plist); ListPrint(plist); ListNode* pos = ListFind(plist, 3); if (pos) { //查找并修改 pos->date *= 10; printf("找到了,它乘10以后是%d\n",pos->date); } else { printf("没找到\n"); } ListPrint(plist); ListInsert(pos, 300); ListPrint(plist); ListErase(pos); ListPrint(plist); ListDestory(plist); } int main() { TestList1(); return 0; }
List.h文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDateType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDateType date; }ListNode; //链表的初始化 ListNode* ListInit(); //链表的销毁 void ListDestory(ListNode* phead); //链表的打印 void ListPrint(ListNode* phead); //链表的尾插 void ListPushBack(ListNode* phead, LTDateType x); //链表的头插 void ListPushFront(ListNode* phead, LTDateType x); //链表的头删 void ListPopFront(ListNode* phead); //链表的尾删 void ListPopBack(ListNode* phead); //查找某一个值的结点地址 ListNode* ListFind(ListNode* phead, LTDateType x); //在pos之前插入一个值 void ListInsert(ListNode* pos, LTDateType x); //删除pos处的值 void ListErase(ListNode* pos);
List.c文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" //创建一个新结点 ListNode* BuyListNode(LTDateType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->date = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //初始化链表 ListNode* ListInit() { ListNode* phead; phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; } //链表的销毁 void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; } //链表的打印 void ListPrint(ListNode* phead) { //当前的要指向链表的第一个结点，也就是哨兵位的下一个结点 ListNode* cur = phead->next; //判断cur是否为哨兵位，如果不是哨兵位，则打印，是哨兵位 //则说明循环已经遍历完了 while (cur != phead) { printf("%d ", cur->date); cur = cur->next; } printf("\n"); } //链表的尾插 void ListPushBack(ListNode* phead, LTDateType x) { assert(phead); //创建一个新的结点 ListNode* newnode = BuyListNode(x); //寻找末尾结点 ListNode* tail = phead->prev; //连接 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //链表的头插 void ListPushFront(ListNode* phead, LTDateType x) { assert(phead); //为x创建一个结点 ListNode* newnode = BuyListNode(x); //先记录一下原来的第一个结点 ListNode* first = phead->next; //连接 phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; } 链表的头插(需要考虑顺序的话) //void ListPushFront(ListNode* phead, LTDateType x) //{ // assert(phead); // ListNode* newnode = BuyListNode(x); // // newnode->next = phead->next; // phead->next->prev = newnode; // // phead->next = newnode; // newnode->prev = phead; //} //链表的头删 void ListPopFront(ListNode* phead) { assert(phead); //这是避免删掉我的哨兵位 assert(phead->next != phead); //第一个结点的地址 ListNode* first = phead->next; //第二个结点的地址 ListNode* second = first->next; //连接 phead->next = second; second->prev = phead; //释放第一个结点 free(first); first = NULL; } //链表的尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); //定义倒数第一个结点 ListNode* tail = phead->prev; //定义倒数第二个结点 ListNode* prev = tail->prev; //连接 phead->prev = prev; prev->next = phead; //销毁原来的结点 free(tail); tail = NULL; } //查找某一个值的结点地址 ListNode* ListFind(ListNode* phead,LTDateType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->date == x) { return cur; } cur = cur->next; } return NULL; } //在pos之前插入一个值 void ListInsert(ListNode* pos, LTDateType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); newnode->next = pos; pos->prev = newnode; prev->next = newnode; newnode->prev = prev; } //删除pos处的值 void ListErase(ListNode* pos) { assert(pos); ListNode* next = pos->next; ListNode* prev = pos->prev; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
四、顺序表和链表的区别和联系
顺序表：
优点
空间连续、支持随机访问
缺点
1.中间或前面部分的插入删除时间复杂度O（N）
2.增容的代价比较大
链表：
优点
1.任意位置插入删除时间复杂度为O（1）
2.没有增容消耗，按需申请结点空间，不用了直接释放
缺点
以节点为单位存储，不支持随机访问
总结
本节讲解了双向带头循环链表的实现，希望大家都有所收获
如果对你有帮助，不要忘记点赞加收藏哦！！！
想看更多更加优质的内容，一定要关注我哦！！！
