目录
一. 双向链表的结构
在List.h的头文件中对链表的结构进行创建
#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;
//双向链表的结构
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;为了方便使用，将结构体类型重命名为LTNode
将存储数据的类型通过typedef来使用，方便进行修改
如果双向链表为空，则只有头节点一个节点。
如果phead=NULL，则只能说明这不是一个有效的双向链表。
二.双向链表的使用
2.1 创建节点
（下列的声明就不再显示，直接写函数的实现）
//创建节点
LTNode* LTNBuyNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->data = x;
node->next = node->prev = node;
return node;
}由于带头双向循环链表的特性，prev和next都指向node本身，也就是自身循环
2.2 初始化
//初始化
void LTInit(LTNode** phead)
{
* phead =LTNBuyNode(-1);
}
初始化就是创建哨兵位，哨兵位的数据和地址都不会被修改
哨兵位也就是头节点，原先单链表中说的头节点其实是指第一个有效节点。
第二种方式：
LTNode* LTInit()
{
LTNode*phead = LTNBuyNode(-1);
return phead;
}无需创建变量，而是直接返回phead
2.3 打印
//打印
void LTPrint(LTNode* phead)//int 类型
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
2.4 尾插
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTNBuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}尾插主要是要直到双向链表尾插的结构和指针指向就很简单了
如果你要在哨兵位前面头插，那相当于尾插（因为双向链表是带头双向循环链表）
2.5 头插
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTNBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}2.6 尾删
//尾删
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;
}注意，需要del来承载phead->next
链表有效且不为空
2.7 头删
//头删
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;
free(del);
del = NULL;
}2.8 在指定位置pos之后插入数据
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTNBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}2.9 查找数据
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}注意返回的是数据的节点地址
所以之后要检验find是否为空来判断是否有
2.10 删除pos位置的节点
//删除pos节点
//为什么不传二级指针
//为了保证接口的一致性
void LTErase(LTNode* pos)
{
//理论上pos不能为phead，但是没有参数phead，无法增加校验
assert(pos);
//pos,pos->next,pos->prev
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}这里不使用二级指针传参是因为为了保证接口的统一性，因为之前的形参都是一级指针
所以此函数使用后需要将find指针变为NULL
2.11 销毁链表
//销毁链表
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;
}使用后还得将plist（实参）赋值为空指针
原来还是应该传二级指针，但是为了接口统一性，跟前者一样