一、双向链表介绍
什么是双向链表？
它是是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两个指针，一个指向前一个节点（pre指针），一个指向后一个节点（next指针）。
双向链表的基本结构？
一张图让你明白：
注：此为带哨兵的双向链表
注：next表示为指向下一个节点的指针，prev表示为指向上一个节点的指针，而head则是作为标兵的存在，里面不存数据，其他data存数据，此双向链表无指向NULL的指针，读者可在下文初始化双向链表得到疑惑的答案。
与单链表相比的优势？
- 双向遍历：由于每个节点都存储了前向和后向指针，可以从头到尾或者从尾到头方便地遍历链表。这样的遍历方式在某些场景下非常有用，特别是需要反向操作或者双向查找的情况。
- 方便插入和删除：在双向链表中，插入和删除操作相对容易。通过修改前后指针，可以方便地调整节点的连接关系，无需像单链表那样需要在删除节点时找到其前驱节点。
- 更灵活的操作：双向链表相比单链表，对于节点的操作更加灵活。例如，在单链表中，如果要删除某个节点，需要先找到它的前驱节点，而在双向链表中，可以直接通过节点本身进行删除操作。
- 提高性能：在某些情况下，双向链表可以提高性能。例如，在需要频繁从链表中删除节点或者在给定节点后插入新节点的情况下，双向链表可以更高效地完成这些操作。
总的来说，双向链表在一些特定场景下相比单链表具有更多的优势和灵活性，双向链表是单链表的优化！
二、总体思路
如何实现？
参照🍀双向链表前置知识：单链表 （这是个链接，快点！），我们同样需要实现增、删、查、改。同样的我们需要先定义好节点，以此得到基本的结构->接着定义好接口（定义完后发现比单链表简单多了）->最后按照接口实现每一个功能 。
节点的定义（结构体）
typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* _next; struct ListNode* _prev; }ListNode;
接口的定义
// 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos);
三、具体每个接口函数的实现
1、初始化（重点）
ListNode* ListCreate() { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (!node) { perror("malloc fail:"); exit(-1); } node->_next = node; node->_prev = node; return node; }
可以看到初始化的作用是建立了一个标兵，这个标兵没有被赋值，因为他的值是多少无关紧要，重点在于：他的next指针指向的是他自己，而prev指针指向的也是他自己。这说明了什么？这说明了双向链表的最开始就是在没有任何值的时候就只有一个标兵，也就是说双向链表的每一个指针都不是空的，都是有指向的，他们指向的地址不可能为NULL。
2、销毁链表
void ListDestory(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { ListNode* tmp = cur->_next; free(cur); cur = tmp; } free(pHead); }
3、查找功能（返回pos的地址）
ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { if (cur->_data == x) return cur; cur = cur->_next; } return NULL; }
4、插入节点的实现（基于查找功能）
ListNode* BuyNode(LTDataType x)//实现节点的获取 { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->_data = x; node->_next = NULL; node->_prev = NULL; return node; } void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyNode(x); ListNode* dist = pos->_prev; dist->_next = newnode; newnode->_prev = dist; newnode->_next = pos; pos->_prev = newnode; }
特别注意
注意：在实现了 插入的功能后，其实一切都简单了起来，比如头插等等，只需要几行代码就能完成操作，而下面的删除操作的实现对于头删等等都是仅需要几行代码就能实现，因此，我们如果要快速的写完一个单链表或者其他链表，最好是从插入和删除开始写！o.o
5、删除节点（基于查找功能）
void ListErase(ListNode* pos) { assert(pos); ListNode* posPrev = pos->_prev; ListNode* posNext = pos->_next; posPrev->_next = posNext; posNext->_prev = posPrev; free(pos); }
6、尾插
void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); //ListInsert(pHead, x);//此为简化，如要简化代码，此段带码后的代码可都不要 ListNode* newnode = BuyNode(x); pHead->_prev->_next = newnode; newnode->_prev=pHead->_prev; newnode->_next = pHead; pHead->_prev = newnode; }
7、尾删
void ListPopBack(ListNode* pHead) { assert(pHead); //ListErase(pHead->_prev);//此为简化，如要简化代码，此段带码后的代码可都不要 if (pHead->_prev != pHead) { ListNode* tmp = pHead->_prev; pHead->_prev = tmp->_prev; tmp->_prev->_next = pHead; free(tmp); tmp = NULL; } }
8、头插
void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); //ListInsert(pHead->_next, x);//此为简化，如要简化代码，此段带码后的代码可都不要 ListNode* newnode = BuyNode(x); newnode->_next=pHead->_next; newnode->_prev = pHead; pHead->_next->_prev = newnode; pHead->_next = newnode; }
9、头删
void ListPopFront(ListNode* pHead) { assert(pHead); //ListErase(pHead->_next);//此为简化，如要简化代码，此段带码后的代码可都不要 if (pHead->_next != pHead) { ListNode* node = pHead->_next; node->_next->_prev = pHead; pHead->_next = node->_next; free(node); node = NULL; } }
10、打印
void ListPrint(ListNode* pHead) { ListNode* cur = pHead->_next; printf("pHead<=>"); while (cur != pHead) { printf("%d<=>", cur->_data); cur = cur->_next; } printf("\n"); }
四、总体代码
1、头文件
#pragma once #define _CRT_SECURE_NO_WARNINGS 01 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> // 带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* _next; struct ListNode* _prev; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos);
2、主体函数文件
#include"list.h" ListNode* BuyNode(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->_data = x; node->_next = NULL; node->_prev = NULL; return node; } ListNode* ListCreate() { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (!node) { perror("malloc fail:"); exit(-1); } node->_next = node; node->_prev = node; return node; } void ListDestory(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { ListNode* tmp = cur->_next; free(cur); cur = tmp; } free(pHead); } void ListPrint(ListNode* pHead) { ListNode* cur = pHead->_next; printf("pHead<=>"); while (cur != pHead) { printf("%d<=>", cur->_data); cur = cur->_next; } printf("\n"); } void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); //ListInsert(pHead, x); ListNode* newnode = BuyNode(x); pHead->_prev->_next = newnode; newnode->_prev=pHead->_prev; newnode->_next = pHead; pHead->_prev = newnode; } void ListPopBack(ListNode* pHead) { assert(pHead); //ListErase(pHead->_prev); if (pHead->_prev != pHead) { ListNode* tmp = pHead->_prev; pHead->_prev = tmp->_prev; tmp->_prev->_next = pHead; free(tmp); tmp = NULL; } } void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); //ListInsert(pHead->_next, x); ListNode* newnode = BuyNode(x); newnode->_next=pHead->_next; newnode->_prev = pHead; pHead->_next->_prev = newnode; pHead->_next = newnode; } void ListPopFront(ListNode* pHead) { assert(pHead); //ListErase(pHead->_next); if (pHead->_next != pHead) { ListNode* node = pHead->_next; node->_next->_prev = pHead; pHead->_next = node->_next; free(node); node = NULL; } } ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { if (cur->_data == x) return cur; cur = cur->_next; } return NULL; } void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyNode(x); ListNode* dist = pos->_prev; dist->_next = newnode; newnode->_prev = dist; newnode->_next = pos; pos->_prev = newnode; } void ListErase(ListNode* pos) { assert(pos); ListNode* posPrev = pos->_prev; ListNode* posNext = pos->_next; posPrev->_next = posNext; posNext->_prev = posPrev; free(pos); }
3、测试用例
#include"list.h" void text() { ListNode* phead = ListCreate(); ListPushBack(phead, 1); ListPushBack(phead, 2); ListPushBack(phead, 3); ListPrint(phead); ListPopBack(phead); ListPrint(phead); ListPushFront(phead, 10); ListPushFront(phead, 20); ListPushFront(phead, 30); ListPrint(phead); ListPopFront(phead); ListPrint(phead); ListNode* pos = ListFind(phead, 20); if (pos) { ListInsert(pos, 300); } ListPrint(phead); ListErase(pos); ListPrint(phead); ListDestory(phead); } int main() { text(); return 0; }
测试结果：
感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
