2.11 在pos位置删除
在 pos 位置删除，只要找到 pos 的前一个节点 posPrev ，然后找到 pos 的后一个节点 posNext ，然后将这两个节点的 prev 和 next 建立正确的链接关系。然后释放 pos 节点，pos 节点置空。
但是注意，删除的位置不能是哨兵位。但是由于这里设计的原因，再传 phead 就显得有点不划算了，所以我们需要注意一下，pos 不能为哨兵位，自己控制好就可以了。
void ListErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); pos = NULL; }
同样的，这个接口也能复用于 尾删 和 头删 。
对于 尾删 来说，pos 位置就是 phead->prev ，为链表的尾，删除 phead->prev 位置，就是尾删：
void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);// 防止把哨兵位删掉 ListErase(phead->prev); }
对于 头删 来说，pos 位置就是 phead->next ，为链表的头，删除 phead->next 位置，就是头删：
// 头删 void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead);// 防止把哨兵位删掉 ListErase(phead->next); }
2.12 打印
打印整个链表，就只需要遍历链表，控制好循环的停止条件：
// 打印 void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d->", cur->data); cur = cur->next; } printf("\n"); }
2.13 销毁
我需要把 哨兵位 ，链表的节点 全部删除，那么我就要使用循环来删除。所以，销毁 双向链表 的思路 和 查找是差不多的，循环的结束条件为 != phead。在销毁的过程中，每次记住我当前节点的下一个节点，以便迭代。
但是当前接口函数中，哨兵位是不能正常删除的！！！
注意：由于在函数中，我释放了哨兵位，并要将其置空。释放是可以的，因为我知道哨兵位的地址，释放就可以，但是置空却完成不了。因为我的 哨兵位 是形参，改变形参并不能影响实参，所以我们还需要在主函数中将 哨兵位 置空(在这个部分就不展示了，马上会在完整代码中呈现)。
// 销毁 void ListDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead);// 只销毁了形参，没有销毁实参，这里只是象征性的销毁一下 phead = NULL; }
3. 完整代码
List.h
#pragma once /* * c++中带头双向循环链表命名方式为List，所以我们也采用这个命名方式 */ #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode; // 初始化 LTNode* ListInit();// 使用返回值处理 // 打印 void ListPrint(LTNode* phead); // 尾插 void ListPushBack(LTNode* phead, LTDataType x); // 尾删 void ListPopBack(LTNode* phead); // 头插 void ListPushFront(LTNode* phead, LTDataType x); // 头删 void ListPopFront(LTNode* phead); // 查找元素 LTNode* ListFind(LTNode* phead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(LTNode* pos); // 销毁双向链表 void ListDestroy(LTNode* phead);
List.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" // 初始化 LTNode* ListInit() { LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); // 双向带头循环链表的prev指向next，next指向prev // 但是这里只有一个节点，所以只能让它自己指向自己 if (phead == NULL) { perror("ListInit"); exit(-1); } phead->next = phead; phead->prev = phead; return phead; } // 创建新节点 LTNode* BuyListNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("ListPushBack"); exit(-1); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } // 打印 void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d->", cur->data); cur = cur->next; } printf("\n"); } // 尾插 void ListPushBack(LTNode* phead, LTDataType x) { assert(phead);// 一定不为空-->有哨兵位 //LTNode* tail = phead->prev;// 尾就是prev，由于是双向循环链表，所以头的prev就是尾 //LTNode* newnode = BuyListNode(x); phead tail newnode //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x); } // 尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);// 防止把哨兵位删掉 /*LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; free(tail); phead->prev = tailprev; tailprev->next = phead;*/ ListErase(phead->prev); } // 另一种写法 //void ListPopBack(LTNode* phead) //{ // assert(phead); // assert(phead->next != phead);// 防止把哨兵位删掉 // LTNode* tail = phead->prev; // // phead->prev = tail->prev; // tail->prev->next = phead; // // free(tail); //} // 头插 void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); /*LTNode* newnode = BuyListNode(x); LTNode* next = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode;*/ ListInsert(phead->next, x); } // 头删 void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); /*LTNode* next = phead->next; LTNode* nextNext = next->next; phead->next = nextNext; nextNext->prev = phead; free(next);*/ ListErase(phead->next); } // 查找 LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } // 在pos位置之前插入 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* posPrev = pos->prev; newnode->prev = posPrev; posPrev->next = newnode; newnode->next = pos; pos->prev = newnode; } // 在pos位置删除 void ListErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); pos = NULL; } // 销毁 void ListDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead);// 只销毁了形参，没有销毁实参 phead = NULL; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" // 测试尾插、尾删 void TestList1() { LTNode* plist = ListInit();// 哨兵位 ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); // 双向链表的缺点 // 当链表只剩下哨兵位时，链表为空 // 如果这时候进行删除，会把哨兵位删掉 // ListPopBack(plist); ListPrint(plist); } // 测试头插、任意位置删除 void TestList2() { LTNode* plist = ListInit();// 哨兵位 ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPushFront(plist, 5); ListPrint(plist); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); LTNode* pos = ListFind(plist, 2); if (pos) { ListErase(pos); } ListPrint(plist); ListDestroy(plist); plist = NULL;// 手动置空 } int main() { //TestList1(); TestList2(); return 0; }
4. 结语
到这里，本篇博客就到此结束了。其实双向链表中还可以增加判空和计算链表大小的接口，也很简单，我这里就不实现了，大家有兴趣可以试一下。
总体来说，双向链表的结构是非常完美的，一般我们说的存储数据的链表其实也就是双向链表，单链表一般是作为其他数据结构的子结构的。所以双向链表因其结构，对于数据管理是十分高效的。而且实现起来也十分便捷~
如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！
我是anduin，一名C语言初学者，我们下期见！
