🚀🚀🚀大家觉不错的话，就恳求大家点点关注，点点小爱心，指点指点🚀🚀🚀
目录
🐰带头双向循环链表
🏡概念
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. }
🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区，我们共同探讨，共同学习，共同进步。谢谢大家！ 🌸🌸🌸
