热门标签
热门文章
- 1计算机网络中23是什么端口号,什么是网络端口，端口有哪些分类-电脑自学网
- 2【话题】程序员应该有什么职业素养
- 3java的JVM学习总结第一章——JVM与java的体系结构
- 4【文献阅读】受山体阴影影响的冰湖制图方法研究（Li JunLi等人，2018.09，IJRS）_阴影损失文献
- 5【数据结构】线性表之《带头双向循环链表》超详细实现
- 6LLM 大模型学习必知必会系列(十)：基于AgentFabric实现交互式智能体应用,Agent实战_dashscope中的llm的api
- 7ue4 UMG添加到场景_unreal umg放到世界空间
- 8译文：dBA和dBC的不同_dba和dbc的区别
- 9网站高性能架构设计——web前端与池化_前端架构设计
- 10spring整合openAI大模型之Spring AI_spring ai maven
当前位置: article > 正文
【数据结构】线性表之《带头双向循环链表》超详细实现
作者：码创造者 | 2024-06-29 14:40:15
赞
踩
【数据结构】线性表之《带头双向循环链表》超详细实现
前言：虽然笔试常考无头单链表，但是实际上存储数据时，常用带头双向循环链表。这带头双向循环链表相比于无头单链表，不仅在存储数据时更为高效，而且在插入、删除等操作中也表现出更优的性能。
一.带头双向循环链表与无头单向非循环链表的区别
无头单向非循环链表（简称：单链表）：
- 结构简单，一般
不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。 - 另外这种结构在
笔试面试中出现很多。尾删，插入与删除，由于需要从头开始找前一个节点，时间复杂度为O(N)，效率较低。
带头双向循环链表（简称：双向链表）：
- 结构最复杂，一般用在单独
存储数据。实际中使用的链表数据结构，都是带头双向循环链表。 - 另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
- 带头节点，不需要改变传过来的指针，也就意味着
不需要传二级指针。 - 带哨兵位的头节点不存储有效数据。若存储链表的长度，当节点中的数据类型是char时，最大只能为255这是不合理的。
- 查找数据时，时间复杂度为O(N)，一般不用这个，而用
平衡搜索树（AVL树，红黑树），哈希表，B树，B+树系列，跳表，布隆过滤器，位图。
二.顺序表和双向链表的优缺点分析
三.带头双向循环链表实现
1.创建双链表
双链表由节点组成，每个节点要存放数据，上一个节点的地址与下一个节点的地址。
双链表：指向该节点的指针。
typedef int LTDataType; //增强程序的可维护性
typedef struct ListNode
{
LTDataType data; //数据域
struct ListNode* next; //前驱指针
struct ListNode* prev; //后继指针
}ListNode;
ListNode* plist;//双链表
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
2.初始化双链表
将双链表初始化为带哨兵位的头节点，并实现循环结构。
ListNode* ListInit()
{
//创建头节点
ListNode* phead = BuyNode(0);
//实现循环结构
phead->next = phead;
phead->prev = phead;
return phead;//返回节点指针
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
3.购买节点
由于头插，尾插，按位置插入链表，都要先准备一个节点。为了减少代码的重复，直接对其进行封装，创建新节点的时候直接调用该接口就行。
ListNode* BuyNode(LTDataType x) { //开辟节点空间 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); //开辟失败 if (newnode == NULL) { perror("malloc fail!"); exit(1); } //开辟成功后初始化节点 newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
4.打印双链表
定义一个指针指向双链表头节点的下一个节点，利用尾节点的next指向头节点这一结束条件，循环遍历打印即可，较为简单。
void ListPrint(ListNode* phead)
{
assert(phead); //断言
//定位链表实际的第一个节点
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d——>", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
5.插入操作
1.头插
头插思想：在头节点与第一个存储数据的节点之间插入，修改4个指针的指向即可。
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);//断言
ListNode* newnode = BuyNode(x); //购买节点
ListNode* first = phead->next; //找到实际的第一个节点
//实现头插
newnode->next = first;
first->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
//等价于：ListInsert(phead->next, x);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
2.尾插
尾插思想：定位尾节点，在尾节点后面插入，修改4个指针的指向即可。
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyNode(x); //购买节点
ListNode* tail = phead->prev; //定位尾节点
//实现尾插
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//等价于：ListInsert(phead, x);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
3.给定位置之前插入
在双链表中插入思路其实都大差不差，而不需考虑单链表时的各种情况，所以说实现较为简单。
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyNode(x); //购买节点
ListNode* prev = pos->prev; //定位pos前一个节点
//实现插入
newnode->next = pos;
pos->prev = newnode;
prev->next = newnode;
newnode->prev = prev;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
6.删除操作
删除操作不用分情况，也较为简单，这么一看带头双向循环链表还是非常完美的。
1.头删
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; //置空，防止野指针 //等价于：ListErase(phead->next); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
2.尾删
void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); //当链表中没有为空时，不能尾删，否则会将头节点删除！ //实现尾删 ListNode* tail = phead->prev; //定位尾节点 ListNode* prev = tail->prev; //定位尾节点前一个节点 prev->next = phead; phead->prev = prev; free(tail); tail = NULL; //等价于：ListErase(phead->prev); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
3.删除给定位置的结点
void ListErase(ListNode* pos)
{
assert(pos);
//实现删除
ListNode* prev = pos->prev; //定位pos的前一个节点
ListNode* next = pos->next; //定位pos的后一个节点
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
7.查找数据
思路：循环遍历双链表即可，找到返回地址，未找到返回NULL。
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->next; //定位第一个节点
while (cur != phead)
{
if (cur->data == x) //找到了，返回cur
{
return cur;
}
cur = cur->next;
}
return NULL; //未找到，返回NULL
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
8.修改数据
思路：直接通过ListFind函数得到地址，在该处修改即可，较为简单，同时ListErase与ListInsert函数都要通过ListFind函数得到地址。
void ListModify(ListNode* pos, LTDataType x)
{
assert(pos);
pos->data = x;//直接修改即可
}
- 1
- 2
- 3
- 4
- 5
9.求双链表长度
int ListLength(ListNode* phead)
{
assert(phead);
int len = 0;
ListNode* cur = phead->next; //定位第一个节点
while (cur != phead)
{
cur = cur->next;
len++;
}
return len;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
10.清空双链表
注意：逐个节点释放，不能释放头节点，为了能找到下一个节点，要用指针保存，最后还原为循环结构。
void Clear(ListNode* phead) { assert(phead); //实现清空 ListNode* cur = phead->next; //定位第一个节点 ListNode* next = cur; //辅助删除节点的指针 while (cur != phead) { next = next->next; free(cur); cur = next; } //注意：还原循环结构 phead->next = phead; phead->prev = phead; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
11.销毁双链表
先调用Clear函数，在释放头节点即可。
void Destory(ListNode* phead)
{
assert(phead);
//先清空，再销毁phead
Clear(phead);
free(phead);
phead = NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
四.模块化源代码
1.DoubleLinkList.h
//#pragma once 防止头文件被重复包含 #ifndef __DOUBLECIRCULARLINKLIST_H__ #define __DOUBLECIRCULARLINKLIST_H__ #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDataType; //增强程序的可维护性 typedef struct ListNode { LTDataType data; //数据域 struct ListNode* next; //前驱指针 struct ListNode* prev; //后继指针 }ListNode; ListNode* BuyNode(LTDataType x);//购买节点 ListNode* ListInit();//初始化链表 void ListPrint(ListNode* phead);//打印链表 void ListPushBack(ListNode* phead, LTDataType x);//尾插 void ListPushFront(ListNode* phead, LTDataType x);//头插 void ListPopBack(ListNode* phead);//尾删 void ListPopFront(ListNode* phead);//头删 ListNode* ListFind(ListNode* phead, LTDataType x);//查找链表中的x值，返回节点的地址 void ListInsert(ListNode* pos, LTDataType x);//利用ListFind函数找到pos，在pos前，插入x void ListErase(ListNode* pos);//利用ListFind函数找到pos，删除pos节点 void ListModify(ListNode* pos, LTDataType x);//将pos位置的数据修改为x int ListLength(ListNode* phead);//求链表的长度 void Clear(ListNode* phead);//清空链表 void Destory(ListNode* phead);//销毁链表 #endif
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
2.DoubleLinkList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"DoubleCircularLinkList.h" ListNode* BuyNode(LTDataType x) { //开辟节点空间 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); //开辟失败 if (newnode == NULL) { perror("malloc fail!"); exit(1); } //开辟成功后初始化节点 newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } ListNode* ListInit() { //创建头节点 ListNode* phead = BuyNode(0); //实现循环结构 phead->next = phead; phead->prev = phead; return phead; } void ListPrint(ListNode* phead) { assert(phead); //断言 //定位链表实际的第一个节点 ListNode* cur = phead->next; while (cur != phead) { printf("%d——>", cur->data); cur = cur->next; } printf("NULL\n"); } void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* newnode = BuyNode(x); //购买节点 ListNode* tail = phead->prev; //定位尾节点 //实现尾插 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; //等价于：ListInsert(phead, x); } void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* newnode = BuyNode(x); //购买节点 ListNode* first = phead->next; //找到实际的第一个节点 //实现头插 newnode->next = first; first->prev = newnode; newnode->prev = phead; phead->next = newnode; //等价于：ListInsert(phead->next, x); } void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); //当链表中没有为空时，不能尾删，否则会将头节点删除！ //实现尾删 ListNode* tail = phead->prev; //定位尾节点 ListNode* prev = tail->prev; //定位尾节点前一个节点 prev->next = phead; phead->prev = prev; free(tail); //释放，防止内存泄漏 tail = NULL; //置空，防止野指针 //等价于：ListErase(phead->prev); } 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; //等价于：ListErase(phead->next); } ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; //定位第一个节点 while (cur != phead) { if (cur->data == x) //找到了，返回cur { return cur; } cur = cur->next; } return NULL; //未找到，返回NULL } void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyNode(x); //购买节点 ListNode* prev = pos->prev; //定位pos前一个节点 //实现插入 newnode->next = pos; pos->prev = newnode; prev->next = newnode; newnode->prev = prev; } void ListErase(ListNode* pos) { assert(pos); //实现删除 ListNode* prev = pos->prev; //定位pos的前一个节点 ListNode* next = pos->next; //定位pos的后一个节点 prev->next = next; next->prev = prev; free(pos); pos = NULL; } void ListModify(ListNode* pos, LTDataType x) { assert(pos); pos->data = x;//直接修改即可 } int ListLength(ListNode* phead) { assert(phead); int len = 0; ListNode* cur = phead->next; //定位第一个节点 while (cur != phead) { cur = cur->next; len++; } return len; } void Clear(ListNode* phead) { assert(phead); //实现清空 ListNode* cur = phead->next; //定位第一个节点 ListNode* next = cur; //辅助删除节点的指针 while (cur != phead) { next = next->next; free(cur); cur = next; } //注意：还原循环结构 phead->next = phead; phead->prev = phead; } void Destory(ListNode* phead) { assert(phead); //先清空，再销毁phead Clear(phead); free(phead); phead = NULL; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
3.test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"DoubleCircularLinkList.h" enum //匿名枚举 { EXIT, PUSHBACK, PUSHFRONT, POPBACK, POPFRONT, INSERT, ERASE, FIND, MODIFY, PRINT, LENGTH, CLEAR }; void Menu() { printf("**********双向循环链表*********\n"); printf("****1.尾插 2.头插****\n"); printf("****3.尾删 4.头删****\n"); printf("****5.插入 6.删除****\n"); printf("****7.查找 8.修改****\n"); printf("****9.打印 10.长度****\n"); printf("***11.清空 0.退出****\n"); printf("*******************************\n"); } int main() { ListNode* plist = NULL; plist = ListInit(); int select = 0; LTDataType value; LTDataType value1; ListNode* pos = NULL; //记录节点的地址 do { Menu(); printf("请输入您的操作："); scanf("%d", &select); switch (select) { case EXIT: printf("退出双向循环链表!\n"); break; case PUSHBACK: printf("请输入要尾插的值（以-1结束）："); while ((scanf("%d", &value), value != -1)) { ListPushBack(plist, value); } break; case PUSHFRONT: printf("请输入要头插的值（以-1结束）："); do { scanf("%d", &value); if (value != -1) { ListPushFront(plist, value); } } while (value != -1); break; case PRINT: ListPrint(plist); break; case POPBACK: ListPopBack(plist); break; case POPFRONT: ListPopFront(plist); case FIND: printf("请输入您要查找的值："); scanf("%d", &value); pos = ListFind(plist, value); if (pos != NULL) { printf("存在!\n"); } else { printf("不存在!\n"); } break; case INSERT: printf("请输入您要插入到《何值前面》以及《插入的值》："); scanf("%d %d", &value1, &value); pos = ListFind(plist, value1); if (pos != NULL) { ListInsert(pos, value); } else { printf("该值不存在，无法插入!\n"); } break; case ERASE: printf("请输入您要删除的值："); scanf("%d", &value); pos = ListFind(plist, value); if (pos != NULL) { ListErase(pos); } else { printf("该值不存在，无法删除!\n"); } break; case MODIFY: printf("请输入您要《要修改的值》以及《修改后的值》："); scanf("%d %d", &value1, &value); pos = ListFind(plist, value1); if (pos != NULL) { ListModify(pos, value); } else { printf("该值不存在，无法修改!\n"); } break; case LENGTH: printf("链表的长度：%d\n", ListLength(plist)); break; case CLEAR: Clear(plist); break; default: printf("输入错误，请重新输入!\n"); break; } } while (select); Destory(plist); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
五.链表必做OJ题
创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！
本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签
