一.前言
在前面的博客中，我们学习了顺序表和结构最简单的链表——单链表，但是单链表存在在着一些不足，比如单链表的插入和删除的操作，总是要找到指定节点的前驱或是后继，这样就会比较麻烦。
那么本篇文章所讲述的双向带头循环链表（以后简称双链表），就可以很好解决这个问题。
二.双向带头循环链表的结构
1.该链表有一个哨兵位节点，即头节点；
2.每个节点都包含一个prev 指针和 next 指针，分别指向当前节点的前驱和后继；
3.头节点的 prev 指向的是尾节点，尾节点的next 指向的是头节点，这样就实现了循环。
请看图示：
别看结构这么复杂，但其实它是一个很厉害的结构，代码实现会很简单。
三.接口实现
A.初始化 ListNodeinit 和销毁 Listdestroy
1.ListNodeinit
这个接口用来创建哨兵位头节点，并使该节点的 prev 和 next 都指向自己以实现循环的目的。
1. LNode* Buynewnode(DLdatatype x) //定义一个 malloc 新节点的函数，以便后续需要 2. { 3. LNode* newnode = (LNode*)malloc(sizeof(LNode)); 4. assert(newnode); 5. newnode->prev = NULL; 6. newnode->next = NULL; 7. newnode->data = x; 8. return newnode; 9. } 10. LNode* ListNodeinit() 11. { 12. LNode* phead = (LNode*)malloc(sizeof(LNode)); 13. assert(phead); 14. phead->prev = phead; //使其都指向自己 15. phead->next = phead; 16. phead->data = -1; 17. return phead; 18. }
2.Listdestroy
我们需要遍历链表，并定义一个next 来保存 cur 的下一个节点，在链表都free 完后，再销毁头节点；
注意：应该是从头节点的 next 开始遍历。
1. void ListNodedestroy(LNode* phead) 2. { 3. assert(phead); 4. 5. LNode* cur = phead->next; 6. while (cur != phead) 7. { 8. LNode* next = cur->next; 9. free(cur); 10. cur = next; 11. } 12. 13. free(phead); 14. phead = NULL; 15. }
B.插入
1.头插 ListNodepushfront
1.这里要头插就太简单了，但是我们最好保存一下头节点的 next ，这样就不应考虑链接时的顺序问题；
2.使头节点的 next 指向新节点，然后新节点的 prev 指向头节点；
3.新节点的 next 指向保存的节点，保存的节点的 prev 指向新节点；
这里并不需要考虑链表为空的情况，这就是双链表的强大之处。
1. void ListNodepushfront(LNode* phead, DLdatatype x) 2. { 3. assert(phead); 4. 5. LNode* newnode = Buynewnode(x); 6. 7. LNode* first = phead->next; //保存头节点的下一个 8. 9. phead->next = newnode; 10. newnode->prev = phead; 11. newnode->next = first; 12. first->prev = newnode; 13. } 14.
2.尾插 ListNodepushback
1.尾插就需要找尾；
2.这里的找尾很简单，就是头节点的 prev；
3.将尾节点与新节点链接起来。
1. void ListNodepushback(LNode* phead, DLdatatype x) 2. { 3. assert(phead); 4. 5. LNode* newnode = Buynewnode(x); 6. LNode* tail = phead->prev; 7. tail->next = newnode; 8. newnode->prev = tail; 9. newnode->next = phead; 10. phead->prev = newnode; 11. 12. }
3.插入 ListNodeinsert
1.再插入前需要写一个 find 函数，用来寻找指定的位置 pos；
2.找到 pos 的前驱 prev ；
3.将前驱，pos，新节点链接起来。
1. LNode* ListNodefind(LNode* phead,DLdatatype x) 2. { 3. assert(phead); 4. 5. LNode* cur = phead->next; 6. while (cur != phead) 7. { 8. if (cur->data == x) 9. { 10. return cur; 11. } 12. 13. cur = cur->next; 14. 15. } 16. 17. return NULL; 18. } 19. 20. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x) 21. { 22. assert(phead); 23. assert(pos); 24. 25. LNode* newnode = Buynewnode(x); 26. LNode* prev = pos->prev; 27. 28. prev->next = newnode; 29. newnode->prev = prev; 30. newnode->next = pos; 31. pos->prev = newnode; 32. }
总结：其实可以用一个插入接口就可以实现头插和尾插这两个接口。
C.删除
1.删除时要注意的点是不能把头节点也给删了，如果删了就破坏了双链表的结构；
2.如果是空链表也不能删除。
1.头删 ListNodepopfront
1.删除时保存其下一个节点；
2.链接头节点 phead 和 保存的下一个节点；
3.删除 phead 的next。
1. void ListNodepopfront(LNode* phead) 2. { 3. assert(phead); 4. assert(ListNodeempty(phead)); 5. if (phead->next == phead) 6. { 7. perror("ListNodepopfront"); 8. return; 9. } 10. 11. LNode* first = phead->next; 12. LNode* second = first->next; 13. phead->next = second; 14. second->prev = phead; 15. 16. free(first); 17. first = NULL; 18. 19. 20. }
2.尾删 ListNodepopback
1.找尾，即：phead的prev；
2.找尾节点的前驱 prev ，使其next指向phead，phead的prev指向该前驱；
1. void ListNodepopback(LNode* phead) 2. { 3. assert(phead); 4. assert(ListNodeempty(phead)); 5. 6. if (phead->next == phead) 7. { 8. perror("ListNodepopback"); 9. exit(-1); 10. } 11. 12. LNode* tail = phead->prev; 13. LNode* prev = tail->prev; 14. 15. prev->next = phead; 16. phead->prev = prev; 17. free(tail); 18. tail = NULL; 19. }
3.删除 ListNodeerase
1.调用 find 函数找到要删除的节点pos；
2.找到 pos 的前驱和后继；
3.链接其前驱，后继；
4.删除pos。
1. void ListNodeerase(LNode* pos, LNode* phead) 2. { 3. assert(phead); 4. assert(pos); 5. 6. if (phead->next == phead) 7. { 8. perror("ListNodeerase"); 9. exit(-1); 10. } 11. LNode* prev = pos->prev; 12. LNode* next = pos->next; 13. 14. prev->next = next; 15. next->prev = prev; 16. 17. free(pos); 18. pos = NULL; 19. }
总结：这里可以复用删除函数去实现头删和尾删。
D.打印 ListNodeprint
注意是从头节点的下一个节点开始遍历，且循环终止条件是看是否等于 phead，因为双链表没有 NULL。
1. void ListNodeprint(LNode* phead) 2. { 3. assert(phead); 4. LNode* cur = phead->next; 5. while (cur != phead) 6. { 7. printf("%d <=> ", cur->data); 8. cur = cur->next; 9. } 10. 11. printf("\n"); 12. 13. 14. }
四.源码
List.h
1. #pragma once 2. 3. 4. #include <stdio.h> 5. #include <stdlib.h> 6. #include <assert.h> 7. #include <stdbool.h> 8. 9. typedef int DLdatatype; 10. 11. typedef struct ListNode 12. { 13. struct ListNode* prev; 14. struct ListNode* next; 15. DLdatatype data; 16. }LNode; 17. 18. LNode* ListNodeinit(); 19. 20. void ListNodeprint(LNode* phead); 21. 22. void ListNodepushback(LNode*phead,DLdatatype x); 23. 24. void ListNodepushfront(LNode* phead, DLdatatype x); 25. 26. void ListNodepopback(LNode* phead); 27. 28. void ListNodepopfront(LNode* phead); 29. 30. LNode* ListNodefind(LNode* phead,DLdatatype x); 31. 32. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x); 33. 34. void ListNodeerase(LNode* pos, LNode* phead); 35. 36. void ListNodedestroy(LNode* phead);
List.c
1. #define _CRT_SECURE_NO_WARNINGS 2. 3. #include "List.h" 4. 5. LNode* Buynewnode(DLdatatype x) 6. { 7. LNode* newnode = (LNode*)malloc(sizeof(LNode)); 8. assert(newnode); 9. newnode->prev = NULL; 10. newnode->next = NULL; 11. newnode->data = x; 12. return newnode; 13. } 14. 15. LNode* ListNodeinit() 16. { 17. LNode* phead = (LNode*)malloc(sizeof(LNode)); 18. assert(phead); 19. phead->prev = phead; 20. phead->next = phead; 21. phead->data = -1; 22. return phead; 23. } 24. 25. void ListNodeprint(LNode* phead) 26. { 27. assert(phead); 28. LNode* cur = phead->next; 29. while (cur != phead) 30. { 31. printf("%d <=> ", cur->data); 32. cur = cur->next; 33. } 34. 35. printf("\n"); 36. 37. 38. } 39. 40. void ListNodepushback(LNode* phead, DLdatatype x) 41. { 42. assert(phead); 43. 44. /*LNode* newnode = Buynewnode(x); 45. LNode* tail = phead->prev; 46. tail->next = newnode; 47. newnode->prev = tail; 48. newnode->next = phead; 49. phead->prev = newnode;*/ 50. 51. ListNodeinsert(phead, phead, x); 52. 53. 54. } 55. 56. void ListNodepushfront(LNode* phead, DLdatatype x) 57. { 58. assert(phead); 59. 60. /*LNode* newnode = Buynewnode(x); 61. 62. LNode* first = phead->next; 63. 64. phead->next = newnode; 65. newnode->prev = phead; 66. newnode->next = first; 67. first->prev = newnode;*/ 68. 69. ListNodeinsert(phead->next, phead, x); 70. } 71. 72. bool ListNodeempty(LNode* phead) 73. { 74. assert(phead); 75. 76. return phead->next == phead; 77. } 78. 79. void ListNodepopback(LNode* phead) 80. { 81. assert(phead); 82. //assert(ListNodeempty(phead)); 83. 84. if (phead->next == phead) 85. { 86. perror("ListNodepopback"); 87. exit(-1); 88. } 89. 90. /*LNode* tail = phead->prev; 91. LNode* prev = tail->prev; 92. 93. prev->next = phead; 94. phead->prev = prev; 95. free(tail); 96. tail = NULL;*/ 97. 98. ListNodeerase(phead->prev, phead); 99. } 100. 101. void ListNodepopfront(LNode* phead) 102. { 103. assert(phead); 104. //assert(ListNodeempty(phead)); 105. if (phead->next == phead) 106. { 107. perror("ListNodepopfront"); 108. return; 109. } 110. 111. /*LNode* first = phead->next; 112. LNode* second = first->next; 113. phead->next = second; 114. second->prev = phead; 115. 116. free(first); 117. first = NULL;*/ 118. 119. ListNodeerase(phead->next, phead); 120. } 121. 122. LNode* ListNodefind(LNode* phead,DLdatatype x) 123. { 124. assert(phead); 125. 126. LNode* cur = phead->next; 127. while (cur != phead) 128. { 129. if (cur->data == x) 130. { 131. return cur; 132. } 133. 134. cur = cur->next; 135. 136. } 137. 138. return NULL; 139. } 140. 141. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x) 142. { 143. assert(phead); 144. assert(pos); 145. 146. LNode* newnode = Buynewnode(x); 147. LNode* prev = pos->prev; 148. 149. prev->next = newnode; 150. newnode->prev = prev; 151. newnode->next = pos; 152. pos->prev = newnode; 153. } 154. 155. void ListNodeerase(LNode* pos, LNode* phead) 156. { 157. assert(phead); 158. assert(pos); 159. 160. if (phead->next == phead) 161. { 162. perror("ListNodeerase"); 163. exit(-1); 164. } 165. LNode* prev = pos->prev; 166. LNode* next = pos->next; 167. 168. prev->next = next; 169. next->prev = prev; 170. 171. free(pos); 172. pos = NULL; 173. } 174. 175. void ListNodedestroy(LNode* phead) 176. { 177. assert(phead); 178. 179. LNode* cur = phead->next; 180. while (cur != phead) 181. { 182. LNode* next = cur->next; 183. free(cur); 184. cur = next; 185. } 186. 187. free(phead); 188. phead = NULL; 189. 190. }
test.c
至于test.c 就不贴出来了，这里面主要是一些测试接口的代码，没必要贴出来。
😽本篇文章到此就结束了，若有错误或是建议，欢迎小伙伴们指出；😻
😍请多多支持博主哦~🥰
🤩谢谢你的阅读~😃
