数据结构：双向链表
代码汇总见：登录 - Gitee.com
与本文章对照理解更好：
数据结构：顺序表-CSDN博客
相关文章：
数据结构：单链表的应用（力扣算法题）第一章-CSDN博客
数据结构：单链表的应用（力扣算法题）第二章-CSDN博客
数据结构：单链表的应用（力扣算法题）第三章-CSDN博客
1.链表的分类
链表的结构非常多样，组合如以下8种：
链表说明：
1.带头或不带头链表
带头链表的头结点中，不存在任何有效的数据，只是用来占位，又名：哨兵位。
2.单向或双向链表
单向链表只能从第一个结点向后走，而双向结点每个有两个指针。
3.循环或不循环链表
在8种链表结构中，我们实际最常用的还是两种结构：单链表（不带头单向不循环链表）和双向链表（带头双向循环链表）。
2.双向链表
2.1概念与结构
注意：这里的“带头”与之前的“头结点”是两个概念，带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只用于”放哨“。
当双向链表为空时，均指向自己：
双向链表中的结点有三个组成部分：
struct ListNode
{int data;struct ListNode* next;//指向后一个结点struct ListNode* prev;//指向前一个结点
};2.2实现双向链表
依旧创建三个文件：test.c List.c List.h
需要实现的内容均包含在头文件中：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义双向链表
typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;////初始化
//void LTInit(LTNode** pphead);
//初始化02
LTNode* LTInit();////销毁链表
//void LTDesTroy(LTNode** pphead);
//销毁链表02
void LTDesTroy(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插
void LTPushFront(LTNode* phead, LTDataType x);//判空
bool LTEmpty(LTNode* phead);//打印
void LTPrint(LTNode* phead);//尾删
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);//删除
void LTErase(LTNode* pos);
2.2.1初始化
代码见下：
//初始化
void LTInit(LTNode** pphead)
{*pphead = (LTNode*)malloc(sizeof(LTNode));if (*pphead == NULL){perror("malloc fail!");exit(1);}(*pphead)->data = 0;//哨兵结点(*pphead)->next = (*pphead)->prev = *pphead;//指向自己
}调试代码：
2.2.2尾插
在双向链表中，增删改查都不会改变哨兵位结点，所以使用一级指针。
尾插时先建立一个新节点newnode，先改变它的指向，prev指针指向d3，next指针指向哨兵位，再将头结点的前一结点指向newnode，并改变d3指向至newnode。
若原本就是空指针，其操作与非空操作也一模一样。
代码：
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}调用调试：
2.2.3头插
具体思路与尾插大同小异。
代码见下：
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}调用调试：
2.2.4判空
在循环双向链表中，有必要单独封装判空函数。
//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;//此时链表为空
}2.2.5打印
终止条件需要注意，不然会一直循环下去。
//打印
void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){printf("%d -> ", cur->data);cur = cur->next;}printf("\n");
}2.2.6尾删
需要将尾删的结点进行保存，不然会找不到其他结点。
代码如下：
//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}调用调试代码：
2.2.7头删
具体思路与尾删相似。
代码见下：
//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}调用调试：
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);2.2.8查找
代码见下：
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}调用测试：
LTNode* pos = LTFind(plist, 6);
if (pos)
{printf("找到了\n");
}
else {printf("未找到\n");
}2.2.9在pos之后插入结点
代码见下：
//在pos之后插入结点
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;
}调用测试：
LTNode* pos = LTFind(plist, 2);
LTInsert(pos, 100);
LTPrint(plist);2.2.10在pos之前插入结点
代码见下：
//在pos之前插入结点
void LTInsertFront(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos->prev newnode posnewnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;
}调用测试：
LTNode* pos = LTFind(plist, 2);
LTInsert(pos, 100);
LTPrint(plist);
LTInsertFront(pos, 200);
LTPrint(plist);2.2.11删除pos位置结点
代码见下：
//删除pos位置结点
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}调用调试：
LTNode* pos = LTFind(plist, 2);
LTErase(pos);
LTPrint(plist);2.2.12销毁链表
先从第一个结点开始删除，而不是头结点。
代码如下：
//销毁链表
void LTDesTroy(LTNode** pphead)
{LTNode* cur = (*pphead)->next;while (cur != *pphead){LTNode* next = cur->next;free(cur);cur = next;}//销毁头结点free(*pphead);*pphead = NULL;
}2.3优化链表
由于有二级指针和一级指针混合，所以为了接口的一致，可以做以下修改：
初始化：
- 通过函数返回值直接返回新创建的头节点地址。
- 调用时通过赋值接收返回值
//初始化02
LTNode* LTInit()
{LTNode* phead = LTBuyNode(0);return phead;
}调用调试：
LTNode* plist = LTInit();销毁链表：
- 能销毁所有节点（包括头节点），但最后
phead = NULL;只修改了函数内部的形参，外部的头指针变量不会被置为NULL。 - 这会导致外部头指针变成 “野指针”（指向已被
free的内存），后续若误操作该指针，会引发未定义行为（如非法访问内存）。
//销毁链表02
void LTDesTroy(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}//销毁头结点free(phead);phead = NULL;
}调用调试：
LTDesTroy(plist);
plist = NULL;通过比较，初始化推荐用 “返回一级指针” 的方式，销毁用 “二级指针” 的方式，才能保证代码的安全性和健壮性。
3.顺序表与链表的分析
本章完。