大家好，欢迎来到IT知识分享网。
目录
引言
在 数据结构——单链表 中我们学习了数据结构中的单链表，它解决了顺序表中插入删除需要挪动大量数据的缺点。但同时也有需要改进的地方，比如说：当我们需要寻找某个节点的前一个节点，对于单链表而言只能遍历，这样就可能造成大量时间的浪费。为了解决这个问题，我们需要学习新的内容——带头双向循环链表。
如图所示：
双向链表的功能
我们今天学习的双链表要实现一下几个功能：
- 初始化双向链表中的数据。
- 打印双向链表中的数据。
- 对双向链表进行尾插(末尾插入数据)。
- 对双向链表进行头插(开头插入数据)。
- 对双向链表进行尾删(末尾删除数据)。
- 对双向链表进行头删(开头删除数据)。
- 对双向链表数据进行查找。
- 对双向链表数据进行修改。
- 对指定位置的数据删除
- 对指定位置的数据插入。
- 销毁双向链表。
双向链表的定义
双向链表的定义结构体需要包含三个成员，一个成员存储数值，一个成员存储前一个节点的地址，最后一个成员存储下一个节点的地址。
如下图所示：
双向链表的功能实现
1.初始化双向链表中的数据
在初始化双向链表时，我们需要创建一个头节点，也就是我们常说的哨兵位头节点。
如图所示：
(1)创建头节点
//申请节点 LTNode* LTCreateNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); // 如果node为NULL，说明内存分配失败 if (node == NULL) { perror("malloc fail"); exit(1); } node->data = x; // 将前后节点都指向自己 node->next = node->prev = node; return node; }(2)初始化
在初始化的时候我们已经将前后指针指向自己本身了，我们在这里把哨兵位头节点设置为-1。
LTNode* LTInit() { LTNode* phead = LTCreateNode(-1); return phead; }(3)复杂度分析
时间复杂度：由于没有额外的空间消耗，因此时间复杂度为O(1)。
空间复杂度：由于每次固定生成一个节点，因此空间复杂度为O(1)。
2.打印双向链表中的数据
(1)代码实现
//打印 void LTPrint(LTNode* phead) { LTNode* pcur = phead->next; // 使用while循环遍历链表，直到回到哨兵节点 while (pcur != phead) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); }(2)复杂度分析
时间复杂度：由于需要遍历整个链表，因此时间复杂度为O(n)。
空间复杂度：由于每次固定生成一个节点，因此空间复杂度为O(1)。
3.双向链表尾插
(1)代码实现
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTCreateNode(x); // 新节点的prev指针指向当前链表的最后一个节点 //（即phead的prev指向的节点） newnode->prev = phead->prev; // 新节点的next指针指向头节点phead，这样就形成了双向循环 newnode->next = phead; // 更新当前链表最后一个节点的next指针，使其指向新节点 phead->prev->next = newnode; // 更新头节点phead的prev指针，使其指向新节点 phead->prev = newnode; }(2)复杂度分析
时间复杂度：由于没有额外的时间消耗，因此时间复杂度为O(1)。
空间复杂度：由于每次固定生成一个节点，因此空间复杂度为O(1)。
4.双向链表头插
(1)代码实现
//头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTCreateNode(x); // 新节点的next指针指向当前头节点的下一个节点 newnode->next = phead->next; // 新节点的prev指针指向头节点phead newnode->prev = phead; // 更新原来头节点的下一个节点的prev指针 phead->next->prev = newnode; // 更新头节点phead的next指针 phead->next = newnode; }(2)复杂度分析
时间复杂度：由于没有额外的时间消耗，因此时间复杂度为O(1)。
空间复杂度：由于每次固定生成一个节点，因此空间复杂度为O(1)。
5.双向链表尾删
要注意，千万不要把头节点给删了。
(1)代码实现
//尾删 void LTPopBack(LTNode* phead) { // 链表必须有效并且链表不能为空（即不能只有哨兵节点） assert(phead && phead->next != phead); LTNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; //删除del节点 free(del); del = NULL; }(2)复杂度分析
时间复杂度：由于没有额外的时间消耗，因此时间复杂度为O(1)。
空间复杂度：由于没有额外的空间消耗，因此空间复杂度为O(1)。
6.双向链表头删
同样，要注意，千万不要把头节点给删了。
(1)代码实现
//头删 void LTPopFront(LTNode* phead) { // 断言检查phead是否为空 // 并且链表是否只有一个哨兵节点（即链表为空） assert(phead && phead->next != phead); // 指向要删除的节点，即当前头节点的下一个节点 LTNode* del = phead->next; // 更新头节点的next指针，使其指向要删除节点的下一个节点 phead->next = del->next; // 更新被删除节点的下一个节点的prev指针 del->next->prev = phead; free(del); del = NULL; }(2)复杂度分析
时间复杂度：由于没有额外的时间消耗，因此时间复杂度为O(1)。
空间复杂度：由于没有额外的空间消耗，因此空间复杂度为O(1)。
7.双向链表数据查找
遍历整个链表，如果找到则返回当前节点的指针，如果遍历完整个链表都没找到则返回NULL。
(1)代码实现
//查找数据 LTNode* LTFind(LTNode* phead, LTDataType x) { LTNode* pcur = phead->next; // 遍历链表，直到回到哨兵节点（表示已经遍历了整个链表） while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }(2)复杂度分析
时间复杂度：由于最坏情况要遍历整个链表，因此时间复杂度为O(n)。
空间复杂度：由于没有额外的空间消耗，因此空间复杂度为O(1)。
8.双向链表数据修改
(1)代码实现
//修改数据 void LTModify(LTNode* phead, LTNode* pos, LTDataType x) { assert(phead); assert(pos != phead); LTNode* pcur = phead->next; // 遍历链表，直到回到头节点 while (pcur != phead) { if (pcur == pos) { pcur->data = x; } pcur = pcur->next; } }(2)复杂度分析
时间复杂度：由于最坏情况要遍历整个链表，因此时间复杂度为O(n)。
空间复杂度：由于没有额外的空间消耗，因此空间复杂度为O(1)。
9.指定位置数据删除
(1)代码实现
//删除pos节点 void LTErase(LTNode* pos) { assert(pos); // 将pos的下一个节点的prev指针指向pos的前一个节点 pos->next->prev = pos->prev; // 将pos的前一个节点的next指针指向pos的下一个节点 pos->prev->next = pos->next; free(pos); pos = NULL; }(2)复杂度分析
时间复杂度：由于没有额外的时间消耗，因此时间复杂度为O(1)。
空间复杂度：由于没有额外的空间消耗，因此空间复杂度为O(1)。
10.指定位置数据插入
指定位置数据插入分为指定位置前后插入数据。
(1)在指定位置前插入数据
//在pos之前插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTCreateNode(x); // 设置新节点的next指针指向pos，这样新节点就“指向”了pos newnode->next = pos; // 设置新节点的prev指针指向pos的前一个节点 newnode->prev = pos->prev; // 更新pos前一个节点的next指针，使其指向新节点 pos->prev->next = newnode; // 更新pos的prev指针，使其指向新节点 pos->prev = newnode; }(2)在指定位置后插入数据
//在pos之后插入数据 void LTInsertAfter(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTCreateNode(x); // 设置新节点的next指针指向pos的下一个节点 newnode->next = pos->next; // 设置新节点的prev指针指向pos newnode->prev = pos; // 更新pos的下一个节点的prev指针 pos->next->prev = newnode; // 更新pos的next指针 pos->next = newnode; }(3)复杂度分析
时间复杂度：由于没有额外的时间消耗，因此时间复杂度为O(1)。
空间复杂度：由于每次固定生成一个节点，因此空间复杂度为O(1)。
11.销毁双向链表
(1)代码实现
//销毁数据 void LTDestroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; // 遍历整个链表 while (pcur != phead) { if (pcur == NULL) { exit(1); } LTNode* next = pcur->next; free(pcur); pcur = NULL; } free(phead); phead = NULL; }(2)复杂度分析
时间复杂度：由于没有额外的时间消耗，因此时间复杂度为O(1)。
空间复杂度：由于没有额外的空间消耗，因此空间复杂度为O(1)。
完整代码
List.h
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDataType; //定义双链表的结构 typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode; //初始化 //void LTInit(LTNode pphead); LTNode* LTInit(); //打印 void LTPrint(LTNode* phead); //插入数据之前，链表必须初始化到只有一个头节点的情况 //不改变哨兵位的地址，因此只需要传一级指针 //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头插 void LTPushFront(LTNode* phead, LTDataType x); //尾删 void LTPopBack(LTNode* phead); //头删 void LTPopFront(LTNode* phead); //在pos之前插入数据 void LTInsert(LTNode* pos, LTDataType x); //在pos之后插入数据 void LTInsertAfter(LTNode* pos, LTDataType x); //删除pos节点 void LTErase(LTNode* pos); //查找数据 LTNode* LTFind(LTNode* phead, LTDataType x); //销毁数据 void LTDestroy(LTNode* phead); //修改数据 void LTModify(LTNode* phead, LTNode* pos, LTDataType x);List.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" //申请节点 LTNode* LTCreateNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); // 如果node为NULL，说明内存分配失败 if (node == NULL) { perror("malloc fail"); exit(1); } node->data = x; // 将前后节点都指向自己 node->next = node->prev = node; return node; } //初始化 //void LTInit(LTNode pphead) //{ // //给双向链表创建一个哨兵位 // *pphead = LTBuyNode(-1); //} LTNode* LTInit() { LTNode* phead = LTCreateNode(-1); return phead; } //打印 void LTPrint(LTNode* phead) { LTNode* pcur = phead->next; // 使用while循环遍历链表，直到回到哨兵节点 while (pcur != phead) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); } //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTCreateNode(x); // 新节点的prev指针指向当前链表的最后一个节点 //（即phead的prev指向的节点） newnode->prev = phead->prev; // 新节点的next指针指向头节点phead，这样就形成了双向循环 newnode->next = phead; // 更新当前链表最后一个节点的next指针，使其指向新节点 phead->prev->next = newnode; // 更新头节点phead的prev指针，使其指向新节点 phead->prev = newnode; } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTCreateNode(x); // 新节点的next指针指向当前头节点的下一个节点 newnode->next = phead->next; // 新节点的prev指针指向头节点phead newnode->prev = phead; // 更新原来头节点的下一个节点的prev指针 phead->next->prev = newnode; // 更新头节点phead的next指针 phead->next = newnode; } //尾删 void LTPopBack(LTNode* phead) { // 链表必须有效并且链表不能为空（即不能只有哨兵节点） assert(phead && phead->next != phead); LTNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; //删除del节点 free(del); del = NULL; } //头删 void LTPopFront(LTNode* phead) { // 断言检查phead是否为空 // 并且链表是否只有一个哨兵节点（即链表为空） assert(phead && phead->next != phead); // 指向要删除的节点，即当前头节点的下一个节点 LTNode* del = phead->next; // 更新头节点的next指针，使其指向要删除节点的下一个节点 phead->next = del->next; // 更新被删除节点的下一个节点的prev指针 del->next->prev = phead; free(del); del = NULL; } //查找数据 LTNode* LTFind(LTNode* phead, LTDataType x) { LTNode* pcur = phead->next; // 遍历链表，直到回到哨兵节点（表示已经遍历了整个链表） while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; } //在pos之前插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTCreateNode(x); // 设置新节点的next指针指向pos，这样新节点就“指向”了pos newnode->next = pos; // 设置新节点的prev指针指向pos的前一个节点 newnode->prev = pos->prev; // 更新pos前一个节点的next指针，使其指向新节点 pos->prev->next = newnode; // 更新pos的prev指针，使其指向新节点 pos->prev = newnode; } //在pos之后插入数据 void LTInsertAfter(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTCreateNode(x); // 设置新节点的next指针指向pos的下一个节点 newnode->next = pos->next; // 设置新节点的prev指针指向pos newnode->prev = pos; // 更新pos的下一个节点的prev指针 pos->next->prev = newnode; // 更新pos的next指针 pos->next = newnode; } //删除pos节点 void LTErase(LTNode* pos) { assert(pos); // 将pos的下一个节点的prev指针指向pos的前一个节点 pos->next->prev = pos->prev; // 将pos的前一个节点的next指针指向pos的下一个节点 pos->prev->next = pos->next; free(pos); pos = NULL; } //销毁数据 void LTDestroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; // 遍历整个链表 while (pcur != phead) { if (pcur == NULL) { exit(1); } LTNode* next = pcur->next; free(pcur); pcur = NULL; } free(phead); phead = NULL; } //修改数据 void LTModify(LTNode* phead, LTNode* pos, LTDataType x) { assert(phead); assert(pos != phead); LTNode* pcur = phead->next; // 遍历链表，直到回到头节点 while (pcur != phead) { if (pcur == pos) { pcur->data = x; } pcur = pcur->next; } }结束语
花了点时间介绍了一下双向链表。
感谢友友们的支持！！！
求点赞收藏关注！！！
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/110626.html
