C语言中数据结构——带头双向循环链表-阿里云开发者社区

🚀🚀🚀大家觉不错的话，就恳求大家点点关注，点点小爱心，指点指点🚀🚀🚀

🐰带头双向循环链表

🏡概念

1.无头单向非循环的链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构，例如哈希桶、图的邻接表等等。这种结构在笔试面试中出现的比较多。（之前提到的单链表是一种无头单向非循环的链表。）

2.带头双向循环链表：结构复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构最燃复杂，但是使用代码实现以后会发现结构会带来很多优势，实现起来反而简单。

🏡链表结构体的定义

1. typedef int LTDatatype;
2. typedef struct ListNode
3. {
4. struct ListNode* next;//保存下个节点的地址
5. struct ListNode* prev;//保存上个节点的地址
6.     LTDatatype data;//存储的数据
7. }ListNode;

🏡链表为空的判断

1. bool ListNodeEmpty(ListNode* pphead)
2. {
3. assert(pphead);
4. return pphead->next==pphead;//哨兵位的下个节点的地址和哨兵位的地址相等则链表为空，这里返回true
5. }

🏡链表节点的创建

动态创建一个节点，将节点的prev指针置空，将节点next指针置空，值赋值为x（x是传进来的参数），然后返回这个节点的地址。

1. ListNode* BuyListNode(LTDatatype x)
2. {
3.     ListNode* newnode=(ListNode*)malloc(sizeof(ListNode));
4. if(newnode==NULL)
5.     {
6. perror("malloc fail!");
7. return NULL;
8.     }
9.     newnode->next=NULL;
10.     newnode->prev=NULL;
11.     newnode->data=x;
12. return newnode;
13. }

🏡链表的初始化

链表的初始化是创建一个哨兵位，哨兵位的数据值为-1。且初始化时，是将哨兵位的prev指针指向自己，哨兵位的next指向自己。返回这个哨兵位的地址

1. ListNode* ListNodeInit(ListNode* pphead)
2. {
3.     pphead=BuyListNode(-1);
4.     pphead->next=pphead;
5.     pphead->prev=pphead;
6. return pphead;
7. }

🏡链表的打印

创建一个结构体指针cur，让cur指向哨兵位的下一个节点（链表的头节点），然后遍历整个链表并打印每个节点的数据值，当cur的值等于哨兵位的指针的值，说明遍历完成，结束打印。

1. void ListNodePrint(ListNode* pphead)
2. {
3. assert(pphead);
4.     ListNode* cur=pphead->next;//从头节点开始打印
5. while(cur!=pphead)//当cur的值等与哨兵位的值（这里的值是存放的节点的地址）相等纠结束打印，
6.     {
7. printf("%d ",cur->data);
8.         cur=cur->next;
9.     }
10. printf("\n");
11. printf("print has done\n");
12. }

🏡链表的尾插

这里不管是头节点还是中间节点，都能完成尾插，但是单向不循环链表，得分头节点和中间节点，体现出双向循环链表在尾删的便利

1. void ListNodePushBack(ListNode* pphead,LTDatatype x)
2. {
3. assert(pphead);
4.     ListNode* tail=pphead->prev;
5.     ListNode* newnode=BuyListNode(x);
6.     tail->next=newnode;
7.     newnode->prev=tail;
8.     newnode->next=pphead;
9.     pphead->prev=newnode;
10. }

🏡链表的头插

1. void ListNodePushFront(ListNode* pphead,LTDatatype x)
2. {
3. //这里不管是头节点还是中间节点，都能完成头插，但是单向不循环链表，得分头节点和中间节点
4. assert(pphead);
5.     ListNode* newnode=BuyListNode(x);
6.     newnode->next=pphead->next;//a
7.     pphead->next->prev=newnode;//b
8. //这里的a b一定在c d的前面，不然pphead->next被改后，没有找到原来的头节点。
9. //这里其实用慢指针去赋值，就可以不在意顺序了
10.     pphead->next=newnode;//c
11.     newnode->prev=pphead;//d
12. }

🏡链表的尾删

尾删的时候，要注意不要把哨兵位删除了，所以需要判断链表是否为空，如果为空不能删除

1. void ListNodePopBack(ListNode* pphead)
2. {
3. assert(pphead);
4. assert(!ListNodeEmpty(pphead));
5.     ListNode* tail=pphead->prev;
6.     ListNode* tailPrev=tail->prev;
7. free(tail);
8.     tail=NULL;
9.     pphead->prev=tailPrev;
10.     tailPrev->next=pphead;
11. }

🏡链表的头删

1. void ListNodePopFront(ListNode* pphead)
2. {
3. assert(pphead);
4. assert(!ListNodeEmpty(pphead));
5. 
6.     ListNode* tail=pphead->next;
7.     ListNode* tailNext=tail->next;
8. free(tail);
9.     tail=NULL;
10. 
11.     pphead->next=tailNext;
12.     tailNext->prev=pphead;
13. }

🏡链表的查找

根据给出的值，然后去遍历整个链表，如果链表中有与给出的值相匹配的节点，就返回这个节点的地址，如果没有返回空指针。

1. ListNode* ListNodeFind(ListNode* pphead,LTDatatype x)
2. {
3. assert(pphead);
4.     ListNode* cur=pphead->next;
5. while(cur!=pphead)
6.     {
7. if(cur->data==x)
8.         {
9. return cur;
10.         }
11.         cur=cur->next;
12.     }
13. return NULL;
14. }

🏡链表中在pos之前插入

1. void ListNodeInsert(ListNode* pos,LTDatatype x)
2. {
3. assert(pos);
4.     ListNode* newnode=BuyListNode(x);
5. //这种方法的可读性高
6.     ListNode* prev=pos->prev;
7.     prev->next=newnode;
8.     newnode->prev=prev;
9.     newnode->next=pos;
10.     pos->prev=newnode;
11. //少定义一个指针的方法，但一定要记住先修改pos的右边
12. //    pos->prev->next=newnode;
13. //    newnode->prev=pos->prev;
14. //    newnode->next=pos;
15. //    pos->prev=newnode;
16. }

🏡删除pos的值

1. void ListNodeErease(ListNode* pos)
2. {
3. assert(pos);
4.     ListNode* posPrev=pos->prev;
5.     ListNode* posNext=pos->next;
6. free(pos);
7.     posPrev->next=posNext;
8.     posNext->prev=posPrev;
9. }

🏡链表的销毁

利用快慢指针的方式，做到free掉每个节点

1. void ListNodeDestroy(ListNode* pphead)
2. {
3. assert(pphead);
4.     ListNode* cur=pphead->next;
5.     ListNode* prev=cur->next;
6. while(cur!=pphead)
7.     {
8. free(cur);
9.         cur=prev;
10.         prev=prev->next;
11.     }
12. free(pphead);
13. }

🏡链表为什么使用的是一级指针

🌸（1）单链表（非头单向不循环连链表）使用二级指针

我们在实现单链表（非头单向不循环连链表）使用的是二级指针。其实我们也可以使用一级指针，但前提是链表不能对头节点进行操作。因为我们在主函数创建的结构体指针plist，如果没有对plist指向的链表的头节点进行操作，在调用删除或插入等函数时，就可以通过形参指针去修改链表。如果对plist指向的链表的头节点进行操作，在调用删除或插入函数时，就不能保证操作正确性了。传给函数的是plist值，函数的形参指针无法对plist进行操作，要想要改变plist的值，只能传plist的地址并且函数形参指针必须是二级指针。

🌸（2）带头双向循环连链表使用一级指针

我们的带头双向循环连链表之所以使用一级指针，因为我们在进行删除或插入等操作时，plist始终指向哨兵位节点，在一系列操作中，哨兵位的位置没有改变。所以链表只需传plist的值且函数形参指针使用一级指针。

🏡狡猾的面试官

如果在面试时，面试官让你在10分钟以内写完一个链表，链表的功能包括：链表的打印，链表的头删，链表的尾删，链表的头插，链表的尾插，链表的任意位置删除，链表任意位置插入，链表销毁。对于我而言，就算我准备的有多么的充足，在面试这种紧张环境下，我根本不可能完成这种要求，也就是我将得不到这家公司的offer。但是我们冷静分析一下，链表面试没有规定是哪一种，链表的种类一共有8之多，我们应该首选带头双向循环链表，别看它结构复杂，但是实现的功能的逻辑简单（可以减少很多空指针的情况），我们选了带头双向循环链表之后，其实链表的任意位置删除和链表的头删，链表的尾删其实功能类似，链表的任意位置删除和链表的头插，链表的尾插实现的功能类似。所以我们只需要复用代码就行。

链表的尾插：

1. void ListNodePushBack(ListNode* pphead,LTDatatype x)
2. {
3. //复用ListNodeInsert
4. ListNodeInsert(pphead->prev, x);
5. }

链表的头插：

1. void ListNodePushFront(ListNode* pphead,LTDatatype x)
2. {  
3. //复用ListNodeInsert
4. ListNodeInsert(pphead->next, x);
5. }

链表的尾删：

1. void ListNodePopBack(ListNode* pphead)
2. {    
3. //复用ListNodeErease
4. ListNodeErease(pphead->prev);
5. }

链表的头删：

1. void ListNodePopFront(ListNode* pphead)
2. {
3. //    复用ListNodeErease
4. ListNodeErease(pphead->next);
5. }

这样我们就可以在10分钟之内识破面试官的诡计

🏡链表的源码

🌸main函数

1. #include "test.h"
2. void test1(void)
3. {
4.     ListNode* plist=NULL;
5.     plist=ListNodeInit(plist);
6. ListNodePushBack(plist, 1);
7. ListNodePushBack(plist, 2);
8. ListNodePushBack(plist, 3);
9. ListNodePushBack(plist, 4);
10. ListNodePrint(plist);
11. }
12. void test2(void)
13. {
14.     ListNode* plist=NULL;
15.     plist=ListNodeInit(plist);
16. ListNodePushFront(plist, 1);
17. ListNodePushFront(plist, 2);
18. ListNodePushFront(plist, 3);
19. ListNodePushFront(plist, 4);
20. ListNodePrint(plist);
21. }
22. void test3(void)
23. {
24.     ListNode* plist=NULL;
25.     plist=ListNodeInit(plist);
26. ListNodePushFront(plist, 1);
27. ListNodePushFront(plist, 2);
28. ListNodePushFront(plist, 3);
29. ListNodePushFront(plist, 4);
30. ListNodePrint(plist);
31. ListNodePopBack(plist);//尾删
32. ListNodePrint(plist);
33. ListNodePopFront(plist);//头删
34. ListNodePrint(plist);
35. ListNodePopBack(plist);//尾删
36. ListNodePrint(plist);
37. ListNodePopFront(plist);//头删
38. ListNodePrint(plist);
39. //ListNodePopFront(plist);//头删
40. }
41. void test4(void)
42. {
43.     ListNode* plist=NULL;
44.     plist=ListNodeInit(plist);
45. ListNodePushFront(plist, 1);
46. ListNodePushFront(plist, 2);
47. ListNodePushFront(plist, 3);
48. ListNodePushFront(plist, 4);
49. ListNodePrint(plist);
50.     ListNode* pos=ListNodeFind(plist, 3);
51. ListNodeInsert(pos, 100);
52. ListNodePrint(plist);
53. }
54. void test5(void)
55. {
56.     ListNode* plist=NULL;
57.     plist=ListNodeInit(plist);
58. ListNodePushFront(plist, 1);
59. ListNodePushFront(plist, 2);
60. ListNodePushFront(plist, 3);
61. ListNodePushFront(plist, 4);
62. ListNodePrint(plist);
63.     ListNode* pos=ListNodeFind(plist, 3);
64. ListNodeErease(pos);
65. ListNodePrint(plist);
66. }
67. void test6(void)
68. {
69.     ListNode* plist=NULL;
70.     plist=ListNodeInit(plist);
71. ListNodePushFront(plist, 1);
72. ListNodePushFront(plist, 2);
73. ListNodePushFront(plist, 3);
74. ListNodePushFront(plist, 4);
75. ListNodePrint(plist);
76. ListNodeDestroy(plist);
77. }
78. int main()
79. {
80. //test1();//头插
81. //test2();//尾插
82. //test3();//头删尾删
83. //test4();//任意位置的插入
84. test5();//任意位置的删除
85. //test6();//销毁链表
86. return 0;
87. }

🌸test.h文件

1. #ifndef test_h
2. #define test_h
3. #include <stdio.h>
4. #include<stdlib.h>
5. #include<assert.h>
6. #include<stdbool.h>
7. #endif /* test_h */
8. 
9. typedef int LTDatatype;
10. typedef struct ListNode
11. {
12. struct ListNode* next;
13. struct ListNode* prev;
14.     LTDatatype data;
15. }ListNode;
16. 
17. //链表为空的判断
18. bool ListNodeEmpty(ListNode* pphead);
19. //链表的初始化
20. ListNode* ListNodeInit(ListNode* pphead);
21. //链表的打印
22. void ListNodePrint(ListNode* pphead);
23. //链表的尾插
24. void ListNodePushBack(ListNode* pphead,LTDatatype x);
25. //链表的头插
26. void ListNodePushFront(ListNode* pphead,LTDatatype x);
27. //链表的尾删
28. void ListNodePopBack(ListNode* pphead);
29. //链表的头删
30. void ListNodePopFront(ListNode* pphead);
31. //链表的查找
32. ListNode* ListNodeFind(ListNode* pphead,LTDatatype x);
33. //在pos之前插入
34. void ListNodeInsert(ListNode* pos,LTDatatype x);
35. //删除pos的值
36. void ListNodeErease(ListNode* pos);
37. //链表的销毁
38. void ListNodeDestroy(ListNode* pphead);

🌸test.c文件

1. #include "test.h"
2. bool ListNodeEmpty(ListNode* pphead)
3. {
4. assert(pphead);
5. return pphead->next==pphead;
6. }
7. ListNode* BuyListNode(LTDatatype x)
8. {
9.     ListNode* newnode=(ListNode*)malloc(sizeof(ListNode));
10. if(newnode==NULL)
11.     {
12. perror("malloc fail!");
13. return NULL;
14.     }
15.     newnode->next=NULL;
16.     newnode->prev=NULL;
17.     newnode->data=x;
18. return newnode;
19. }
20. ListNode* ListNodeInit(ListNode* pphead)
21. {
22.     pphead=BuyListNode(-1);
23.     pphead->next=pphead;
24.     pphead->prev=pphead;
25. return pphead;
26. }
27. void ListNodePrint(ListNode* pphead)
28. {
29. assert(pphead);
30.     ListNode* cur=pphead->next;//从头节点开始打印
31. while(cur!=pphead)//当cur的值等与哨兵位的值（这里的值是存放的节点的地址）相等纠结束打印，
32.     {
33. printf("%d ",cur->data);
34.         cur=cur->next;
35.     }
36. printf("\n");
37. printf("print has done\n");
38. }
39. void ListNodePushBack(ListNode* pphead,LTDatatype x)
40. {
41. //    //这里不管是头节点还是中间节点，都能完成尾插，但是单向不循环链表，得分头节点和中间节点
42. //    assert(pphead);
43. //    ListNode* tail=pphead->prev;
44. //    ListNode* newnode=BuyListNode(x);
45. //    tail->next=newnode;
46. //    newnode->prev=tail;
47. //    newnode->next=pphead;
48. //    pphead->prev=newnode;
49. 
50. //复用ListNodeInsert
51. ListNodeInsert(pphead->prev, x);
52. }
53. void ListNodePushFront(ListNode* pphead,LTDatatype x)
54. {
55. //    //这里不管是头节点还是中间节点，都能完成头插，但是单向不循环链表，得分头节点和中间节点
56. //    assert(pphead);
57. //    ListNode* newnode=BuyListNode(x);
58. //    newnode->next=pphead->next;//a
59. //    pphead->next->prev=newnode;//b
60. //    //这里的a b一定在c d的前面，不然pphead->next被改后，没有找到原来的头节点。
61. //    //这里其实用慢指针去赋值，就可以不在意顺序了
62. //    pphead->next=newnode;//c
63. //    newnode->prev=pphead;//d
64. 
65. 
66. //复用ListNodeInsert
67. ListNodeInsert(pphead->next, x);
68. }
69. void ListNodePopBack(ListNode* pphead)
70. {
71. //    assert(pphead);
72. //    assert(!ListNodeEmpty(pphead));
73. //    ListNode* tail=pphead->prev;
74. //    ListNode* tailPrev=tail->prev;
75. //    free(tail);
76. //    tail=NULL;
77. //    pphead->prev=tailPrev;
78. //    tailPrev->next=pphead;
79. 
80. 
81. //复用ListNodeErease
82. ListNodeErease(pphead->prev);
83. }
84. void ListNodePopFront(ListNode* pphead)
85. {
86. //    assert(pphead);
87. //    assert(!ListNodeEmpty(pphead));
88. //
89. //    ListNode* tail=pphead->next;
90. //    ListNode* tailNext=tail->next;
91. //    free(tail);
92. //    tail=NULL;
93. //
94. //    pphead->next=tailNext;
95. //    tailNext->prev=pphead;
96. //
97. //    复用ListNodeErease
98. ListNodeErease(pphead->next);
99. }
100. ListNode* ListNodeFind(ListNode* pphead,LTDatatype x)
101. {
102. assert(pphead);
103.     ListNode* cur=pphead->next;
104. while(cur!=pphead)
105.     {
106. if(cur->data==x)
107.         {
108. return cur;
109.         }
110.         cur=cur->next;
111.     }
112. return NULL;
113. }
114. void ListNodeInsert(ListNode* pos,LTDatatype x)
115. {
116. assert(pos);
117.     ListNode* newnode=BuyListNode(x);
118. //这种方法的可读性高
119.     ListNode* prev=pos->prev;
120.     prev->next=newnode;
121.     newnode->prev=prev;
122.     newnode->next=pos;
123.     pos->prev=newnode;
124. //少定义一个指针的方法，但一定要记住先修改pos的右边
125. //    pos->prev->next=newnode;
126. //    newnode->prev=pos->prev;
127. //    newnode->next=pos;
128. //    pos->prev=newnode;
129. }
130. //ListNodeErease有一个缺陷，就是可能删除了哨兵位
131. void ListNodeErease(ListNode* pos)
132. {
133. assert(pos);
134.     ListNode* posPrev=pos->prev;
135.     ListNode* posNext=pos->next;
136. free(pos);
137.     posPrev->next=posNext;
138.     posNext->prev=posPrev;
139. }
140. void ListNodeDestroy(ListNode* pphead)
141. {
142. assert(pphead);
143.     ListNode* cur=pphead->next;
144.     ListNode* prev=cur->next;
145. while(cur!=pphead)
146.     {
147. free(cur);
148.         cur=prev;
149.         prev=prev->next;
150.     }
151. free(pphead);
152. }

🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区，我们共同探讨，共同学习，共同进步。谢谢大家！ 🌸🌸🌸

C语言中数据结构——带头双向循环链表

🐰带头双向循环链表

🏡概念

🏡链表结构体的定义

🏡链表为空的判断

🏡链表节点的创建

🏡链表的初始化

🏡链表的打印

🏡链表的尾插

🏡链表的头插

🏡链表的尾删

🏡链表的头删

🏡链表的查找

🏡链表中在pos之前插入

🏡删除pos的值

🏡链表的销毁

🏡链表为什么使用的是一级指针

🌸（1）单链表（非头单向不循环连链表）使用二级指针

🌸（2）带头双向循环连链表使用一级指针

🏡狡猾的面试官

🏡链表的源码

🌸main函数

🌸test.h文件

🌸test.c文件

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C语言中数据结构——带头双向循环链表

🐰带头双向循环链表

🏡概念

🏡链表结构体的定义

🏡链表为空的判断

🏡链表节点的创建

🏡链表的初始化

🏡链表的打印

🏡链表的尾插

🏡链表的头插

🏡链表的尾删

🏡链表的头删

🏡链表的查找

🏡链表中在pos之前插入

🏡删除pos的值

🏡链表的销毁

🏡链表为什么使用的是一级指针

🌸（1）单链表（非头单向不循环连链表）使用二级指针

🌸（2）带头双向循环连链表使用一级指针

🏡狡猾的面试官

🏡链表的源码

🌸main函数

🌸test.h文件

🌸test.c文件

热门文章

最新文章

相关课程

相关电子书