数据结构-双向链表【详细解析，包含注意事项】
一、双向链表概述
双向链表与单链表类似，每个节点由结构体组成。单链表节点的结构体主要包括一个指针（指向下一个节点）、存储的数据，单链表是单向指向；双链表的的节点的结构体主要包含前指针（指向前一个节点）、后指针（指向后一个节点）、存储的数据，双链表是双向指向。以及引入哨兵位节点（作为头节点，不存储数据）概念，如下所示：
注意：在双链表中我们一般将哨兵位节点称为头节点，有数据存贮的节点叫第一个节点（如上图存储数据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。
七、双向链表的插入
插入操作哨兵节点一定存在，地址不为空，所以需要assert（phead)断言。
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->next=phead，表面链表为空（哨兵位节点自己指向自己）。
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; }这里pphead=NULL就是将传过来的实参赋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;如这里的plist=NULL,如果不是很理解可以观看总代码。
十、总代码
将代码分装在三个文件中：
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* pos=LTFind(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; }文章有错欢迎留言联系，各位佬多多指教。