一、双向链表概述双向链表与单链表类似每个节点由结构体组成。单链表节点的结构体主要包括一个指针指向下一个节点、存储的数据单链表是单向指向双链表的的节点的结构体主要包含前指针指向前一个节点、后指针指向后一个节点、存储的数据双链表是双向指向。以及引入哨兵位节点作为头节点不存储数据概念如下所示注意在双链表中我们一般将哨兵位节点称为头节点有数据存贮的节点叫第一个节点如上图存储数据1的节点。注意看最后一个节点的后指针指向哨兵为节点哨兵位节点的前指针指向组后一个节点。双向链表主要完成的功能与单链表类似主要有头插、尾插、头删、尾删、查找节点、在指定位置插入节点、删除指定位置节点等等总体功能代码如下//插入节点 //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头插 void LTPushFront(LTNode* phead, LTDataType x); //删除 //头删 void LTPopBack(LTNode* phead); //尾删 void LTPopFront(LTNode* phead); bool LTEmpty(LTNode* phead); //查找某数据 LTNode* LTFind(LTNode* phead, LTDataType x); //在pos之后插入节点 void LTInsert(LTNode* pos, LTDataType x); //删除指定位置节点 void LTErase(LTNode* pos);二、双向链表结构的定义上面已经赘述了双向链表的组成代码如下//定义双链表结构 typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode;注意点在结构体中定义前后指针时的数据类型必须用struct ListNode* next;不能用LTNode*next;毕竟计算机在读取你这段代码时先读取到struct ListNode* next然后才读取到你对struct ListNode 的重新命名。如果你要写LTNode* next可以在结构体之前将struct ListNode命名好即typedef struct ListNode LTNode。三、创建新的节点双向链表在插入操作时需要引进新的节点我们用一个函数LTBuyNode来封装方便之后各种插入、初始化调用。先看代码//创建一个节点 LTNode* LTBuyNode(LTDataType x) { LTNode* newnode (LTNode*)malloc(sizeof(LTNode)); if (newnode NULL) { perror(malloc fail!); exit(1); } newnode-data x; //prev next newnode-next newnode-prev newnode; return newnode; }主要讲两个点1申请新的节点空间为什么用malloc函数不用relloc函数详细解释可以看前面的文章-顺序表答简单来说我们链表申请新的空间只需要申请指定位置大小的空间就好了malloc主要向内存申请指定空间所以用malloc函数。2由于是双向链表我们创建一个新的节点这个节点的前指针和后指针都要指向他自己即newnode-next newnode-prev newnode;最后将创建的节点返回即可。四、双向链表的初始化代码如下//初始化 LTNode* LTInit() { LTNode* phead LTBuyNode(-1); return phead; }我们初始化的是哨兵位节点由于其不存储数据我们传一个负数就好不是有效数据。五、双向链表的打印打印双向链表我们需要弄清楚链表循环结束的条件这里是pcur!phead,即再次返回到哨兵位节点时已经遍历一遍双向链表了其代码如下//打印链表 void LTPrint(LTNode* phead) { LTNode* pcur phead-next; while (pcur ! phead) { printf(%d-, pcur-data); pcur pcur-next; } printf(\n); }六、数据的查找我们查找一个数据最后返回的是这个节点记得assert(phead),查找数据头节点不能为空要不然查找个毛线。//查找某数据 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead);//查找数据头节点不能为空 LTNode* pcur phead-next; while (pcur ! phead) { if (pcur-data x) return pcur; pcur pcur-next; } return NULL; }循环结束的条件是pcur!phead因为最后一个节点的后指针指向phead,当再次指向phead后表面遍历完毕。如果没找到记得返回NULL。七、双向链表的插入插入操作哨兵节点一定存在地址不为空所以需要assertphead)断言。1、尾插操作先看代码对代码作详细解释//插入操作 //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); //phead phead-prev newnode newnode-next phead; newnode-prev phead-prev; phead-prev-next newnode;//注意这里是phead-prev-next phead-prev newnode; }首先申请一个新的节点LTNode* newnode LTBuyNode(x);其次将新节点的后指针指向哨兵位节点newnode-next phead;新节点的前指针指向原来链表的最后一个节点newnode-prev phead-prev;这里的phead-prev就是原来链表的最后一个节点。最后将原链表的最后一个节点的后指针指向新节点phead-prev-next newnode;注意一下这里是phead-prev-next。将哨兵位节点的前指针指向新节点phead-prev newnode;。注意操作的顺序。2、头插操作头插操作是在哨兵位节点后、第一个节点前进行插入。先看代码再详细解释//头插 void LTPushFront(LTNode* phead, LTDataType x) { LTNode* newnode LTBuyNode(x); LTNode* next phead-next; newnode-prev phead; newnode-next next; phead-next newnode; next-prev newnode; }首先申请一个新的节点LTNode* newnode LTBuyNode(x);并记录原链表的第一个节点地址LTNode* next phead-next;其次将新节点的前指针指向哨兵位节点newnode-prev phead;新节点的后指针指向原链表的第一个节点newnode-next next;最后将哨兵位节点的后指针指向新节点phead-next newnode;原链表的第一个节点next的前指针指向新节点next-prev newnode;。3、指定位置的插入指定位置的插入与上面的操作大相径庭代码如下//在pos之后插入节点 void LTInsert(LTNode* pos, LTDataType x) { LTNode* next pos-next; LTNode* newnode LTBuyNode(x); newnode-prev pos; newnode-next next; pos-next newnode; next-prev newnode; }八、双向链表的删除执行删除操作前必须判断链表是否为空为空不能删除。还有一点删除操作不删除哨兵位节点。我们间判断链表是否为空的操作封装在LTEmpty函数中删除操作都需要调用代码如下//为删除操作做准备 //删除操作不可以删除头节点 bool LTEmpty(LTNode* phead) { assert(phead); return phead-next phead; }这里return phead-nextphead表面链表为空哨兵位节点自己指向自己。1、头删操作头删操作删的是原链表的第一个节点不是头节点哨兵位节点。代码如下//头删 void LTPopBack(LTNode* phead) { assert(phead);//删除操作头节点不能为空 assert(!LTEmpty(phead));//删除头节点报错 LTNode* pcur phead-next; phead-next pcur-next; pcur-next-prev phead; free(pcur); pcur NULL; }首先记录原链表的第一个节点LTNode* pcur phead-next;然后将哨兵位的后指针指向原链表的第二个节点phead-next pcur-next;原链表的第二个节点的前指针指向哨兵位节点pcur-next-prev phead;最后free(pcur)即可记得将pcur赋NULL。2、尾删操作尾删操作记得最后找最后一个节点即phead-prve。代码如下//尾删 void LTPopFront(LTNode* phead) { assert(phead);//删除操作头节点不能为空 assert(!LTEmpty(phead));//删除头节点报错 LTNode* ptail phead-prev; phead-prev ptail-prev; ptail-prev -next phead; free(ptail); ptail NULL; }首先记录原链表最后一个节点LTNode* ptail phead-prev;然后将哨兵位节点的前指针指向原链表倒数第二个节点phead-prev ptail-prev;原链表倒数第二个节点的后指针指向哨兵位节点ptail-prev -next phead;最后将最后一个节点free掉并将其赋NULL。3、删除指定位置数据代码类似如下//删除指定位置节点 void LTErase(LTNode* pos) { assert(pos); pos-prev-next pos-next; pos-next-prev pos-prev; free(pos); pos NULL; }做个小总结我们在指向插入删除操作时要根据情况记录要插入或者删除数据的前一个节点或者后一个节点。九、双向链表的销毁销毁操作先销毁各个节点然后把再销毁哨兵位节点。销毁时候传参有两种第一种实参传一级指针地址用二级指针接收第二种是传一级指针销毁操作大致相似。1第一种实参传一级指针地址用二级指针接收我们可以在形参的函数中方直接将传过来的指针销毁赋NULL。void LTDesTroy(LTNode** pphead) { assert(pphead *pphead); LTNode* pcur (*pphead)-next; while (pcur ! *pphead) { LTNode* Next pcur-next; free(pcur); pcur Next; } //销毁哨兵位节点 free(*pphead); *pphead NULL; pcur NULL; pphead NULL; }这里ppheadNULL就是将传过来的实参赋NULL。2第二种需要在原函数传实参的函数将所传的指针赋NULL。void LTDesTroy2(LTNode* phead) { assert(phead); LTNode* pcur phead-next; while (pcur ! phead) { LTNode* Next pcur-next; free(pcur); pcur Next; } free(phead); phead pcur NULL; }LTDesTroy2(plist); plist NULL;如这里的plistNULL,如果不是很理解可以观看总代码。十、总代码将代码分装在三个文件中List.c双向链表的各种工能实现。List.h:双向链表的创建以及各种功能函数的声明。test.c函数功能的测试。List.c代码如下#define _CRT_SECURE_NO_WARNINGS 1 #include List.h //创建一个节点 LTNode* LTBuyNode(LTDataType x) { LTNode* newnode (LTNode*)malloc(sizeof(LTNode)); if (newnode NULL) { perror(malloc fail!); exit(1); } newnode-data x; //prev next newnode-next newnode-prev newnode; return newnode; } //初始化 LTNode* LTInit() { LTNode* phead LTBuyNode(-1); return phead; } //打印链表 void LTPrint(LTNode* phead) { LTNode* pcur phead-next; while (pcur ! phead) { printf(%d-, pcur-data); pcur pcur-next; } printf(\n); } //插入操作 //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); //phead phead-prev newnode newnode-next phead; newnode-prev phead-prev; phead-prev-next newnode;//注意这里是phead-prev-next phead-prev newnode; } //头插 void LTPushFront(LTNode* phead, LTDataType x) { LTNode* newnode LTBuyNode(x); LTNode* next phead-next; newnode-prev phead; newnode-next next; phead-next newnode; next-prev newnode; } //为删除操作做准备 //删除操作不可以删除头节点 bool LTEmpty(LTNode* phead) { assert(phead); return phead-next phead; } //删除 //头删 void LTPopBack(LTNode* phead) { assert(phead);//删除操作头节点不能为空 assert(!LTEmpty(phead));//删除头节点报错 LTNode* pcur phead-next; phead-next pcur-next; pcur-next-prev phead; free(pcur); pcur NULL; } //尾删 void LTPopFront(LTNode* phead) { assert(phead);//删除操作头节点不能为空 assert(!LTEmpty(phead));//删除头节点报错 LTNode* ptail phead-prev; phead-prev ptail-prev; ptail-prev -next phead; free(ptail); ptail NULL; } //查找某数据 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead);//查找数据头节点不能为空 LTNode* pcur phead-next; while (pcur ! phead) { if (pcur-data x) return pcur; pcur pcur-next; } return NULL; } //在pos之后插入节点 void LTInsert(LTNode* pos, LTDataType x) { LTNode* next pos-next; LTNode* newnode LTBuyNode(x); newnode-prev pos; newnode-next next; pos-next newnode; next-prev newnode; } //删除指定位置节点 void LTErase(LTNode* pos) { assert(pos); pos-prev-next pos-next; pos-next-prev pos-prev; free(pos); pos NULL; } void LTDesTroy(LTNode** pphead) { assert(pphead *pphead); LTNode* pcur (*pphead)-next; while (pcur ! *pphead) { LTNode* Next pcur-next; free(pcur); pcur Next; } //销毁哨兵位节点 free(*pphead); *pphead NULL; pcur NULL; pphead NULL; } void LTDesTroy2(LTNode* phead) { assert(phead); LTNode* pcur phead-next; while (pcur ! phead) { LTNode* Next pcur-next; free(pcur); pcur Next; } free(phead); phead pcur NULL; }Slist.h代码如下#pragma once #include stdio.h #include stdlib.h #include stdbool.h #include assert.h //定义双链表结构 typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode; //初始化 LTNode* LTInit(); //打印双链表 void LTPrint(LTNode* phead); //插入节点 //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头插 void LTPushFront(LTNode* phead, LTDataType x); //删除 //头删 void LTPopBack(LTNode* phead); //尾删 void LTPopFront(LTNode* phead); bool LTEmpty(LTNode* phead); //查找某数据 LTNode* LTFind(LTNode* phead, LTDataType x); //在pos之后插入节点 void LTInsert(LTNode* pos, LTDataType x); //删除指定位置节点 void LTErase(LTNode* pos); //销毁 void LTDesTroy(LTNode** pphead); void LTDesTroy2(LTNode* phead);//传一级需要手动将plist置为NULLtest.c代码如下#define _CRT_SECURE_NO_WARNINGS 1 #include List.h void test1() { LTNode* plist LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPrint(plist);//1-2-3-4- LTNode* posLTFind(plist,3);//查找数据 LTInsert(pos, 7);//在pos后面插入7 LTPrint(plist);//1-2-3-7-4- LTErase(pos);//删除pos节点 LTPrint(plist);//1-2-7-4- //第一种销毁 // LTDesTroy(plist); //第二种销毁 LTDesTroy2(plist); plist NULL; } void test2() { LTNode* plist LTInit(); LTPushFront(plist, 1); LTPrint(plist); LTPushFront(plist, 2); LTPrint(plist); LTPushFront(plist, 3); LTPrint(plist); LTPushFront(plist, 4); LTPrint(plist);//4-3-2-1- //头删 LTPopBack(plist); LTPrint(plist);//3-2-1- //尾删 LTPopFront(plist);//3-2- LTPrint(plist); } int main() { //尾插操作 test1(); //头插操作 //test2(); return 0; }文章有错欢迎留言联系各位佬多多指教。