前言
双向链表是一种带头双向循环的链表。在双向链表中，首先存在着一个头结点；其次每个节点有指向下一个节点的指针next 和指向上一个节点的指针prev ；最后，双向链表的头结点中存放上一个节点的指针指向链表的尾节点，尾节点中存放下一个节点的指针指向链表的头结点，形成一个闭环。这样双向链表既可以从前遍历，也可以从后遍历，直到回到起点。
一、链表的分类
链表的结构多种多样，链表呢可以是带头（不带头）、双向（单向）、循环（不循环）的，我们之前实现的单链表其实就是不带头，单向，不循环的链表。 
而这些有什么区别呢？
带头和不带头
这里带头和不带头指的是有没有头结点，这单链表的实现过程中，是直接创建一个指针变量指向链表的第一个节点（这是没有头结点的情况），而存在头结点呢，就是一个哨兵位，里面没有存放数据，存放了指向第一个节点的指针。 
可以看到，带头的链表多了一个节点（head），这个节点中没有存放任何数据，这样做可以方便对链表的节点进行统一操作。
单向和双向
单向是可以通过一个节点找到它的后一个节点，而双向是可以通过一个节点找到它前后的节点。 
循环和不循环
这实现单链表的时候，我们将链表的最后一个节点next指针置位了空指针（NULL），而循环的链表中，我们会将最后一个节点的next指针指向链表的头结点，对于双向链表，将头节点的prev(上一个节点）指针指向链表的尾节点。 
二、双向链表的实现
这里实现的双向链表，先来看一下双向链表的节点结构
双向链表节点
typedef int LTDataType; //双向链表 typedef struct ListNode { struct ListNode* prev; //指向上一个节点 struct ListNode* next; //指向下一个节点 LTDataType data; }LTNode;
双向链表的功能预览
//初始化并创建头结点 void LTInit(LTNode** phead); //LTNode* LTInit(); //输出 void LTPrint(LTNode* phead); //创建新的节点 LTNode* LTBuyNode(LTDataType x); //头插 void LTPushFront(LTNode* phead, LTDataType x); //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头删 void LTPopFront(LTNode* phead); //尾删 void LTPopBack(LTNode* phead); //查找 LTNode* LTFind(LTNode* phead, LTDataType find); //在pos节点之后插入数据 void LTPushAfter(LTNode* pos, LTDataType x); //在pos节点之前插入数据 void LTPush(LTNode* pos, LTDataType x); //删除pos节点 void LTPop(LTNode* pos); //链表销毁 void LTDesTroy(LTNode* phead);
2.1、创建新的节点
创建节点，和单链表一样，都是动态开辟的空间。
//创建新的节点 LTNode* LTBuyNode(LTDataType x) { LTNode* ptail = (LTNode*)malloc(sizeof(LTNode)); if (ptail == NULL) { perror("LTBuyNode--malloc filed!"); exit(1); } ptail->data = x; ptail->prev = ptail->next = NULL; return ptail; }
2.2、双向链表初始化并创建头结点
链表初始化，其实就是创建一个头节点（也叫哨兵位）；因为这里是双向链表，创建完头节点之后，让头节点的prev和next指针都指向它自己。
//初始化并创建头结点 void LTInit(LTNode** phead) { *phead = LTBuyNode(-1); (*phead)->prev = (*phead)->next = *phead; }
2.3、输出链表
遍历链表并输出有效数据，这里双向链表可以从前开始遍历也可以从后开始遍历。
//输出 void LTPrint(LTNode* phead) { LTNode* ptail = phead->next; //遍历双向链表 -- 从前开始遍历 while (ptail != phead) { printf("%d -> ", ptail->data); ptail = ptail->next; } printf("\n"); }
2.4、双向链表头插数据
从链表的头部插入数据，创建新的节点，然后将新的节点prev指针指向头节点，将next指针指向头节点的下一个节点；然后修改头节点的next指针和头节点下一个节点的prev指针即可。
//头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->prev = phead; newnode->next = phead->next; //修改前后节点的指针指向 phead->next->prev = newnode; phead->next = newnode; }
2.5、双向链表尾插数据
从链表尾部插入到尾节点的后面，创建新的节点，将新节点的prev指针指向头节点的上一个节点，将next指针指向头节点，然后修改尾节点的next指针和头节点的prev指针即可。
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->prev = phead->prev; newnode->next = phead; //修改前后节点指针指向 phead->prev->next = newnode; phead->prev = newnode; }
2.6、双向链表头删数据
头删是删除头节点的后一个节点，因为是动态开辟的内存，需要内存释放；删除后，让头节点的next指针 指向下一个数据的节点。
//头删 void LTPopFront(LTNode* phead) { assert(phead && phead != phead->next); //链表为空的话就不能进行删除 LTNode* del = phead->next; phead->next->next->prev = phead; phead->next = phead->next->next; free(del); del = NULL; }
2.7、双向链表尾删数据
尾插是删除链表的尾节点，释放内存之后，让尾节点的上一个节点next指针指向头节点，头节点的prev指针指向删除节点的上一个节点。
//尾删 void LTPopBack(LTNode* phead) { assert(phead && phead->next != phead); //链表为空不能进行删除 LTNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; free(del); del = NULL; }
2.8、双向链表查找数据
这里如果找到了，就返回该节点的指针，如果没有就返回NULL；方便对其进行前后插入数据和删除。
//查找 LTNode* LTFind(LTNode* phead, LTDataType find) { assert(phead); LTNode* ptail = phead->next; while (ptail != phead) //遍历链表 { if (ptail->data == find) { return ptail; } ptail = ptail->next; } return NULL; }
2.9、在指定节点pos之前插入数据
根据我们查找到的节点，在其之前插入数据，首先创建新节点，将新节点的prev指针指向pos的前一个节点，新节点的next指针指向pos；再修改pos的上一个节点的next指针指向和pos的prev指针指向即可；
//在pos节点之前插入数据 void LTPush(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos; newnode->prev = pos->prev; //修改pos前后节点指针的指向 pos->prev->next = newnode; pos->prev = newnode; }
这里就可以发现双向链表的一个好处，不用像单向链表那样遍历链表来寻找pos的上一个节点。
2.10、在指定节点pos之后插入数据
根据查找到的节点，在其之后插入数据；首先创建节点，将新节点的prev指针指向pos，新节点的next指针指向pos的下一个节点；然后修改pos的next指针指向和pos下一个节点的prev指针指向即可。
//在pos节点之后插入数据 void LTPushAfter(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; //修改pos前后节点指针的指向 pos->next->prev = newnode; pos->next = newnode; }
2.11、删除指定节点pos
根据查找到的节点，然后将其删除，这里需要修改pos前后节点的指针指向。
//删除pos节点 void LTPop(LTNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; }
2.12、双向链表的销毁
及时对动态开辟的内存进行释放，养成好习惯
现在，动态开辟的链表需要进行销毁（也就是动态内存释放），这里就需要遍历链表了。
//链表销毁 void LTDesTroy(LTNode* phead) { assert(phead); LTNode* ptail = phead->next; while (ptail != phead) { LTNode* del = ptail->next; free(ptail); ptail = del; } free(ptail); ptail = NULL; }
代码总览
List.h
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDataType; //双向链表 typedef struct ListNode { struct ListNode* prev; //指向上一个节点 struct ListNode* next; //指向下一个节点 LTDataType data; }LTNode; //初始化并创建头结点 void LTInit(LTNode** phead); //LTNode* LTInit(); //输出 void LTPrint(LTNode* phead); //创建新的节点 LTNode* LTBuyNode(LTDataType x); //头插 void LTPushFront(LTNode* phead, LTDataType x); //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头删 void LTPopFront(LTNode* phead); //尾删 void LTPopBack(LTNode* phead); //查找 LTNode* LTFind(LTNode* phead, LTDataType find); //在pos节点之后插入数据 void LTPushAfter(LTNode* pos, LTDataType x); //在pos节点之前插入数据 void LTPush(LTNode* pos, LTDataType x); //删除pos节点 void LTPop(LTNode* pos); //链表销毁 void LTDesTroy(LTNode* phead);
List.c
#include"List.h" //创建新的节点 LTNode* LTBuyNode(LTDataType x) { LTNode* ptail = (LTNode*)malloc(sizeof(LTNode)); if (ptail == NULL) { perror("malloc filed!"); exit(1); } ptail->data = x; ptail->prev = ptail->next = NULL; return ptail; } //初始化并创建头结点 void LTInit(LTNode** phead) { *phead = LTBuyNode(-1); (*phead)->prev = (*phead)->next = *phead; } //输出 void LTPrint(LTNode* phead) { LTNode* ptail = phead->next; //遍历双向链表 -- 从前开始遍历 while (ptail != phead) { printf("%d -> ", ptail->data); ptail = ptail->next; } printf("\n"); } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->prev = phead; newnode->next = phead->next; //修改前后节点的指针指向 phead->next->prev = newnode; phead->next = newnode; } //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->prev = phead->prev; newnode->next = phead; //修改前后节点指针指向 phead->prev->next = newnode; phead->prev = newnode; } //头删 void LTPopFront(LTNode* phead) { assert(phead && phead != phead->next); //链表为空的话就不能进行删除 LTNode* del = phead->next; phead->next->next->prev = phead; phead->next = phead->next->next; free(del); del = NULL; } //尾删 void LTPopBack(LTNode* phead) { assert(phead && phead->next != phead); //链表为空不能进行删除 LTNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; free(del); del = NULL; } //查找 LTNode* LTFind(LTNode* phead, LTDataType find) { assert(phead); LTNode* ptail = phead->next; while (ptail != phead) //遍历链表 { if (ptail->data == find) { return ptail; } ptail = ptail->next; } return NULL; } //在pos节点之前插入数据 void LTPush(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos; newnode->prev = pos->prev; //修改pos前后节点指针的指向 pos->prev->next = newnode; pos->prev = newnode; } //在pos节点之后插入数据 void LTPushAfter(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; //修改pos前后节点指针的指向 pos->next->prev = newnode; pos->next = newnode; }
感谢各位大佬支持并指出问题，
