双向链表的学习
经过单链表、双链表的学习，可以总结链表的适用场合：
-
适合用于节点数目不固定，动态变化较大的场合
-
适合用于节点需要频繁插入、删除的场合
-
适合用于对节点查找效率不十分敏感的场合
双向链表的增删改查实现
双向链表的初始化
//指的是双向链表中的节点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造链表的结点，链表中所有结点的数据类型应该是相同的
typedef struct CircularLinkedList
{
DataType_t Data; //结点的数据域
struct CircularLinkedList *Pre; //结点的直接前驱指针域
struct CircularLinkedList *Next; //结点的直接后继指针域
}DouList_t;
//创建一个空双向链表，空链表应该有一个头结点,对链表进行初始化
DouList_t *CreateEmptyDouLinkedList(void)
{
//1.创建一个头结点并为头结点申请内存
DouList_t *Head = (DouList_t *)calloc(1,sizeof(DouList_t ));
if(Head == NULL)
{
perror("Calloc memory for Head is Failed");
return NULL;
}
//2.对头结点进行初始化，头节点是不存储有效内容的
Head->Pre = NULL;
Head->Next = NULL;
//3.把头结点的地址返回即可
return Head;
}
//创建新的结点，并对新结点进行初始化(数据域+指针域)
DouList_t *CreateDouNewLinkedList(DataType_t Data)
{
//1.申请一个结点的内存空间
DouList_t *NewNode = (DouList_t *)calloc(1,sizeof(DouList_t ));
if(NewNode == NULL)
{
perror("Calloc memory for Head is Failed");
return NULL;
}
//2.对新结点的数据域和指针域进行初始化
NewNode->Data = Data;
NewNode->Pre = NULL;
NewNode->Next = NULL;
//3.返回新结点的地址
return NewNode;
}
插入结点
头插
/*****************************************************
* @function_name : InsertDouList
* @brief_ : 将新结点插入链表中的头结点之后
* @param_ :
* DouList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/23
* @version_ : v1.0
* @note_ : None
*******************************************************/
//头插
bool InsertDouList(DouList_t *Head, DataType_t Data)
{
//1.创建一个新结点
DouList_t * new = CreateDouNewLinkedList(Data);
//2.如果链表为空
if(Head->Next == NULL)
{
Head->Next = new;
return true;
}
//3.如果链表不为空
new->Next = Head->Next; //新结点先链接后面的结点
Head->Next->Pre = new; //新结点链接后面的结点的前驱目标结点
Head->Next = new; //让头结点链接新结点
return true;
}
尾插
/*****************************************************
* @function_name : InsertTailDouList
* @brief_ : 将新结点插入链表中的尾结点之后
* @param_ :
* DouList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/23
* @version_ : v1.0
* @note_ : None
*******************************************************/
//尾插
bool InsertTailDouList(DouList_t *Head, DataType_t Data)
{
DouList_t *new = CreateDouNewLinkedList(Data);
//如果链表为空
if(Head->Next == NULL)
{
Head->Next = new;
return true;
}
//如果链表不为空
DouList_t *Ptail = Head;
//遍历链表，找到尾结点
while(Ptail->Next)
{
Ptail = Ptail->Next;
}
Ptail->Next = new; //尾结点先链接后面的结点
new->Pre = Ptail; //新结点链接后面的结点的前驱目标结点
return true;
}
指定插
/*****************************************************
* @function_name : InsertPosDouList
* @brief_ : 指定目标数据域，将新结点插入目标结点之后(第一个目标结点)
* @param_ :
* DouList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* DataType_t Dest --> 目标结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/23
* @version_ : v1.0
* @note_ : None
*******************************************************/
//指定目标位置插入
bool InsertPosDouList(DouList_t *Head, DataType_t Data,DataType_t Dest)
{
//如果链表为空
if(Head->Next == NULL)
{
return false;
}
//如果链表不为空
DouList_t *Phead = Head->Next;
//1.遍历, 先找到目标结点
while(Phead->Next && Dest != Phead->Data)//查找data值为dest的结点
{
Phead = Phead->Next;//把头的直接后继作为新的头结点
}
if (NULL == Phead->Next && Dest != Phead->Data) //不存在元素为dest的结点, 返回false
return false;
//2.若目标结点存在, 创建新的结点，并对新结点进行初始化
DouList_t *New = CreateDouNewLinkedList(Data);
//3.把新结点插入到目标结点的后面
//如果是尾结点
if(Phead->Next == NULL)
{
Phead->Next = New;
New->Pre = Phead;
}
//如果不是尾结点
else
{
New->Next = Phead->Next;//新结点先链接后面的结点
Phead->Next->Pre = New;//新结点链接后面的结点的前驱目标结点
Phead->Next = New;//让目标元素结点链接新结点
New->Pre = Phead;//新结点链接目标结点的前驱
}
return true;
}
删除结点
头删
/*****************************************************
* @function_name : DeleteDouList
* @brief_ : 删除链表中的首元结点
* @param_ :
* DouList_t *Head--> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/23
* @version_ : v1.0
* @note_ : None
*******************************************************/
//头部删除
bool DeleteDouList(DouList_t *Head)
{
//1.如果链表为空
if(Head->Next == NULL)
{
printf(" Linked List is Empty\n");
return false;
}
//2.如果链表不为空
DouList_t *Phead = Head;
if(Phead->Next->Next == NULL) //只有一个结点
{
Head->Next = NULL;
free(Phead->Next);
}
else
{
Head->Next = Phead->Next; //更新头结点的Next
Phead->Next->Pre = NULL; //更新新首结点的前驱
Phead->Next = NULL; //更新旧首结点的后继
free(Phead);
}
}
尾删
/*****************************************************
* @function_name : DeleteTailDouList
* @brief_ : 删除链表中的尾结点
* @param_ :
* DouList_t *Head--> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/23
* @version_ : v1.0
* @note_ : None
*******************************************************/
//尾部删除
bool DeleteTailDouList(DouList_t *Head)
{
//1.如果链表为空
if(Head->Next == NULL)
{
printf(" Linked List is Empty\n");
return false;
}
//2.如果链表不为空
DouList_t *Ptail = Head;
//遍历链表，找到尾结点
while(Ptail->Next)
{
Ptail = Ptail->Next;
}
//3.若尾结点存在, 删除尾结点
if(Head->Next->Next == NULL) //只有一个结点
{
Head->Next = NULL;
free(Ptail->Next);
}
else
{
Ptail->Pre->Next = NULL; //更新旧尾结点的前驱的后继
Ptail->Pre = NULL; //更新旧尾结点的前驱
free(Ptail);
}
return true;
}
指定删
/*****************************************************
* @function_name : DoublelList_DestDel
* @brief_ : 指定目标数据域，将该结点删除
* @param_ :
* DouList_t *Head --> 链表头结点的地址
* DataType_t Dest --> 要删除结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/23
* @version_ : v1.1
* @note_ : None
*******************************************************/
bool DoublelList_DestDel(DouList_t *Head, DataType_t dest)
{
DouList_t *Phead = Head; // 备份头结点地址,防止头结点丢失
// 1.判断双向链表是否为空, 如果为空, 则直接插入到头结点之后
if (NULL == Head->Next)
{
printf("linked list is empty\n");
return false;
}
// 2.如果双向链表为非空,此时遍历链表查找没有目标结点(找到or未找到)
while (Phead->Next)
{
Phead = Phead->Next;
if (Phead->Data = dest)
{
break;
}
}
// 如果链表中没有目标结点,此时直接退出即可
if (Phead->Next == NULL && Phead->Data != dest)
{
printf("dest node is not found\n");
return false;
}
// 如果链表中发现目标结点,此时分为(头部 or尾部 or中间)
if (Phead == Head->Next) // 头部
{
Head->Next = Phead->Next; // 更新头结点,让头结点的Nest指针指向首结点的直接后继
if (Phead->Next != NULL) // 判断是否是最后一个结点
{
Phead->Next->Pre = NULL; // 更新首结点的直接后继结点的前驱指针
Phead->Next = NULL; // 更新首结点的直接后继指针
}
free(Phead); // 释放待删除结点内存
}
else if (Phead->Next == NULL) // 尾部
{
Phead->Pre->Next = NULL; // 尾结点的直接前驱结点的Nest指针指向NULL
Phead->Pre = NULL; // 尾结点的Pre指针指向NULL
free(Phead); // 释放待删除结点内存
}
else
{
Phead->Pre->Next = Phead->Next; // 让待删除结点的直接前驱结点的Nest指针指向待删除结点的直接后继地址
Phead->Next->Pre = Phead->Pre; // 让待删除结点的直接后继结点的Pre指针指向待删除结点的直接前驱地址
Phead->Next = NULL; // 让待删除结点的Nest指针指向NULL
Phead->Pre = NULL; // 让待删除结点的Pre指针指向NULL
free(Phead); // 释放待删除结点内存
}
return true;
}
遍历链表
/*****************************************************
* @function_name : DouLList_Print
* @brief_ : 遍历输出链表各个结点的数据域
* @param_ :
* DouList_t *Head --> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/23
* @version_ : v1.0
* @note_ : None
*******************************************************/
//遍历链表
bool DouLList_Print(DouList_t *Head)
{
//1.如果链表为空
if(Head->Next == NULL)
{
printf(" Linked List is Empty\n");
return false;
}
//2.如果链表不为空
DouList_t *Phead = Head->Next;
while(Phead)
{
printf("%d\n",Phead->Data);
Phead = Phead->Next;
}
return true;
}
摧毁链表
/*****************************************************
* @function_name : DestroyDouList
* @brief_ : 摧毁链表，释放空间
* @param_ :
* DouList_t *Head --> 链表头结点的地址
* @retval_ : 空
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//摧毁链表
void DestroyDouList(DouList_t *Head)
{
while (Head->Next!= NULL)
{
DeleteDouList(Head);
}
Head->Next = NULL;
free(Head);
}
双向循环链表的增删改查实现
双向循环链表的初始化
//指的是双向循环链表中的节点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造链表的结点，链表中所有结点的数据类型应该是相同的
typedef struct DoubleCircularLinkedList
{
DataType_t Data; //结点的数据域
struct DoubleCircularLinkedList *Prev; //结点的指针域
struct DoubleCircularLinkedList *Next; //结点的指针域
}DouCirList_t;
//创建一个空双向循环链表，空链表应该有一个头结点,对链表进行初始化
DouCirList_t *CreateEmptyCLinkedList(void)
{
//1.创建一个头结点并为头结点申请内存
DouCirList_t *Head = (DouCirList_t *)calloc(1,sizeof(DouCirList_t));
if(Head == NULL)
{
perror("Calloc memory for Head is Failed");
return NULL;
}
//2.对头结点进行初始化，头节点是不存储有效内容的
Head->Next = Head;
Head->Prev = Head;
//3.把头结点的地址返回即可
return Head;
}
//创建新的结点，并对新结点进行初始化(数据域+指针域)
DouCirList_t *CreateNewDCLinkedList(DataType_t Data)
{
//1.申请一个结点的内存空间
DouCirList_t *NewNode = (DouCirList_t *)calloc(1,sizeof(DouCirList_t));
if(NewNode == NULL)
{
perror("Calloc memory for Head is Failed");
return NULL;
}
//2.对新结点的数据域和指针域进行初始化
NewNode->Data = Data;
NewNode->Prev = NULL;
NewNode->Next = NULL;
//3.返回新结点的地址
return NewNode;
}
插入结点
头插
/*****************************************************
* @function_name : InsertDCList
* @brief_ : 将新结点插入链表中的头结点之后
* @param_ :
* DouCirList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/24
* @version_ : v1.0
* @note_ : None
*******************************************************/
//头插
bool InsertDCList(DouCirList_t *Head, DataType_t Data)
{
//1.创建一个新结点
DouCirList_t *NewNode = CreateNewDCLinkedList(Data);
if(NewNode == NULL)
{
return false;
}
//2.断链表是否为空
if(Head->Next == Head)
{
//链表为空
Head->Next = NewNode;
NewNode->Next = NewNode;
NewNode->Prev = NewNode;
}
else
{
DouCirList_t *Phead = Head->Next;
//链表不为空
NewNode->Prev = Phead->Prev; //新结点Prev指向尾结点
NewNode->Next = Phead; //新结点Next指向旧首结点
Head->Next = NewNode; //头结点Next指向新结点
Phead->Prev->Next = NewNode; //尾结点Prev指向新结点
Phead->Prev = NewNode; //旧首结点Prev指向新结点
}
return true;
}
尾插
/*****************************************************
* @function_name : InsertTailDCList
* @brief_ : 将新结点插入链表中的尾结点之后
* @param_ :
* DouCirList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/24
* @version_ : v1.0
* @note_ : None
*******************************************************/
//尾插
bool InsertTailDCList(DouCirList_t *Head, DataType_t Data)
{
//1.创建一个新结点
DouCirList_t *NewNode = CreateNewDCLinkedList(Data);
//2.判断链表是否为空
if(Head->Next == Head)
{
//3.链表为空
Head->Next = NewNode;
NewNode->Next = NewNode;
NewNode->Prev = NewNode;
}
else
{
//4.链表不为空
DouCirList_t *Phead = Head->Next;
NewNode->Prev = Phead->Prev; //新结点的Prev指向旧尾结点
NewNode->Next = Phead; //新结点的Next指向首结点
Phead->Prev->Next = NewNode; //旧尾结点的Next指向新结点
Phead->Prev = NewNode; //首结点的Prev指向新结点
}
}
指定插
/*****************************************************
* @function_name : InsertAfterDCList
* @brief_ : 指定目标数据域，将新结点插入目标结点之后(第一个目标结点)
* @param_ :
* DouCirList_t *Head--> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/24
* @version_ : v1.0
* @note_ : None
*******************************************************/
//指定插在后面
bool InsertAfterDCList(DouCirList_t *Head, DataType_t Data, DataType_t Dest)
{
//1.创建一个新结点
DouCirList_t *NewNode = CreateNewDCLinkedList(Data);
//2.判断链表是否为空
if(Head->Next == Head)
{
//链表为空
Head->Next = NewNode;
NewNode->Next = NewNode;
NewNode->Prev = NewNode;
}
else
{
//链表不为空
DouCirList_t *Phead = Head->Next;
// 1.遍历链表，找到目标结点
while(Phead->Data != Dest && Phead->Next != Phead)
{
Phead = Phead->Next; //如果Phead->Data不等于目标结点，则继续遍历
}
//2.判断是否找到目标结点
if(Phead->Data != Dest)
{
//没有找到目标结点
printf("Can't find the Destination!!!\n");
return false;
}
else
{
//找到了目标结点
// if(Phead->Next == Phead)
// {
// //链表只有一个结点 Phead->Next==Phead(利用这个可以简化代码)
// NewNode->Next = Phead->Next; //新结点指向目标结点
// NewNode->Prev = Phead;
// Phead->Prev = NewNode;
// Phead->Next = NewNode; //目标结点指向新结点
// }
//链表有多个结点
NewNode->Prev = Phead; //新结点Prev指向目标结点
NewNode->Next = Phead->Next; //新结点Next指向目标结点Next
Phead->Next->Prev = NewNode; //目标结点NextPrev指向新结点
Phead->Next=NewNode; //目标结点Next指向新结点
}
return true;
}
}
删除结点
头删
/*****************************************************
* @function_name : DeleteHeadDCList
* @brief_ : 删除链表中的首元结点
* @param_ :
* DouCirList_t *Head--> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/24
* @version_ : v1.0
* @note_ : None
*******************************************************/
//头删
bool DeleteHeadDCList(DouCirList_t *Head)
{
//如果链表为空
if(Head->Next==Head)
{
printf("List is Empty!!!");
return false;
}
//链表不为空
DouCirList_t *Phead = Head->Next; //备份首结点地址
if(Phead->Next == Phead)
{
//链表只有一个结点
Head->Next = Head;
Phead->Prev = NULL;
Phead->Next = NULL;
}
else
{
//链表有多个结点
Head->Next=Phead->Next; //头结点指向新首结点
Phead->Next->Prev=Phead->Prev; //新首结点Prev指向尾结点
Phead->Prev->Next=Phead->Next; //尾结点Next指向新首结点
Phead->Next=NULL;
Phead->Prev=NULL;
}
free(Phead);
return true;
}
尾删
/*****************************************************
* @function_name : DeleteTailDCList
* @brief_ : 删除链表中的尾结点
* @param_ :
* DouCirList_t *Head--> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/24
* @version_ : v1.0
* @note_ : None
*******************************************************/
//尾删
bool DeleteTailDCList(DouCirList_t *Head)
{
//如果链表为空
if(Head->Next==Head)
{
printf("List is Empty!!!");
return false;
}
//链表不为空
DouCirList_t *Phead = Head->Next->Prev; //备份尾结点地址
if(Phead->Next == Phead)
{
//链表只有一个结点
Head->Next = Head;
Phead->Prev = NULL;
Phead->Next = NULL;
}
else
{
//链表有多个结点
Phead->Prev->Next=Head->Next; //新尾结点指向首结点
Phead->Next->Prev=Phead->Prev; //首结点Prev指向新尾结点
Phead->Next=NULL;
Phead->Prev=NULL;
}
free(Phead);
return true;
}
指定删
/*****************************************************
* @function_name : DeleteDCList
* @brief_ : 指定目标数据域，删除该结点(第一个目标结点)
* @param_ :
* DouCirList_t *Head--> 链表头结点的地址
* DataType_t Data --> 需删除结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/24
* @version_ : v1.0
* @note_ : None
*******************************************************/
//指定删除
bool DeleteDCList(DouCirList_t *Head, DataType_t Data)
{
//如果链表为空
if(Head->Next==Head)
{
printf("List is Empty!!!");
return false;
}
//链表不为空
DouCirList_t *Phead = Head->Next; //备份首结点地址
//1.遍历链表，找到目标结点
while(Phead->Data != Data && Phead->Next != Phead)
{
Phead = Phead->Next; //如果Phead->Data不等于目标结点，则继续遍历
}
//2.判断是否找到目标结点
if(Phead->Data != Data)
{
//3.没有找到目标结点
printf("Can't find the Destination!!!\n");
return false;
}
//4.找到了目标结点
//5.判断目标结点是否为尾结点
if(Phead->Next == Head->Next)
{
//链表只有一个结点
if(Phead->Next == Phead)
{
Head->Next = Head;
Phead->Prev = NULL;
Phead->Next = NULL;
}
else
//链表有多个结点
{
Phead->Prev->Next=Head->Next; //新尾结点指向首结点
Phead->Next->Prev=Phead->Prev; //首结点Prev指向新尾结点
Phead->Next=NULL;
Phead->Prev=NULL;
}
free(Phead);
}
//目标值不为尾结点
else
{
if(Phead == Head->Next)
Head->Next=Phead->Next;
Phead->Next->Prev=Phead->Prev;
Phead->Prev->Next=Phead->Next;
Phead->Next=NULL;
Phead->Prev=NULL;
free(Phead);
}
return true;
}
遍历链表
/*****************************************************
* @function_name : CirDCLList_Print
* @brief_ : 遍历输出链表各个结点的数据域
* @param_ :
* DouCirList_t *Head --> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/24
* @version_ : v1.0
* @note_ : None
*******************************************************/
//遍历链表
bool CirDCLList_Print(DouCirList_t *Head)
{
//1.如果链表为空
if(Head->Next == Head)
{
printf(" Linked List is Empty\n");
return false;
}
//2.如果链表不为空
DouCirList_t *Phead = Head;
//从首结点开始遍历
while(Phead->Next)
{
//把头结点的直接后继作为新的头结点
Phead = Phead->Next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->Data);
//判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->Next == Head->Next)
{
break;
}
}
return true;
}
摧毁链表
/*****************************************************
* @function_name : DestroyDCList
* @brief_ : 摧毁链表
* @param_ :
* DouCirList_t *Head--> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/24
* @version_ : v1.0
* @note_ : None
*******************************************************/
//摧毁链表
void DestroyDCList(DouCirList_t *Head)
{
while (Head->Next != Head)
{
DeleteHeadDCList(Head);
}
Head->Next = Head;
free(Head);
}