数据结构 — 双向链表

1、双向链表

2.1、双向不循环链表

2.2、双向循环链表

1、双向链表

双向链表和单向链表相比，最大的不同是指针域中多了一个指向前一个节点的地址域。这样一来，双向链表中的每个节点就保存了前后节点的地址，从而通过地址形成一条链式的存储结构。

双向链表的最大便利之处在于查询链表时不仅可以正向查找也可以反向查找，甚至如果当前查询的位置在链表中间的位置的时候，可以反方向两头查找，提高查找的速度和效率，增加了便利。

双向链表也有循环和不循环两种方式，下面分别介绍。

2.1、双向不循环链表

双向不循环链表是头结点的前一个指针指向头结点自身，尾节点的后一个指针指向为NULL。示意图如下：

双向不循环链表的代码实现如下示例：


#include <stdio.h>
#include <stdlib.h>
 
 
/*** 定义链表操作的位置：开头、中间、结尾 ***/
typedef enum
{
	Head = 1,
	Middle,
	End,
}Location;
 
 
/*** 定义一个链表节点 ******/
// 1.定义一个链表节点的数据域。以记录一个苹果的信息为例，为方便说明，假设每个苹果的信息各不相同
typedef struct LinkData_struct
{
	int  weight; // 苹果的重量
	int  hight;  // 苹果的高度
	// ... 		 // 还可以定义更多的其他的数据
}LinkData_t;
 
typedef struct LinkNode_Struct
{
	LinkData_t data;				// 链表节点的数据域
	struct LinkNode_Struct *Prev; 	// 链表节点的上一个节点的指针域
	struct LinkNode_Struct *Next; 	// 链表节点的下一个节点的指针域
}LinkNode_t;
 
 
/*** 定义一个单向链表的头结点 ***/
LinkNode_t AppleInfo_head; //作为单向链表的一个头结点
 
 
// 初始化单向链表的头结点
void Init_LinkNode(LinkNode_t * HeadNode)
{
	HeadNode->Next = NULL;
	HeadNode->Prev = NULL;
}
 
// 创建一个链表节点并接入到链表中
LinkNode_t * LinkNode_Create(LinkNode_t * HeadNode, LinkData_t *InsetData)
{
	LinkNode_t *Prev_pf,*Next_pf;
	LinkNode_t *xReturn = NULL;
	LinkNode_t *Node = (LinkNode_t *)malloc(sizeof(LinkNode_t));
 
	if (Node == NULL)
	{
		printf("节点创建失败！！！\r\n");
		return NULL;
	}
 
	Prev_pf = Next_pf = HeadNode;
	
	// 第一节点从头结点后面开始插入
	if (HeadNode->Next == NULL && HeadNode->Prev == NULL)
	{
		HeadNode->Next = Node;
		Node->Next = NULL;
		Node->Prev = HeadNode;
		Node->data.hight  = InsetData->hight;
		Node->data.weight = InsetData->weight;
		xReturn = Node;
	}
	else
	{
		while (Next_pf->Next != NULL)
		{
			Next_pf = Next_pf->Next;
		}
		Next_pf->Next = Node;
		Node->Prev = Next_pf;
		Node->Next = NULL;
		Node->data.hight = InsetData->hight;
		Node->data.weight = InsetData->weight;
		xReturn = Node;
	}
	
	printf("完成一个链表节点的创建，地址 = 0x%X\r\n",xReturn);
	return xReturn;
}
 
// 删除链表中的某个节点,根据weight进行删除
void destroy_LinkNode(LinkNode_t * HeadNode, int weight)
{
	int deleteFlag = 0;
	LinkNode_t *pf;
 
	pf = HeadNode;
 
	do
	{
		pf = pf->Next;
		if (pf->data.weight == weight)
		{
			deleteFlag = 1;
			break;
		}		
	}while (pf->Next != NULL);
 
	if (!deleteFlag)
	{
		printf("链表中找不到这个节点！！！\r\n");
	}
	else
	{
		if (pf->Next == NULL)
		{
			pf->Prev->Next = NULL;
		}
		else
		{
			pf->Prev->Next = pf->Next;
			pf->Next->Prev = pf->Prev; 
		}
		
		free(pf);
		printf("节点weight = %d 销毁成功！\r\n",weight);
	}
}
 
// 输出显示整条链表
void print_LinkNode_Info(LinkNode_t * HeadNode)
{
	int length = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		printf("weight = %d\r\n", (int)pf->data.weight);
		printf("height = %d\r\n", (int)pf->data.hight);
		printf("\r\n");
		length++;
	}while (pf->Next != NULL);
	printf("链表输出完成。长度为：%d\r\n",length);
}
 
 
// 按条件查询链表中某个节点的数据
void search_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("\r\n");
		}
		length++;
	}while (pf->Next != NULL);
 
	if(search_flag)
	{
		printf("链表查找结束。所在节点位置为：%d\r\n",length);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}
 
// 查询链表中有几个相同的数据
void search_Same_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0,cnt = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		length++;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("这个节点在链表中的位置：%d\r\n",length);
			cnt++;
		}
	}while (pf->Next != NULL);
 
	if(search_flag)
	{
		printf("链表查找结束。相同数据的节点数量为：%d\r\n",cnt);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}
 
 
void print_debug_info(void)
{
	printf("******** 链表控制台 *****************\r\n");
	printf("*                                  \r\n");
	printf("*  1：创建链表                      \r\n");
	printf("*  2：删除链表                      \r\n");
	printf("*  3：显示整条链表的数据             \r\n");
	printf("*  4：按条件查找链表节点             \r\n");
	printf("*  5：查找链表中有几个相同数据的节点  \r\n");
	printf("*  8：清空显示                      \r\n");
	printf("*  9：结束运行                      \r\n");
	printf("*                                  \r\n");
	printf("************************************\r\n");
}
 
 
int main(int argc, char *argv[]) 
{
	int Num,i,j;
	int Options;
	int weight,height;
	LinkData_t InsetData;
 
	Init_LinkNode(&AppleInfo_head);
 
	
	while (1)
	{
		print_debug_info();
		printf("\r\n请输入需要操作的键值，按回车键确认！\r\n");
		scanf("%d", &Options);
		switch (Options)
		{
			case 1:
				/*** 创建任意长度的链表 **********************************************************/
				printf("请输入需要创建的链表节点的数量,按回车结束！\r\n");
				scanf("%d", &Num);
 
				printf("请输入节点的数据：\r\n");
				for (i = 0; i < Num; i++)
				{
					printf("请输入第 %d 节点的数据,weight = Height = ,输入完毕按回车结束！\r\n",i+1);
					scanf("%d %d", &weight,&height);
					InsetData.weight = weight;
					InsetData.hight  = height;
					printf("weight = %d height = %d\r\n",weight,height);
 
					if(LinkNode_Create(&AppleInfo_head, &InsetData) > NULL)
					{
						printf("节点 %d 创建成功！\r\n\r\n\r\n",i+1);
					}
					else
					{
						printf("节点 %d 创建失败！\r\n\r\n\r\n",i+1);
					}
				}
				printf("\r\n");
				break;
			
			case 2:
				/******* 删除链表中的某个节点 ***************************************************/
				printf("请输入需要删除的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				destroy_LinkNode(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 3:
				printf("链表数据为：\r\n");
				print_LinkNode_Info(&AppleInfo_head);
				printf("\r\n");
				break;
 
			case 4:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 5:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_Same_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 8:
				system("cls");
				break;
 
			case 9:
				printf("退出链表控制台，请再次运行程序！\r\n");
				return;
				break;
			
			default:
				printf("无效的键值，请重新输入！\r\n");
				break;
		}
	}
	return 0;
}

2.2、双向循环链表

双向循环链表是头结点的前一个指针指向尾结点的地址，尾节点的后一个指针指向头结点的地址所在，从而构成一种链式的循环结构。示意图如下：

双向循环链表的示意代码如下：


#include <stdio.h>
#include <stdlib.h>
 
 
/*** 定义链表操作的位置：开头、中间、结尾 ***/
typedef enum
{
	Head = 1,
	Middle,
	End,
}Location;
 
 
/*** 定义一个链表节点 ******/
// 1.定义一个链表节点的数据域。以记录一个苹果的信息为例，为方便说明，假设每个苹果的信息各不相同
typedef struct LinkData_struct
{
	int  weight; // 苹果的重量
	int  hight;  // 苹果的高度
	// ... 		 // 还可以定义更多的其他的数据
}LinkData_t;
 
typedef struct LinkNode_Struct
{
	LinkData_t data;				// 链表节点的数据域
	struct LinkNode_Struct *Prev; 	// 链表节点的上一个节点的指针域
	struct LinkNode_Struct *Next; 	// 链表节点的下一个节点的指针域
}LinkNode_t;
 
 
/*** 定义一个单向链表的头结点 ***/
LinkNode_t AppleInfo_head; //作为单向链表的一个头结点
 
 
// 初始化单向链表的头结点
void Init_LinkNode(LinkNode_t * HeadNode)
{
	HeadNode->Next = NULL;
	HeadNode->Prev = HeadNode;	// 双向循环链表的头结点的前一个指针指向头结点本身
}
 
// 创建一个链表节点并接入到链表中
LinkNode_t * LinkNode_Create(LinkNode_t * HeadNode, LinkData_t *InsetData)
{
	LinkNode_t *Prev_pf,*Next_pf;
	LinkNode_t *xReturn = NULL;
	LinkNode_t *Node = (LinkNode_t *)malloc(sizeof(LinkNode_t));
 
	if (Node == NULL)
	{
		printf("节点创建失败！！！\r\n");
		return NULL;
	}
 
	Prev_pf = Next_pf = HeadNode;
	
	// 第一节点从头结点后面开始插入
	if (HeadNode->Next == NULL && HeadNode->Prev == HeadNode)
	{
		HeadNode->Next = Node;
		HeadNode->Prev = Node;
		Node->Next = HeadNode;
		Node->Prev = HeadNode;
		Node->data.hight  = InsetData->hight;
		Node->data.weight = InsetData->weight;
		xReturn = Node;
	}
	else
	{
		while (Next_pf->Next != HeadNode)
		{
			Next_pf = Next_pf->Next;
		}
		Next_pf->Next  = Node;
		HeadNode->Prev = Node;
		Node->Prev = Next_pf;
		Node->Next = HeadNode;
		Node->data.hight = InsetData->hight;
		Node->data.weight = InsetData->weight;
		xReturn = Node;
	}
	
	printf("完成一个链表节点的创建，地址 = 0x%X\r\n",xReturn);
	return xReturn;
}
 
// 删除链表中的某个节点,根据weight进行删除
void destroy_LinkNode(LinkNode_t * HeadNode, int weight)
{
	int deleteFlag = 0;
	LinkNode_t *pf;
 
	pf = HeadNode;
 
	do
	{
		pf = pf->Next;
		if (pf->data.weight == weight)
		{
			deleteFlag = 1;
			break;
		}		
	}while (pf->Next != HeadNode);
 
	if (!deleteFlag)
	{
		printf("链表中找不到这个节点！！！\r\n");
	}
	else
	{
		if (pf->Next == HeadNode)
		{
			pf->Prev->Next = HeadNode;
			HeadNode->Prev = pf;
		}
		else
		{
			pf->Prev->Next = pf->Next;
			pf->Next->Prev = pf->Prev; 
		}
		
		free(pf);
		printf("节点weight = %d 销毁成功！\r\n",weight);
	}
}
 
// 输出显示整条链表
void print_LinkNode_Info(LinkNode_t * HeadNode)
{
	int length = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		printf("weight = %d\r\n", (int)pf->data.weight);
		printf("height = %d\r\n", (int)pf->data.hight);
		printf("\r\n");
		length++;
	}while (pf->Next != HeadNode);
	printf("链表输出完成。长度为：%d\r\n",length);
}
 
 
// 按条件查询链表中某个节点的数据
void search_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("\r\n");
		}
		length++;
	}while (pf->Next != HeadNode);
 
	if(search_flag)
	{
		printf("链表查找结束。所在节点位置为：%d\r\n",length);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}
 
// 查询链表中有几个相同的数据
void search_Same_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0,cnt = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		length++;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("这个节点在链表中的位置：%d\r\n",length);
			cnt++;
		}
	}while (pf->Next != HeadNode);
 
	if(search_flag)
	{
		printf("链表查找结束。相同数据的节点数量为：%d\r\n",cnt);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}
 
 
void print_debug_info(void)
{
	printf("******** 链表控制台 *****************\r\n");
	printf("*                                  \r\n");
	printf("*  1：创建链表                      \r\n");
	printf("*  2：删除链表                      \r\n");
	printf("*  3：显示整条链表的数据             \r\n");
	printf("*  4：按条件查找链表节点             \r\n");
	printf("*  5：查找链表中有几个相同数据的节点  \r\n");
	printf("*  8：清空显示                      \r\n");
	printf("*  9：结束运行                      \r\n");
	printf("*                                  \r\n");
	printf("************************************\r\n");
}
 
 
int main(int argc, char *argv[]) 
{
	int Num,i,j;
	int Options;
	int weight,height;
	LinkData_t InsetData;
 
	Init_LinkNode(&AppleInfo_head);
 
	
	while (1)
	{
		print_debug_info();
		printf("\r\n请输入需要操作的键值，按回车键确认！\r\n");
		scanf("%d", &Options);
		switch (Options)
		{
			case 1:
				/*** 创建任意长度的链表 **********************************************************/
				printf("请输入需要创建的链表节点的数量,按回车结束！\r\n");
				scanf("%d", &Num);
 
				printf("请输入节点的数据：\r\n");
				for (i = 0; i < Num; i++)
				{
					printf("请输入第 %d 节点的数据,weight = Height = ,输入完毕按回车结束！\r\n",i+1);
					scanf("%d %d", &weight,&height);
					InsetData.weight = weight;
					InsetData.hight  = height;
					printf("weight = %d height = %d\r\n",weight,height);
 
					if(LinkNode_Create(&AppleInfo_head, &InsetData) > NULL)
					{
						printf("节点 %d 创建成功！\r\n\r\n\r\n",i+1);
					}
					else
					{
						printf("节点 %d 创建失败！\r\n\r\n\r\n",i+1);
					}
				}
				printf("\r\n");
				break;
			
			case 2:
				/******* 删除链表中的某个节点 ***************************************************/
				printf("请输入需要删除的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				destroy_LinkNode(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 3:
				printf("链表数据为：\r\n");
				print_LinkNode_Info(&AppleInfo_head);
				printf("\r\n");
				break;
 
			case 4:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 5:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_Same_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 8:
				system("cls");
				break;
 
			case 9:
				printf("退出链表控制台，请再次运行程序！\r\n");
				return;
				break;
			
			default:
				printf("无效的键值，请重新输入！\r\n");
				break;
		}
	}
	return 0;
}

总结：

单向链表和双向链表都有各自的用处，到底用哪一个好还是要根据自己到底需要什么样的功能决定，实际问题实际处理。实际开发中，只要不是一些大型的项目，或者一些要求高效率快速的要求，一般单向的链表也就足够了。

相关阅读:
Windows 安装的虚拟环境位置在哪里，怎么找到pycharm对应的python解释器
 人工智能AI 全栈体系（四）
家政预约小程序07服务分类展示
 【微信小程序】事件传参的两种方式
 第02章变量
 Vim操作的常用命令记录
 知识图谱丨知识图谱赋能企业数字化转型
 掌握Linux常用命令，扫平面试需求障碍
 xilinx primitives(原语)
东北大学acm暑期夏令营结构体
原文地址：https://blog.csdn.net/weixin_43866583/article/details/127090511