1. 双向链表的结构
哨兵位不存储有效数据。
当链表中只有哨兵位节点的时候，我们称该链表为空链表，即哨兵位是不能删除的。
注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”
“哨兵位”存在的意义：
遍历循环链表避免死循环。
2. 双向链表的实现
哨兵位：非有效结点。
首结点：第一个有效结点。
尾结点：最后一个有效结点。
2.1 头文件
typedef int LTDataType;
//链表中结点的结构
typedef struct ListNode
{
struct ListNode* next; //指针保存下⼀个节点的地址——后继结点指针
struct ListNode* prev; //指针保存前⼀个节点的地址——前驱结点指针
LTDataType data;
}LTNode;
//注意：双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位(单向链表可以直接插入数据)
//注意：当链表中删到只有哨兵位时，称为空链表（不可再删）
//注意：哨兵位是不能删除也不能修改的，即不能对哨兵位进行任何操作，但是可以改变哨兵位的指向（头插：指插入到哨兵位之后，头节点之前，成为新的头节点）
//传入参数-改变参数式的初始化方式
//void LTInit(LTNode** pphead);
//接受返回值式的初始化
LTNode* LTInit();
void LTDesTroy(LTNode** pphead);
void LTdesTroy(LTNode* phead); //推荐一级（优：保持接口一致性；缺：调用完后phead需手动置空）
void LTPrint(LTNode* phead);
//不需要改变哨兵位（的位置），则不需要传二级指针
//需要改变哨兵位（的内容val、next），则不需要传二级指针
//如果需要修改哨兵位（的位置）的话（phead->next），则传二级指针××××××××
//注意：改变phead->next只需要*phead，改变哨兵位需要*pphead
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);
//指定插入（之后）
void LTInsert(LTNode* pos, LTDataType x);
//指定删除
void LTErase(LTNode* pos);2.2 实现代码、测试代码
（1）初始化
函数声明
//List.h
//传入参数-改变参数式的初始化方式
//void LTInit(LTNode** pphead);
//接受返回值式的初始化
LTNode* LTInit();函数实现
//List.c
//双链表
#include "Double_Linked_List.h"
LTNode* LTBuyNode(LTDataType x) {
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
//让新节点自循环
newnode->next = newnode->prev = newnode;
return newnode;
}
//void LTInit(LTNode** pphead) {
// *pphead = (LTNode*)malloc(sizeof(LTNode));
// if (*pphead == NULL) {
// perror("malloc fail!");
// exit(1);
// }
// (*pphead)->data = -1; //给哨兵位一个无效的数据
// //带头双向循环链表：初始化哨兵位时，其前驱指针和后继指针都是它自己
// (*pphead)->next = (*pphead)->prev = *pphead;
//}
LTNode* LTInit() {
LTNode* phead = LTBuyNode(-1);
return phead;
}函数测试
（2）打印
函数声明
void LTPrint(LTNode* phead);函数实现
void LTPrint(LTNode* phead) {
//phead不能为空
assert(phead);
//先走到首结点
LTNode* pcur = phead->next; //phead->next 不会为空，至少也是自己（哨兵位）
//循环条件：没到下一个哨兵位
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}（3）头插、尾插
函数声明
//头插、尾插
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);双链表同样是通过一个结点指针来维护，这个结点指针永远指向头结点——哨兵位，永远不会改变其指向，则不需要传二级指针。
逻辑演示
头插是在第一个有效结点之前插入，而不是在哨兵位之前插入——这是尾插。
函数实现
//List.c
//双链表
//尾插——在最后一个有效节点之后、哨兵位之前插入节点
void LTPushBack(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead phead->prev(ptail) newnode
//生成两条链——修改新结点的指向
newnode->next = phead;
newnode->prev = phead->prev;
//重连两条链——修改尾结点、哨兵位的指向
phead->prev->next = newnode;
phead->prev = newnode;
}
//头插——在第一个有效节点之前、哨兵位之后插入节点
void LTPushFront(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead newnode phead->next
//生成两条链——修改新结点的指向
newnode->next = phead->next;
newnode->prev = phead;
//重连两条链——修改首结点、哨兵位的指向
phead->next->prev = newnode;
phead->next = newnode;
}函数测试
（4）头删、尾删
函数声明
//头删、尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);双链表同样是通过一个结点指针来维护，这个结点指针永远指向头结点——哨兵位，永远不会改变其指向，则不需要传二级指针。
逻辑演示
函数实现
//List.c
//双链表
//尾删
void LTPopBack(LTNode* phead) {
assert(phead);
//链表为空：只有一个哨兵位节点
assert(phead->next != phead);//或者phead->prev != phead
//找到待删节点
LTNode* tail = phead->prev;
//找到待删节点的前驱节点
LTNode* tailprev = tail->prev;
//互指
tailprev->next = phead;
phead->prev = tailprev;
free(tail);
tail = NULL;
}
//头删
void LTPopFront(LTNode* phead) {
assert(phead);
assert(phead->next != phead);
//找到待删节点
LTNode* del = phead->next;
//找到待删节点的后继节点
LTNode* next = del->next;
//phead del next
next->prev = phead;
phead->next = next;
free(del);
del = NULL;
}函数测试
（5）查找pos位置
函数声明
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);函数实现
思路：遍历查找。
//List.c
//双链表
//查找pos位置
LTNode* LTFind(LTNode* phead, LTDataType x) {
assert(phead);
//遍历之前，先走到首结点
LTNode* pcur = phead->next;
//遍历结束条件：来的第2个哨兵位
while (pcur != phead)
{
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}函数测试
（6）在pos位置之后插入
函数声明
//指定插入（之后）
void LTInsert(LTNode* pos, LTDataType x);双链表同样是通过一个结点指针来维护，这个结点指针永远指向头结点——哨兵位，永远不会改变其指向，则不需要传二级指针。
逻辑演示
函数实现
//List.c
//双链表
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
//生成两条链
newnode->next = pos->next;
newnode->prev = pos;
//重连两条链——注意先后顺序
pos->next->prev = newnode; //先
pos->next = newnode; //后
}函数测试
（7）删除pos位置的数据
函数声明
//指定删除
void LTErase(LTNode* pos);双链表同样是通过一个结点指针来维护，这个结点指针永远指向头结点——哨兵位，永远不会改变其指向，则不需要传二级指针。
逻辑演示
函数实现
//List.c
//双链表
//删除pos位置的数据
void LTErase(LTNode* pos) {
assert(pos);
//pos->prev pos pos->next
//重连两条链——指出去的两条链不用管，只需修改指进来的两条链
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}函数测试
（8）销毁
函数声明
//销毁
void LTDesTroy(LTNode** pphead);
void LTdesTroy(LTNode* phead);
//推荐一级——
//优：保持接口一致性；
//缺：调用完后phead需手动置空函数实现
//List.c
//双链表
//销毁
//void LTDesTroy(LTNode** pphead) {
// assert(pphead);
// //哨兵位不能为空
// assert(*pphead);
//
// //循环遍历，保存下一个，删除这一个
// LTNode* pcur = (*pphead)->next;
// while (pcur != *pphead)
// {
// LTNode* next = pcur->next;
// free(pcur);
// pcur = next;
// }
// //链表中只有一个哨兵位
// free(*pphead);
// *pphead = NULL;
//}
void LTdesTroy(LTNode* phead) {
//哨兵位不能为空
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//此时链表中，只剩一个哨兵位
free(phead);
phead = NULL;
}函数测试
3. 顺序表和链表的优缺点分析
完