学习完单链表，现在继续学习双链表
一、双链表结构
带头双向循环链表（简称：双链表）
注意：这⾥的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨 的” “哨兵位”存在的意义： 遍历循环链表避免死循环。
二、双链表的实现
定义双链表节点结构
与单链表相比，双链表由于是双向的，因此它多了一个前驱指针
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;//保存指向前一个节点的指针
struct ListNode* next;//指向下一个节点的指针
}LTNode;说明
双链表是带头链表，即它的头节点（哨兵节点）是不可变的，它作用是站岗放哨，为后续的有效节点标明位置，因此，与单链表不同的是，双链表在函数传参的过程中传的是一级指针，不再是二级指针（保证哨兵节点不可改变）
在接下来的双链表实现中，为保持接口一致性，全部传一级指针
双链表初始化 InitList
单链表为空的意思就是空链表，链表内无任何节点，而双链表为空时，此时链表中只剩下一个头节点（哨兵节点），无有效节点，代表双链表为空的意思
因此，在插入数据之前，双链表必须初始化到只有一个头结点的情况
创建一个函数LTBuyNode，表示申请节点，在初始化时给链表申请一个哨兵节点
思考一下，是否可以将哨兵节点的prev指针和next指针初始化为NULL？显然是不可以的
双链表是循环链表，它的首尾相连的，因此，链表的prev指针和next指针应该在初始化时指向哨兵节点本身
//申请节点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if(node == NULL)
{
perror("LTBuyNode-malloc");
exit(1);
}
node->data = x;
node->next = node->prev = node;
return node;
}
//初始化 - 传一级指针的写法
LTNode* InitList()
{
LTNode* phead = LTBuyNode(-1);//也可以传其他数字，表示初始化哨兵节点为某一个值
return phead;
}
//初始化 - 传二级指针的写法
void InitList(LTNode** pphead)
{
//给双链表创建一个哨兵节点
*pphead = LTBuyNode(-1);
}测试：
//初始化
LTNode* plist = InitList();
//LTNode* plist = NULL;
//InitList(&plist);
打印链表 LTPrint
打印链表的步骤基本上和单链表相同，但是要注意，打印双链表的节点时，哨兵节点并不需要打印出来，是从链表的第一个有效节点开始打印（即哨兵节点的后一个节点）；
在while循环条件部分不同：双链表头尾相连，如果按照单链表的循环条件pcur进行打印，会陷入无限循环，因此，我们要在尾节点的next指针为头节点时，停止打印
void LTPrint(LTNode* phead)
{
LTNode* pcur = phead->next;
while(pcur != phead)
{
printf("%d->",pcur->data);
pcur = pcur->next;
}
printf("\n");
}尾部插入/头部插入
尾插 LTPushBack
我们知道，链表的尾节点的next指针就是头节点phead（尾节点->next=phead），头节点phead的prev指针就是尾节点（即phead->prev=尾节点）【首尾相连】，我们要做的就是将创建的新节点newnode尾插到原链表的尾部作为新的尾节点并与头节点首尾相连。
首先要做的是将newnode尾插到原链表中，将newnode的prev指针指向phead->prev（原尾节点），然后将newnode的next指针指向头节点phead，这样就将newnode节点插入到了原链表中
接着更新新的尾节点与头节点头尾相连，将原链表的尾节点phead->prev的next指针指向newnode，然后newnode成为新的尾节点 phead->prev
void LTPushBack(LTNode* phead,LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//1.先在尾部插入新节点
newnode->prev = phead->prev;
newnode->next = phead;
//2.更新新的尾节点与头节点进行首尾相连
phead->prev->next = newnode;
phead->prev = newnode;
}
头插 LTPushFront
要注意，我们所说的头插是头插到第一个有效节点的前面，即头节点（哨兵节点）的后面
（将新节点插入到哨兵节点前面，就是尾插）
首先还是将新节点newnode插入到原链表中，将newnode插入到头节点phead和第一个有效节点phead->next之间，然后更新newnode为新的第一个有效节点：
将phead->next(原第一个有效节点)的prev指针指向newnode，再将newnode的prev指针指向phead，或者先将newnode的prev指针指向phead，再通过newnode找到原第一个有效节点（newnode->next），将newnode->next的prev指针指向newnode
void LTPushFront(LTNode* phead,LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//1.先在头节点和第一个有效节点之间插入一个新节点，表示头插
newnode->next = phead->next;
newnode->prev = phead;
//2.更新新的节点为新的第一个有效节点
phead->next->prev = newnode;
phead->next = newnode;
//phead->next = newnode;
//newnode->next->prev = newnode;
}
尾部删除/头部删除
尾删 LTPopBack
能够进行尾删的条件：链表有效且链表不能为空（只有一个哨兵节点）
要将尾节点（phead->prev）删除，将它的前一个节点phead->prev->prev变成新的尾节点：将phead->prev->prev的next指针指向phead，将phead的prev指针指向phead->prev->prev，然后将原尾节点释放掉
但是，要注意，此时已经找不到原尾节点的位置了，无法进行释放操作，因此，在进行以上操作前，先将原尾节点phead->prev存放在一个指针变量del中
void LTPopBack(LTNode* phead)
{
//链表必须有效且链表不能为空（只有一个哨兵位）
assert(phead && phead->next != phead);
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
//删除del节点
free(del);
del = NULL;
}
头删 LTPopFront
能够进行头删的条件：链表有效且链表不能为空
头删是删除链表的第一个有效节点，使第二个有效节点成为新的第一个有效节点
首先先将要删除的phead->next节点存放在指针del中，然后将phead的next指针改为del->next(第二个有效节点)，再将del->next的prev指针指向phead，然后将del释放掉
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != phead);
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
查找链表 LTFind
通过遍历链表找到想要找的节点数据，如果找到了，返回这个节点的指针，如果没有找到，返回NULL
LTNode* LTFind(LTNode* phead,LTDataType x)
{
LTNode* pcur = phead->next;
while(pcur != phead)
{
if(pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
在pos位置之后插入数据 LTInsert
需要将新节点newnode插入在pos和pos->next之间，即先将newnode的prev指针指向pos，newnode的next指针指向pos->next，然后将newnode节点变成新的pos->next节点
注意有一种情况：当pos的位置是尾节点时，就是要在phead->prev和phead之间插入数据，即尾插
但是我们在对该函数传参时，并不需要用到phead（在pos位置之后插入节点只需知道pos和pos->next，以及要插入的数据即可）,因此，不能直接调用尾插函数。不过我们并不需要调用尾插函数也可以做到，因为将newnode插入pos和pos->next之间的做法也适用于尾插的情况
这里不再画图讲解
void LTInsert(LTNode* pos,LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next = newnode;
}
在pos位置之前插入数据 LTInsertBefort
需要将newnode节点插入在pos->prev与pos之间，先将newnode的prev指针指向pos->prev，再将newnode的next指针指向pos，表示插入新节点成功，当然，这也有一种情况：当pos的围位置是第一个有效节点时，就是头插的方法，不过我们也不需要调用函数使用，因为以上的操作已经覆盖了头插做法
void LTInsertBefort(LTNode* pos,LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->prev = pos->prev;
newnode->next = pos;
pos->prev->next = newnode;
pos->prev = newnode;
}
删除pos节点
删除pos节点，直接修改pos->next的prev指针为pos->prev，pos->prev的next指针为pos->next，然后将pos节点释放掉即可
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
销毁链表 LTDestroy
在遍历销毁链表之前，应该保存一下下一个节点的指针，避免后续找不到位置
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while(pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//此时pcur指向phead，而phead还没有被销毁
free(phead);
phead = NULL;
}注意
LTErase 和 LTDestroy 函数参数理论上要传二级指针，因为我们需要让形参的改变影响到实参，但为了保持接口一致性传一级指针，传一级指针存在的问题：当形参phead置为NULL后，实参plist不会被修改为NULL，因此解决办法：调用完方法后手动将实参置为NULL
//测试删除pos节点
LTErase(find);
find = NULL;
LTPrint(plist);
//销毁链表
LTDestroy(plist);
plist = NULL;三、完整代码
List.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//声明双向链表中提供的方法
//初始化
//void InitList(LTNode** pphead);
LTNode* InitList();
//打印链表
void LTPrint(LTNode* phead);
//在插入数据之前，链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址，因此传一级指针即可
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//在pos位置之前插入数据
void LTInsertFront(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//申请节点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc");
exit(1);
}
node->data = x;
node->next = node->prev = node;
return node;
}
//初始化
//void InitList(LTNode** pphead)
//{
// //给双链表申请一个哨兵位
// *pphead = LTBuyNode(-1);
//}
LTNode* InitList()
{
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
//1.先在尾部插入新节点
newnode->prev = phead->prev;
newnode->next = phead;
//2.更新新的尾节点与头节点进行首尾相连
phead->prev->next = newnode;
phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x) //头插，要往头节点后面插入
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead newnode phead->next
//1.先在头节点和第一个有效节点之间插入一个新节点，表示头插
newnode->next = phead->next;
newnode->prev = phead;
//2.更新新的节点为新的第一个有效节点
phead->next->prev = newnode;
phead->next = newnode;
//也可以这样写
/*phead->next = newnode;
newnode->next->prev = newnode;*/
}
//尾删
void LTPopBack(LTNode* phead)
{
//链表必须有效且链表不能为空（只有一个哨兵位）
assert(phead && phead->next != phead);
LTNode* del = phead->prev;
//phead del->prev del
del->prev->next = phead;
phead->prev = del->prev;
//删除del节点
free(del);
del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != phead);
LTNode* del = phead->next;
//phead del del->next
phead->next = del->next;
del->next->prev = phead;
//删除del节点
free(del);
del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
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)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next = newnode;
}
//在pos位置之前插入数据
void LTInsertFront(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos->prev newnode pos
newnode->prev = pos->prev;
newnode->next = pos;
pos->prev->next = newnode;
pos->prev = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{
//pos理论上来说不能为phead，但是没有参数phead，无法增加校验
assert(pos);
//pos->prev pos pos->next
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
//销毁链表
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//此时pcur指向phead，而phead还没有被销毁
free(phead);
phead = NULL;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest01()
{
//初始化
/*LTNode* plist = NULL;
InitList(&plist);*/
LTNode* plist = InitList();
//测试尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
//测试头插
/*LTPushFront(plist, 1);
LTPrint(plist);
LTPushFront(plist, 2);
LTPrint(plist);
LTPushFront(plist, 3);
LTPrint(plist);*/
//测试尾删
/*LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);*/
//测试头删
/*LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);*/
//测试查找链表
LTNode* find = LTFind(plist, 2);
/*if (find == NULL)
{
printf("找不到\n");
}
else
{
printf("找到了\n");
}*/
//测试在pos位置之后插入数据
/*LTInsert(find, 66);
LTPrint(plist);*/
//测试在pos位置之前插入数据
/*LTInsertFront(find, 88);
LTPrint(plist);*/
//测试删除pos节点
LTErase(find);
find = NULL; //LTErase 和 LTDestroy 函数参数理论上要传二级指针，因为我们需要让形参的改变影响到实参，但为了保持接口一致性传
LTPrint(plist); //一级指针，传一级指针存在的问题：当形参phead置为NULL后，实参plist不会被修改为NULL，因此解决办法：调用完方法后
//手动将实参置为NULL
//销毁链表
LTDestroy(plist);
plist = NULL;
}
int main()
{
ListTest01();
return 0;
}