定义链表分类单向和双向
在这里插入图片描述
带头和不带头
在这里插入图片描述
带头是指存在一个头结点（哨兵位），但是不存储任何有效数据，用来占位子
注意：单链表是不带头的，方便理解，有时候称为第一个结点为头结点，实际上是没有头结点的
循环和不循环
在这里插入图片描述双向链表：带头双向循环链表在这里插入图片描述
组成：保存的数据 + 指向下一个结点的指针 + 指向上一个节点的指针
单链表为空时，指向第一个节点的指针为空，双链表为空时，链表中只有一个头结点！
在这里插入图片描述初始化法一：定义一个双向链表的结构体，然后将指向双向链表的指针plist作为形参开始初始化然后返回
法二：通过函数的返回值来返回
代码语言：javascript复制函数的声明代码语言：javascript复制//结构的定义
typedef int LTDataType;
typedef struct ListNode {
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//初始化(法一)
void LTInit(LTNode** pphead);
//法二:
//LTNode* LTInit();代码语言：javascript复制函数的实现代码语言：javascript复制#include"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)
{
assert(pphead);
*pphead = LTBuyNode(-1);
}
/*法二
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;//返回双向链表的头结点
}*/代码语言：javascript复制函数的测试代码语言：javascript复制#include"List.h"
void test01()
{ //法一：
LTNode* plist = NULL;//单链表为空时，指向第一个节点的指针为空
//双链表为空时，链表中只有一个头结点！
LTInit(&plist);
/*法二：
LTNode* plist = LTInit();
*/
}
int main()
{
test01();
return 0;
}法一：相当于你提着一个空的油桶（一个形参）去买油，然后给你装满油；
法二：相当于你空手去买油，然后连油带桶给你（推荐这种）。
打印单链表的打印是从第一个结点开始往后遍历，且第一个结点不能为空while(pcur)，但是双链表的第一个结点（哨兵位）就不储存数据，所以当还是用相同的办法会陷入死循环，如何解决？
将哨兵位的下一个结点定为pcur，向后遍历，停止的标志为pcur = phead
代码语言：javascript复制//打印
void LTPrint(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead) //将哨兵位的下一个结点定为pcur，向后遍历，停止的标志为pcur = phead
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("\n");
}尾插双向链表中尾插，头结点不会发生改变（哨兵位），所以传一级指针。
phead指向链表的第一个结点，通过phead->prev找到尾结点，然后申请一个新结点（newnode）,当尾插进来，受到影响的指针有“尾结点的next指针不再指向头结点，而是指向newnode；头结点的prev指针不再指向尾结点，而是指向newnode”，最后newnode的next指针指向头结点。
但是修改的顺序是？先修改对原链表没有影响的结点，因为先修改头结点的prev指针指向newnode后你就找不到原来的尾结点了；通常一般先改变newnodeprev和next指针，最后改头结点受到影响的。
代码语言：javascript复制//尾插
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;
}头插newnode放在哨兵位的后面，如果放在哨兵位的前面则相当于尾插。
phead指向链表的第一个结点，通过phead->next找到哨兵位下一个结点，然后申请一个新结点（newnode）,当头插进来，受到影响的指针有“头结点的next指针不再指向哨兵位下一个结点，而是指向newnode；哨兵位下一个结点的prev指针不再指向头结点，而是指向newnode”，最后newnode的next指针指向头结点。
但是修改的顺序是？先修改对原链表没有影响的结点，因为先修改头结点的next指针指向newnode后你就找不到原来哨兵位下一个结点了；通常一般先改变newnodeprev和next指针，最后改头结点受到影响的。
代码语言：javascript复制//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}尾删删除phead->prev指针，思考能不能直接释放掉？
如果直接释放掉，phead->prev和phead->prev->prev->next均会变成野指针，所以要先将phead->prev->prev->next指向头结点，然后将头结点的prev指针指向phead->prev->prev->next。删除之前要将此结点存起来del = phead->prev，执行完上述操作后释放掉，并且置位空。
代码语言：javascript复制//判断链表是否为空:只有一个头结点，记得在头文件声明
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
} // 返回true为空，反回flase不为空
//尾删
void LTPopBack(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}头删删除phead->next指针，先将del->next->prev指向头结点，然后将头结点的next指针指向del->next。删除之前要将此结点存起来del = phead->next，执行完上述操作后释放掉，并且置位空。
代码语言：javascript复制//判断链表是否为空:只有一个头结点
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
} // 返回true为空，反回flase不为空
//头删
void LTPopFront(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = NULL;
}代码语言：javascript复制以上时间复杂度全是O(1),不需要遍历查找定义一个pcur为phead的next结点，然后进行遍历查找，找到了就返回查找的值，没有找到就返回空，循环的条件是pcur不走到头结点。
代码语言：javascript复制//查找，记得添加到头文件
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(指定位置)之后插入结点先修改对原链表没有影响的结点
受到影响的结点：pos，pos->next这两个结点
还是先改newnode指针的指向，然后改pos->next指向的结点，最后改pos结点
代码语言：javascript复制//在pos位置后插入结点
void LTInsertBack(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}在pos(指定位置)之前插入结点先修改对原链表没有影响的结点
受到影响的结点：pos，pos->prev这两个结点
还是先改newnode指针的指向，然后改pos->prev指向的结点，最后改pos结点
代码语言：javascript复制//在pos位置前插入结点
void LTInsertFront(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos;
newnode->prev = pos->prev;
pos->prev->next = newnode;
pos->prev = newnode;
}删除pos(指定位置)的结点代码语言：javascript复制//删除pos位置的结点
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}销毁定义一个pcur指向头结点的下一个结点的地址，当pcur不等于头结点（哨兵位）时，进入循环，将pcur的下一个结点先保存下来，然后销毁pcur，然后让pcur走到刚刚保存的下一个结点，就这样进行遍历，最后销毁完全部后在手动销毁头结点并且置位空。
代码语言：javascript复制//链表的销毁，因为形参会影响实参，所以传二级指针
void LTDestroy(LTNode** pphead)
{
LTNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(*pphead);
*pphead = NULL;
}代码语言：javascript复制void test01()
{
LTDestroy(&plist);
}但是这个定义的函数违背了接口一致性？因为其他的所有函数都是传的一级指针，此处传的二级，如何解决?
代码语言：javascript复制void LTDestroy(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}因为这样不能改变形参的值，需要手动置空
代码语言：javascript复制void test01()
{
LTDestroy(plist);
plist = NULL;
}顺序表与链表的分析对比维度
顺序表
单链表
双向链表
存储结构
物理连续（数组）
节点 + 单向指针
节点 + 前驱/后继双指针
随机访问效率
O(1)
O(n)
O(n)
头插/头删效率
O(n)（需移动元素）
O(1)
O(1)
尾插/尾删效率
O(1)（若预留空间）
O(n)（需遍历）
O(1)（直接访问尾节点）
任意位置插入删除
O(n)
O(n)（需找前驱节点）
O(1)（已知位置时）
空间开销
仅数据
数据 + 1个指针/节点
数据 + 2个指针/节点
内存灵活性
需预分配，可能浪费
动态分配，无浪费
动态分配，无浪费
逆向遍历
支持（但效率同正向）
不支持
支持（O(n)）
适用场景
高频访问、数据量稳定
频繁头操作、未知数据量
需要双向操作（如LRU缓存）