双向链表
双向链表的原理与应用
如果想要提高单向链表或者单向循环链表的访问速度，则可以在链表中的结点中再添加一个指针域，让新添加的指针域指向当前结点的直接前驱的地址，也就意味着一个结点中有两个指针域（prev + next），也被称为双向链表（Double Linked List）。
单向循环链表实现分析：
（1）为了管理单向循环链表，需要构造头结点的数据类型以及构造有效结点的数据类型
// 指的是双向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
// 构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
DataType_t data; // 结点的数据域
struct DoubleLinkedList *prev; // 直接前驱的指针域
struct DoubleLinkedList *next; // 直接后继的指针域
} DoubleLList_t;
(2)创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！
/********************************************************************
*
* name : DoubleLList_Create
* function : 创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
* argument :
* none
*
* retval : 调用成功返回已经完成初始化的双向链表的头结点,否则退出程序
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
// 创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
DoubleLList_t *DoubleLList_Create(void)
{
// 1.创建一个头结点并对头结点申请内存
DoubleLList_t *Head = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL
Head->prev = NULL;
Head->next = NULL;
// 3.把头结点的地址返回即可
return Head;
}
(3)创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：
/********************************************************************
*
* name : DoubleLList_NewNode
* function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
* argument :
* @data 新节点需要存储的数据
*
* retval : 调用成功返回已经完成初始化的双向链表的新节点,否则返回NULL
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
DoubleLList_t *DoubleLList_NewNode(DataType_t data)
{
// 1.创建一个新结点并对新结点申请内存
DoubleLList_t *New = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
// 2.对新结点的数据域和指针域（2个）进行初始化
New->data = data;
New->prev = NULL;
New->next = NULL;
return New;
}
(4)根据情况把新结点插入到链表中，此时可以分为尾部插入、头部插入、指定位置插入：
头插:
原理图：
代码实现：
/********************************************************************
*
* name : DoubleLList_HeadInsert
* function : 将新节点头插进单向循环链表中
* argument :
* @Head 单向循环链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_HeadInsert(DoubleLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL)
{
printf("HeadInsert is fail!n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == NULL)
{
Head->next = New;
printf("HeadInsert of %d is success!n", New->data);
return;
}
// 1.将新节点更换为首节点
New->next = Head->next;
// 2.将原首节点的prev更换为新节点
Head->next->prev = New;
// 3.更换头结点的next
Head->next = New;
printf("HeadInsert of %d is success!n", New->data);
return;
}
尾插：
原理图：
代码实现：
/********************************************************************
*
* name : DoubleLList_TailInsert
* function : 将新节点尾插进双向链表中
* argument :
* @Head 双向链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_TailInsert(DoubleLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL)
{
printf("TailInsert is fail!n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == NULL)
{
Head->next = New;
printf("TailInsert of %d is success!n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至尾结点，将尾结点的next更换为新节点
while (Phead->next != NULL)
{
Phead = Phead->next;
}
// 跳出while循环时，Phead极为尾节点;
Phead->next = New;
// 2.将新节点的Prev指向为尾结点
New->prev = Phead;
printf("TailInsert of %d is success!n", New->data);
return;
}
指定位置插（中间位置，除首尾情况外）:
原理图：
代码实现：
/********************************************************************
*
* name : DoubleLList_DestInsert
* function : 将新节点插进双向链表指定位置中
* argument :
* @Head 双向链表头结点
* @destval 指定位置的数据域值
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
// 指定位置插入（中间位置，排除首尾情况）
void DoubleLList_DestInsert(DoubleLList_t *Head, DataType_t destval, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleLList_t *Phead = Head->next;
//定义一个旗帜变量，用于判断是否找到目标值
int flag = 0;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL)
{
printf("DestInsert is fail!n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == NULL)
{
Head->next = New;
printf("DestInsert of %d is success!n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至目标节点
while (Phead->next != NULL)
{
// 条件判断找出目标节点
if (Phead->data == destval)
{
flag = 1;
break;
}
Phead = Phead->next;
}
//判断是否找到目标节点，否则不执行插入操作
if(flag == 0)
{
printf("destval is no find!n");
free(New);
return;
}
// 跳出while循环时，Phead为目标节点
New->next = Phead->next;
Phead->next->prev = New;
New->prev = Phead;
Phead->next = New;
printf("DestInsert of %d is success!n", New->data);
return;
}
(5) 根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定元素删除：
头删:
原理图：
代码实现：
/********************************************************************
*
* name : DoubleLList_HeadDel
* function : 删除链表的首节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功后删除链表的首节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_HeadDel(DoubleLList_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
DoubleLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!n");
return;
}
// 1.将首节点更换
Head->next = Head->next->next;
// 2.将备份与链表节点断开
Phead->next = NULL;
Head->next->prev = NULL;
// 3.释放掉原首节点
free(Phead);
printf("HeadDel is success!n");
return;
}
尾删:
原理图：
代码实现：
/********************************************************************
*
* name : DoubleLList_TailDel
* function : 删除链表的尾节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功后删除链表的尾节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_TailDel(DoubleLList_t *Head)
{
// 对单向循环链表的首结点的地址进行备份
DoubleLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!n");
return;
}
// 1.遍历至尾结点的前驱节点，跳出while循环时，Phead极为尾节点的前驱节点;
while (Phead->next->next != NULL)
{
Phead = Phead->next;
}
// 2.将尾结点赋值给新的指针变量备份
DoubleLList_t *Temp = Phead->next;
// 3.将尾结点前驱节点更新为尾结点
Phead->next = NULL;
Temp->prev = NULL;
// 4.释放掉原尾结点
free(Temp);
printf("TailDel is success!n");
return;
}
指定位置删（中间位置）:
原理图：
代码实现：
/********************************************************************
*
* name : DoubleLList_DestDel
* function : 删除链表的指定节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
@destval 指定位置的数据域值
*
* retval : 调用成功后删除链表的尾节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_DestDel(DoubleLList_t *Head, DataType_t destval)
{
// 对单向循环链表的首结点的地址进行备份
DoubleLList_t *Phead = Head->next;
// 定义一个旗帜变量，用于判断是否找到目标节点
int flag = 0;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!n");
return;
}
// 1.遍历至为直接前驱节点
while (Phead->next != NULL)
{
// 条件判断找出目标节点
if (Phead->next->data == destval)
{
flag = 1;
break;
}
Phead = Phead->next;
}
//判断是否找到目标节点，没有找到则不执行删除操作
if( flag == 0)
{
printf("destval is no find!n");
return;
}
// 2.定义一个指针变量用于备份删除节点
DoubleLList_t *Temp = Phead->next;
// 3.将删除节点的前驱节点的next改为首节点
Phead->next = Phead->next->next;
Phead->next->prev = Phead;
// 4.将删除节点的next指向NULL
Temp->next = NULL;
Temp->prev = NULL;
// 5.释放删除节点
free(Temp);
printf("DestDel is success!n");
return;
}
(6)遍历输出链表中的所有节点的数据域值
/********************************************************************
*
* name : DoubleLList_Print
* function : 遍历输出单向循环链表中所有节点的数据域
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功输出链表中所有节点的数据域的值
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_Print(DoubleLList_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
DoubleLList_t *Phead = Head;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!n");
return;
}
// 从首结点开始遍历
while (Phead->next)
{
// 把头结点的直接后继作为新的头结点
Phead = Phead->next;
// 输出头结点的直接后继的数据域
printf("%d->", Phead->data);
// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == NULL)
{
break;
}
}
return;
}
代码整体展示:
/*******************************************************************
*
* file name: DoubleLinkedList.c
* author : 790557054@qq.com
* date : 2024/04/23
* function : 该案例是掌握单向循环链表的增删查改原理
* note : None
*
* CopyRight (c) 2023-2024 790557054@qq.com All Right Reseverd
*
* *****************************************************************/
#include
#include
// 指的是双向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
// 构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
DataType_t data; // 结点的数据域
struct DoubleLinkedList *prev; // 直接前驱的指针域
struct DoubleLinkedList *next; // 直接后继的指针域
} DoubleLList_t;
/********************************************************************
*
* name : DoubleLList_Create
* function : 创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
* argument :
* none
*
* retval : 调用成功返回已经完成初始化的双向链表的头结点,否则退出程序
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
// 创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
DoubleLList_t *DoubleLList_Create(void)
{
// 1.创建一个头结点并对头结点申请内存
DoubleLList_t *Head = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL
Head->prev = NULL;
Head->next = NULL;
// 3.把头结点的地址返回即可
return Head;
}
/********************************************************************
*
* name : DoubleLList_NewNode
* function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
* argument :
* @data 新节点需要存储的数据
*
* retval : 调用成功返回已经完成初始化的双向链表的新节点,否则返回NULL
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
DoubleLList_t *DoubleLList_NewNode(DataType_t data)
{
// 1.创建一个新结点并对新结点申请内存
DoubleLList_t *New = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
// 2.对新结点的数据域和指针域（2个）进行初始化
New->data = data;
New->prev = NULL;
New->next = NULL;
return New;
}
/********************************************************************
*
* name : DoubleLList_HeadInsert
* function : 将新节点头插进单向循环链表中
* argument :
* @Head 单向循环链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_HeadInsert(DoubleLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL)
{
printf("HeadInsert is fail!n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == NULL)
{
Head->next = New;
printf("HeadInsert of %d is success!n", New->data);
return;
}
// 1.将新节点更换为首节点
New->next = Head->next;
// 2.将原首节点的prev更换为新节点
Head->next->prev = New;
// 3.更换头结点的next
Head->next = New;
printf("HeadInsert of %d is success!n", New->data);
return;
}
/********************************************************************
*
* name : DoubleLList_TailInsert
* function : 将新节点尾插进双向链表中
* argument :
* @Head 双向链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_TailInsert(DoubleLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL)
{
printf("TailInsert is fail!n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == NULL)
{
Head->next = New;
printf("TailInsert of %d is success!n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至尾结点，将尾结点的next更换为新节点
while (Phead->next != NULL)
{
Phead = Phead->next;
}
// 跳出while循环时，Phead极为尾节点;
Phead->next = New;
// 2.将新节点的Prev指向为尾结点
New->prev = Phead;
printf("TailInsert of %d is success!n", New->data);
return;
}
/********************************************************************
*
* name : DoubleLList_DestInsert
* function : 将新节点插进双向链表指定位置中
* argument :
* @Head 双向链表头结点
* @destval 指定位置的数据域值
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
// 指定位置插入
void DoubleLList_DestInsert(DoubleLList_t *Head, DataType_t destval, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL)
{
printf("DestInsert is fail!n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == NULL)
{
Head->next = New;
printf("DestInsert of %d is success!n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至目标节点
while (Phead->next != NULL)
{
// 条件判断找出目标节点
if (Phead->data == destval)
{
break;
}
Phead = Phead->next;
}
// 跳出while循环时，Phead为目标节点
New->next = Phead->next;
Phead->next->prev = New;
New->prev = Phead;
Phead->next = New;
printf("DestInsert of %d is success!n", New->data);
return;
}
/********************************************************************
*
* name : DoubleLList_HeadDel
* function : 删除链表的首节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功后删除链表的首节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_HeadDel(DoubleLList_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
DoubleLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!n");
return;
}
// 1.将首节点更换
Head->next = Head->next->next;
// 2.将备份与链表节点断开
Phead->next = NULL;
Head->next->prev = NULL;
// 3.释放掉原首节点
free(Phead);
printf("HeadDel is success!n");
return;
}
/********************************************************************
*
* name : DoubleLList_Print
* function : 遍历输出单向循环链表中所有节点的数据域
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功输出链表中所有节点的数据域的值
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_Print(DoubleLList_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
DoubleLList_t *Phead = Head;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!n");
return;
}
// 从首结点开始遍历
while (Phead->next)
{
// 把头结点的直接后继作为新的头结点
Phead = Phead->next;
// 输出头结点的直接后继的数据域
printf("%d->", Phead->data);
// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == NULL)
{
break;
}
}
return;
}
/********************************************************************
*
* name : DoubleLList_TailDel
* function : 删除链表的尾节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功后删除链表的尾节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_TailDel(DoubleLList_t *Head)
{
// 对单向循环链表的首结点的地址进行备份
DoubleLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!n");
return;
}
// 1.遍历至尾结点的前驱节点，跳出while循环时，Phead极为尾节点的前驱节点;
while (Phead->next->next != NULL)
{
Phead = Phead->next;
}
// 2.将尾结点赋值给新的指针变量备份
DoubleLList_t *Temp = Phead->next;
// 3.将尾结点前驱节点更新为尾结点
Phead->next = NULL;
Temp->prev = NULL;
// 4.释放掉原尾结点
free(Temp);
printf("TailDel is success!n");
return;
}
/********************************************************************
*
* name : DoubleLList_DestDel
* function : 删除链表的指定节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
@destval 指定位置的数据域值
*
* retval : 调用成功后删除链表的尾节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleLList_DestDel(DoubleLList_t *Head, DataType_t destval)
{
// 对单向循环链表的首结点的地址进行备份
DoubleLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!n");
return;
}
// 1.遍历至为直接前驱节点
while (Phead->next != NULL)
{
// 条件判断找出目标节点
if (Phead->next->data == destval)
{
break;
}
Phead = Phead->next;
}
// 2.定义一个指针变量用于备份删除节点
DoubleLList_t *Temp = Phead->next;
// 3.将删除节点的前驱节点的next改为首节点
Phead->next = Phead->next->next;
Phead->next->prev = Phead;
// 4.将删除节点的next指向NULL
Temp->next = NULL;
Temp->prev = NULL;
// 5.释放删除节点
free(Temp);
printf("DestDel is success!n");
return;
}
int main(int argc, char const *argv[])
{
// 创建头结点
DoubleLList_t *Head = DoubleLList_Create();
// 头插
DoubleLList_HeadInsert(Head, 10);
DoubleLList_HeadInsert(Head, 20);
printf("n");
// 遍历显示
DoubleLList_Print(Head);
printf("n");
// 尾插
DoubleLList_TailInsert(Head, 50);
DoubleLList_TailInsert(Head, 60);
printf("n");
// 遍历显示
DoubleLList_Print(Head);
printf("n");
// 指定位置插
DoubleLList_DestInsert(Head, 20, 666);
printf("n");
// 遍历显示
DoubleLList_Print(Head);
printf("n");
// 头删
DoubleLList_HeadDel(Head);
printf("n");
// 遍历显示
DoubleLList_Print(Head);
printf("n");
// 尾删
DoubleLList_TailDel(Head);
printf("n");
// 遍历显示
DoubleLList_Print(Head);
printf("n");
// 指定删
DoubleLList_DestDel(Head, 50);
printf("n");
// 遍历显示
DoubleLList_Print(Head);
printf("n");
return 0;
}
结果验证
代码分析补充：
代码中所说的指定位置删除/增加，均为排除了首尾情况，即链表中间位置进行操作，如果需要任意位置删除/增加，则需要考虑首尾情况。
