[数据结构与算法]2021-09-03

双向链表的使用（数据结构）

一、双向链表的概述

双向链表也是链表的一种，它每个数据结点中都有两个结点，分别指向其直接前驱和直接后继。所以我们从双向链表的任意一个结点开始都可以很方便的访问其前驱元素和后继元素

二、双向链表的存储结构

三、双向与单向链表区别

1.单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。.
2.单向链表不能自我删除，需要靠辅助节点
3.双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp,temp 是待删除节点的前一个节点

四、代码测试

/**************************双向链表结构体创建**************************/
//定义结构体
struct Node
{
	int iData; //结构体成员
	struct Node *pPre; //结点前驱
	struct Node *pNext;//结点后驱
};

//在下面代码测试中函数不带参这里我们将头结点和尾结点以及结点的个数定义全局变量
//定义头结点 尾结点为全局变量和结点个数
struct  Node *g_pHead = NULL; //初始化头结点 防止野指针
struct  Node *g_pEnd = NULL;//初始化尾结点 防止野指针
int g_CountNode = 0;//初始化结点数量

1.头添加法和尾添加法

原理图片展示

头添加

新节点的下一个指向头结点
头结点的前一个指向新节点
新节点成为新的头结点

尾添加

尾结点的下一个指向新节点
新节点的前一个指向尾结点
新节点成为尾结点（上面图片中写错了一个）

//头插法加入结点
void AddNodeByHead(int iData)
{
	//参数合法性检测
	if(0 > g_CountNode)
	{
		printf("Node Number is error !!!\n");
		return;
	}

	//创建结点
	struct Node *pTemp = (struct Node *)malloc(sizeof(struct Node));
	//判断是否创建成功
	if(NULL == pTemp)
	{
		printf("malloc is error !!!\n");
		return;
	}
	else
	{
		//结构体成员赋值
		pTemp->iData = iData;
		pTemp->pPre = NULL;
		pTemp->pNext = NULL;

		//链接
		if(NULL == g_pHead)
		{
			//头结点为空 该链表中没有数据 头结点== 尾结点
			g_pHead = pTemp;
			g_pEnd = pTemp;
		}
		else
		{
			pTemp->pNext = g_pHead;
			g_pHead->pPre = pTemp;
			g_pHead = pTemp;
		}
	}
	g_CountNode++;
}


//尾插法加入结点数据
void AddNodeByTail(int iData)
{
	//参数合法性判断
	if(0 > g_CountNode)
	{
		printf(" Node Number is error !!!\n");
		return;
	}
	else
	{
		//创建结点
		struct Node *pTemp = (struct Node *)malloc(sizeof(struct Node));
		//判断是否创建成功
		if(NULL == pTemp)
		{
			printf("malloc is error !!!\n");
			return;
		}
		//结构体成员赋值
		pTemp->iData = iData;
		pTemp->pPre = NULL;
		pTemp->pNext = NULL;

		//数据链接
		//如果头结点为空 头结点==尾结点
		if(NULL == g_pHead)
		{
			g_pHead = pTemp;
			g_pEnd = pTemp;
		}
		else
		{
			g_pEnd->pNext = pTemp;
			pTemp->pPre = g_pEnd;
			g_pEnd = pTemp;
		}
	}
	g_CountNode++;
}

2.正向和反向打印链表

双链表的打印和单链表的打印大同小异，主要差异在于单向链表只能从头向尾遍历链表，而双向链表既可以从头到尾也可以从尾到头，在实际的运用中大大的提升了数据处理效率。

图片原理展示

//正向打印链表
void PrintListByForward()
{
	//参数合法性检测
	if(NULL == g_pHead )
	{
		printf("g_pHead IS EMPTY ！！！\n");
		return ;
	}
	//定义临时结构体变量赋值头结点
	struct Node *pTemp = g_pHead;
	printf("current node is %d\n",g_CountNode);
	while(NULL != pTemp)
	{
		printf("%d ",pTemp->iData);
		pTemp=pTemp->pNext;
	}
	printf("\n");
}

//反向打印链表
void PrintListByBack()
{
	//参数合法性检测
	if(NULL == g_pHead)
	{
		printf("g_pHead is Empty!!!\n");
		return ;
	}
	//定义临时结构体变量赋值头结点
	struct Node *pTemp = g_pEnd;
	printf("Node Number IS %d\n",g_CountNode);
	while(NULL != pTemp)
	{
		printf("%d ",pTemp->iData);
		pTemp = pTemp->pNext;
	}
	printf("\n");
}

3.链表的释放

//释放链表
void FreeList()
{
	//参数合法性检测
	if(NULL == g_pHead)
	{
		//链表为空直接返回
		return;
	}
	struct Node *pTemp = g_pHead;
	while(NULL != pTemp)
	{
		struct Node *pt = pTemp;
		pTemp = pTemp->pNext;
		free(pt);
	}
	//free完成 为结构体成员重新赋初值
	g_pHead = NULL;
	g_pEnd = NULL;
	g_CountNode = 0;
}

4.通过指定下标和数据查找结点

//通过下标查找结点
struct Node *FindNodeByIndex(int iIndex)
{
	//参数合法性检测
	if(NULL == g_pHead || iIndex < 0 || iIndex > g_CountNode)
	{
		printf("Node Index is error !!!\n");
		return NULL;
	}
	//循环查找数据
	int Index = 0;
	struct Node *pTemp = g_pHead;
	while(pTemp != NULL)
	{
		if(Index == iIndex)
		{
			break;
		}
		pTemp = pTemp->pNext;
	    Index++;
	}
	return pTemp;
}


//通过数据查找结点
struct Node *FindNodeByData(int iValue)
{
	//参数合法性检测
	if(NULL == g_pHead)
	{
		printf("g_pHead is Empty!!!\n");
		return NULL;
	}
	//循环遍历查找
	struct Node *pTemp = g_pHead;
	while(NULL != pTemp)
	{
		if(pTemp->iData == iValue)
		{
			return pTemp;
		}
		pTemp = pTemp->pNext;
	}
}

5.通过指定下标和数据对结点进行数据修改

/通过指定下标修改数据
void ModiNodeByIndex(int iIndex ,int iValue)
{
	//先通过下标查找到该数据 定义变量返回查找的结点数据
	struct Node *Res = FindNodeByIndex(iIndex);
	if(NULL == Res)
	{
		printf("Find Node is failed!!!\n");
		return;
	}
	else
	{
		//查找成功 进行相应下标数数据的修改
		Res->iData = iValue;
	}
}


//通过指定数据修改数据
void ModiNodeByData(int iData,int iValue)
{
	//先通过数据查找 定义变量返回查找的数据是否成功
	struct Node *Res = FindNodeByData(iData);
	if(NULL == Res)
	{
		printf("Find Node is failed!!!\n");
		return;
	}
	else
	{
		//查找成功 进行对应数据的修改
		Res->iData = iValue;
	}
}

6.通过指定下标和数据对结点进行数据删除

//删除结点情况判断
void DeleteNode(struct Node *pTemp)
{
	//参数合法性jianc
	if(NULL == g_pHead)
	{
		printf("Node is Empty!!!\n");
		return;
	}
	//结点位置情况考虑
		//只有一个节点
		if(pTemp == g_pHead )
		{
			if(pTemp == g_pEnd)
			{
				free(pTemp);
				g_pHead = NULL;
				g_pEnd = NULL;
			//	g_CountNode--; //结点--
			}	
			//有多个结点
			else
			{
				//结点向下走
				pTemp = pTemp->pNext;
				free(pTemp->pPre);
				pTemp->pPre = NULL;
				//g_CountNode--;
			}
		}
		//结点为尾结点
		else if(pTemp == g_pEnd)
		{
			//尾巴前移
			pTemp = pTemp->pPre;
			//释放
			free(pTemp->pNext);
			pTemp->pNext = NULL;
			//g_CountNode--;
		}
		//为中间结点
		else
		{
			//当前结点的前一个指针当前结点的下一个
			pTemp->pPre->pNext = pTemp->pNext;
			//当前结点的下一个指向当前结点的前一个
			pTemp->pNext = pTemp->pPre;
			free(pTemp);
			//g_CountNode--;
		}
		g_CountNode--;//结点数量自减
}


//通过下标删除结点
void DeleteNodeByIndex(int iIndex)
{
	struct Node * Res = FindNodeByIndex(iIndex);
	if(Res != NULL)//成功找到该下标
	{
		DeleteNode(Res);
	}
}


//通过指定数据删除相同结点
void DeleteNodeByData(int iData)
{
	struct Node *Res = FindNodeByData(iData);
	while(Res != NULL)//成功找到该数据
	{
		DeleteNode(Res);
		//printf("%d Delete success\n",Res->iData);
	}
}

7.指定下标或数据结点前添加数据（采样头添加法）

//指定下标前添加多个结点(头添加)
void AddNodeByIndex(int iData,int Count,int iIndex)
{
	//参数合法性检测
	if(Count == 0 || iIndex < 0 || iIndex > g_CountNode)
	{
		printf("Node param is error!!!\n");
		return;
	}
	//头结点
	if(iIndex == 0)
	{
		//循环添加个数
		for(int i = 0 ; i< Count ;i++)
		{
			AddNodeByHead(iData);
		}
	}
	//尾结点
	else if(iIndex == g_CountNode)
	{
		//循环添加个数
		for(int i = 0; i < Count ;i++)
		{
			AddNodeByTail(iData);
		}
	}
	//中间位置
	else
	{
		struct Node *pt = g_pHead;
		for(int i = 0 ; i < iIndex ;i++)
		{
			pt = pt->pNext;
		}
		//创建新数据空间
		for(int i = 1 ;i <= Count ;i++)
		{
			struct Node *pTemp = (struct Node *)malloc(sizeof(struct Node));
			//合法性判断
			if(NULL == pTemp)
			{
				printf("malloc failed!!!\n");
				return;
			}
			//结构体成员赋值
			pTemp->iData = iData;
			pTemp->pNext = NULL;
			pTemp->pPre = NULL;
			//结点链接
			//指定位置前一个与新结点相连
			pt->pPre->pNext = pTemp;
			pTemp->pPre = pt->pPre;
			//新结点与指定位置向连
			pTemp->pNext = pt;
			pTemp->pPre = pTemp;
		}	
			g_CountNode+=Count; //结点数量增加
	}
}

//指定数据前添加结点(头添加)
void AddNodeByData(int iData,int iValue)
{
	//参数合法性检测
	if(NULL == g_pHead)
	{
		printf(" Node is Empty!!!\n");
		return ;
	}
	struct Node *pTemp = g_pHead;
	while(NULL != pTemp)
	{
		//循环查找
		if(pTemp->iData == iData)
		{
			break; //找到该结点跳出循环
		}
		pTemp = pTemp->pNext;
	}
	if(pTemp != NULL)
	{
		//头结点
		if(pTemp == g_pHead)
		{
			AddNodeByHead(iValue);
		}
		else
		{
			//中间添加
			struct Node *pt = (struct Node *)malloc(sizeof(struct Node));
			//判断是否空间合法
			if(NULL == pt)
			{
				printf("malloc failed!!!\n");
				return;
			}
			//结构体成原赋值
			pt->iData = iValue;
			pt->pPre = NULL;
			pt->pNext = NULL;
			//链接
			//当前结点的前一个与新结点相连
			pTemp->pPre->pNext = pt;
			pt->pPre = pTemp->pPre;
			//新结点与当前结点相连
			pt->pNext = pTemp;
			pTemp->pPre = pt;
			g_CountNode++; //结点数量增加
		}
	}	
}

8.整体代码测试

/*****************************双向链表练习*************************/
#include <stdio.h>
#include <stdlib.h>
//定义结构体
struct Node
{
	int iData; //结构体成员
	struct Node *pPre; //结点前驱
	struct Node *pNext;//结点后驱
};

//定义头结点 尾结点为全局变量和结点个数
struct  Node *g_pHead = NULL; //初始化头结点 防止野指针
struct  Node *g_pEnd = NULL;//初始化尾结点 防止野指针
int g_CountNode = 0;//初始化结点数量


//功能函数
void AddNodeByHead(int iData); //头插法添加结点
void AddNodeByTail(int iData); //尾插法添加结点
struct Node *FindNodeByIndex(int iIndex);//通过下标查找结点
struct Node *FindNodeByData(int iValue);//通过指定数据修改数据
void ModiNodeByIndex(int iIndex ,int iValue);//通过指定下标修改数据
void ModiNodeByData(int iData ,int iValue);//通过指定数据修改数据
void AddNodeByIndex(int iData,int Count,int iIndex);//指定下标前添加多个结点(头添加)
void AddNodeByData(int iData,int iValue);//指定数据前提交结点(头添加)
void FreeList();//释放链表
void PrintListByForward(); //正向打印链表
void PrintListByBack();  //反向打印链表



//头插法加入结点
void AddNodeByHead(int iData)
{
	//参数合法性检测
	if(0 > g_CountNode)
	{
		printf("Node Number is error !!!\n");
		return;
	}

	//创建结点
	struct Node *pTemp = (struct Node *)malloc(sizeof(struct Node));
	//判断是否创建成功
	if(NULL == pTemp)
	{
		printf("malloc is error !!!\n");
		return;
	}
	else
	{
		//结构体成员赋值
		pTemp->iData = iData;
		pTemp->pPre = NULL;
		pTemp->pNext = NULL;

		//链接
		if(NULL == g_pHead)
		{
			//头结点为空 该链表中没有数据 头结点== 尾结点
			g_pHead = pTemp;
			g_pEnd = pTemp;
		}
		else
		{
			pTemp->pNext = g_pHead;
			g_pHead->pPre = pTemp;
			g_pHead = pTemp;
		}
	}
	g_CountNode++;
}


//尾插法加入结点数据
void AddNodeByTail(int iData)
{
	//参数合法性判断
	if(0 > g_CountNode)
	{
		printf(" Node Number is error !!!\n");
		return;
	}
	else
	{
		//创建结点
		struct Node *pTemp = (struct Node *)malloc(sizeof(struct Node));
		//判断是否创建成功
		if(NULL == pTemp)
		{
			printf("malloc is error !!!\n");
			return;
		}
		//结构体成员赋值
		pTemp->iData = iData;
		pTemp->pPre = NULL;
		pTemp->pNext = NULL;

		//数据链接
		//如果头结点为空 头结点==尾结点
		if(NULL == g_pHead)
		{
			g_pHead = pTemp;
			g_pEnd = pTemp;
		}
		else
		{
			g_pEnd->pNext = pTemp;
			pTemp->pPre = g_pEnd;
			g_pEnd = pTemp;
		}
	}
	g_CountNode++;
}

//指定下标前添加多个结点(头添加)
void AddNodeByIndex(int iData,int Count,int iIndex)
{
	//参数合法性检测
	if(Count == 0 || iIndex < 0 || iIndex > g_CountNode)
	{
		printf("Node param is error!!!\n");
		return;
	}
	//头结点
	if(iIndex == 0)
	{
		//循环添加个数
		for(int i = 0 ; i< Count ;i++)
		{
			AddNodeByHead(iData);
		}
	}
	//尾结点
	else if(iIndex == g_CountNode)
	{
		//循环添加个数
		for(int i = 0; i < Count ;i++)
		{
			AddNodeByTail(iData);
		}
	}
	//中间位置
	else
	{
		struct Node *pt = g_pHead;
		for(int i = 0 ; i < iIndex ;i++)
		{
			pt = pt->pNext;
		}
		//创建新数据空间
		for(int i = 1 ;i <= Count ;i++)
		{
			struct Node *pTemp = (struct Node *)malloc(sizeof(struct Node));
			//合法性判断
			if(NULL == pTemp)
			{
				printf("malloc failed!!!\n");
				return;
			}
			//结构体成员赋值
			pTemp->iData = iData;
			pTemp->pNext = NULL;
			pTemp->pPre = NULL;
			//结点链接
			//指定位置前一个与新结点相连
			pt->pPre->pNext = pTemp;
			pTemp->pPre = pt->pPre;
			//新结点与指定位置向连
			pTemp->pNext = pt;
			pTemp->pPre = pTemp;
		}	
			g_CountNode+=Count; //结点数量增加
	}
}

//指定数据前添加结点(头添加)
void AddNodeByData(int iData,int iValue)
{
	//参数合法性检测
	if(NULL == g_pHead)
	{
		printf(" Node is Empty!!!\n");
		return ;
	}
	struct Node *pTemp = g_pHead;
	while(NULL != pTemp)
	{
		//循环查找
		if(pTemp->iData == iData)
		{
			break; //找到该结点跳出循环
		}
		pTemp = pTemp->pNext;
	}
	if(pTemp != NULL)
	{
		//头结点
		if(pTemp == g_pHead)
		{
			AddNodeByHead(iValue);
		}
		else
		{
			//中间添加
			struct Node *pt = (struct Node *)malloc(sizeof(struct Node));
			//判断是否空间合法
			if(NULL == pt)
			{
				printf("malloc failed!!!\n");
				return;
			}
			//结构体成原赋值
			pt->iData = iValue;
			pt->pPre = NULL;
			pt->pNext = NULL;
			//链接
			//当前结点的前一个与新结点相连
			pTemp->pPre->pNext = pt;
			pt->pPre = pTemp->pPre;
			//新结点与当前结点相连
			pt->pNext = pTemp;
			pTemp->pPre = pt;
			g_CountNode++; //结点数量增加
		}
	}	
}


//通过下标查找结点
struct Node *FindNodeByIndex(int iIndex)
{
	//参数合法性检测
	if(NULL == g_pHead || iIndex < 0 || iIndex > g_CountNode)
	{
		printf("Node Index is error !!!\n");
		return NULL;
	}
	//循环查找数据
	int Index = 0;
	struct Node *pTemp = g_pHead;
	while(pTemp != NULL)
	{
		if(Index == iIndex)
		{
			break;
		}
		pTemp = pTemp->pNext;
	    Index++;
	}
	return pTemp;
}


//通过数据查找结点
struct Node *FindNodeByData(int iValue)
{
	//参数合法性检测
	if(NULL == g_pHead)
	{
		printf("g_pHead is Empty!!!\n");
		return NULL;
	}
	//循环遍历查找
	struct Node *pTemp = g_pHead;
	while(NULL != pTemp)
	{
		if(pTemp->iData == iValue)
		{
			return pTemp;
		}
		pTemp = pTemp->pNext;
	}
}


//通过指定下标修改数据
void ModiNodeByIndex(int iIndex ,int iValue)
{
	//先通过下标查找到该数据 定义变量返回查找的结点数据
	struct Node *Res = FindNodeByIndex(iIndex);
	if(NULL == Res)
	{
		printf("Find Node is failed!!!\n");
		return;
	}
	else
	{
		//查找成功 进行相应下标数数据的修改
		Res->iData = iValue;
	}
}


//通过指定数据修改数据
void ModiNodeByData(int iData,int iValue)
{
	//先通过数据查找 定义变量返回查找的数据是否成功
	struct Node *Res = FindNodeByData(iData);
	if(NULL == Res)
	{
		printf("Find Node is failed!!!\n");
		return;
	}
	else
	{
		//查找成功 进行对应数据的修改
		Res->iData = iValue;
	}
}


//删除结点情况判断
void DeleteNode(struct Node *pTemp)
{
	//参数合法性jianc
	if(NULL == g_pHead)
	{
		printf("Node is Empty!!!\n");
		return;
	}
	//结点位置情况考虑
		//只有一个节点
		if(pTemp == g_pHead )
		{
			if(pTemp == g_pEnd)
			{
				free(pTemp);
				g_pHead = NULL;
				g_pEnd = NULL;
			//	g_CountNode--; //结点--
			}	
			//有多个结点
			else
			{
				//结点向下走
				pTemp = pTemp->pNext;
				free(pTemp->pPre);
				pTemp->pPre = NULL;
				//g_CountNode--;
			}
		}
		//结点为尾结点
		else if(pTemp == g_pEnd)
		{
			//尾巴前移
			pTemp = pTemp->pPre;
			//释放
			free(pTemp->pNext);
			pTemp->pNext = NULL;
			//g_CountNode--;
		}
		//为中间结点
		else
		{
			//当前结点的前一个指针当前结点的下一个
			pTemp->pPre->pNext = pTemp->pNext;
			//当前结点的下一个指向当前结点的前一个
			pTemp->pNext = pTemp->pPre;
			free(pTemp);
			//g_CountNode--;
		}
		g_CountNode--;//结点数量自减
}


//通过下标删除结点
void DeleteNodeByIndex(int iIndex)
{
	struct Node * Res = FindNodeByIndex(iIndex);
	if(Res != NULL)//成功找到该下标
	{
		DeleteNode(Res);
	}
}


//通过指定数据删除相同结点
void DeleteNodeByData(int iData)
{
	struct Node *Res = FindNodeByData(iData);
	while(Res != NULL)//成功找到该数据
	{
		DeleteNode(Res);
		//printf("%d Delete success\n",Res->iData);
	}
}


//正向打印链表
void PrintListByForward()
{
	//参数合法性检测
	if(NULL == g_pHead )
	{
		printf("g_pHead IS EMPTY ！！！\n");
		return ;
	}
	//定义临时结构体变量赋值头结点
	struct Node *pTemp = g_pHead;
	printf("current node is %d\n",g_CountNode);
	while(NULL != pTemp)
	{
		printf("%d ",pTemp->iData);
		pTemp=pTemp->pNext;
	}
	printf("\n");
}

//反向打印链表
void PrintListByBack()
{
	//参数合法性检测
	if(NULL == g_pHead)
	{
		printf("g_pHead is Empty!!!\n");
		return ;
	}
	//定义临时结构体变量赋值头结点
	struct Node *pTemp = g_pEnd;
	printf("Node Number IS %d\n",g_CountNode);
	while(NULL != pTemp)
	{
		printf("%d ",pTemp->iData);
		pTemp = pTemp->pNext;
	}
	printf("\n");
}
                                                                                           


//释放链表
void FreeList()
{
	//参数合法性检测
	if(NULL == g_pHead)
	{
		//链表为空直接返回
		return;
	}
	struct Node *pTemp = g_pHead;
	while(NULL != pTemp)
	{
		struct Node *pt = pTemp;
		pTemp = pTemp->pNext;
		free(pt);
	}
	g_pHead = NULL;
	g_pEnd = NULL;
	g_CountNode = 0;
}


//主函数
int main(void)
{
	AddNodeByHead(1);
	AddNodeByHead(2);
	AddNodeByHead(3);
	AddNodeByTail(4);
	AddNodeByTail(5);
	AddNodeByTail(6);
	PrintListByForward();
	printf("修改后数据:\n");
	ModiNodeByData(2,7);
	ModiNodeByData(6,70);
	ModiNodeByIndex(3,9);
	ModiNodeByIndex(4,19);
	PrintListByForward();
	DeleteNodeByIndex(3);
	DeleteNodeByIndex(2);
	printf("删除后数据:\n");
	PrintListByForward();
	//FreeList();
	return 0;
}

运行结果