数据结构-双向链表

1个月前发布

单向链表只能找它的直接后继，而不能找到直接前驱，而双向链表不仅能找到直接后继，而且也能找到直接前驱

/*******************************************************************************
*
*
* 设计双向链表的接口
* author：jindouliu2024@163.com 
* date：2025.3.29
* 
*
* Copyright (c)  2024-2025   jindouliu2024@163.com   All right Reserved
* *******************************************************************************/

配置双向链表的头首节点

typedef struct DoubleLinkedList
{
	DataType_t  		     data; //结点的数据域
	struct DoubleLinkedList	*prev; //直接前驱的指针域
	struct DoubleLinkedList	*next; //直接后继的指针域

}DoubleLList_t;

创建一个空的链表

//创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
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;
}

创建一个新的结点


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;
}

头插结点

bool DoubleLList_HeadInsert(DoubleLList_t * Head,DataType_t data)
{
	//创建新结点
	DoubleLList_t * New= DoubleLList_NewNode(data);
	//判断新结点创建是否成功
	if(NULL == New){
		printf("HeadInsert create new node failed\n ");
		return false;
	}
	//判断链表是否为空
	if(Head->next == NULL){
		Head->next = New;
		
		return true;
	}
	New->next = Head->next;
	Head->next->prev = New;
	Head->next = New;
	return true;

}

尾插结点

bool DoubleLList_TailInsert(DoubleLList_t * Head,DataType_t data)
{
	DoubleLList_t * Phead = Head;
	//创建新结点
	DoubleLList_t * New= DoubleLList_NewNode(data);
	//判断新结点创建是否成功
	if(NULL == New){
		printf("HeadInsert create new node failed\n ");
		return false;
	}
	//判断链表是否为空
	if(Head->next == NULL){
		Head->next = New;
		return true;
	}
	//遍历找到尾结点
	while(Phead->next != NULL){
		Phead = Phead->next;
	}
	Phead->next = New;
	New->prev = Phead;
	return true;
}

指定目标结点后边插入

bool DoubleLList_DestInsert(DoubleLList_t * Head,DataType_t destval,DataType_t data)
{
	DoubleLList_t * Phead = Head->next;
	//创建新结点
	DoubleLList_t * New= DoubleLList_NewNode(data);
	//判断新结点创建是否成功
	if(NULL == New){
		printf("HeadInsert create new node failed\n ");
		return false;
	}
	//判断链表是否为空
	if(Head->next == NULL){
		Head->next = New;
		return true;
	}
	//循环找到目标结点
	while(Phead->next != NULL && Phead->data != destval){
		Phead = Phead->next;
	}
	//如果目标不是尾结点
	if(Phead->next == NULL && Phead->data != destval){
		printf("do not find destval\n");
		return false;
	}
	//如果目标是尾结点
	if(Phead->next == NULL && Phead->data == destval){
		Phead->next = New;
		New->prev = Phead;
	}
	else{
	New->next = Phead->next;
	Phead->next->prev = New;
	New->prev = Phead;
	Phead->next = New;
	}
	return true;

}

头删结点

bool DoubleLList_HeadDel(DoubleLList_t * Head)
{
	DoubleLList_t * Phead = Head->next;
	//判断链表是否为空
	if(Head->next == NULL){
		printf("this is empty list,do not delete head\n");
		return false;
	}
	Head->next = Phead->next;
	Phead->next = NULL;
	Head->next->prev = NULL;
	free(Phead);
	return true;

}

尾删结点

bool DoubleLList_TailDel(DoubleLList_t * Head)
{
	DoubleLList_t * Phead = Head->next;
	//判断链表是否为空
	if(Head->next == NULL){
		printf("this is empty list,do not delete head\n");
		return false;
	}
	//遍历找到尾结点
	while(Phead->next != NULL){
		Phead = Phead->next;
	}	
	Phead->prev->next = NULL;
	Phead->prev = NULL;
	free(Phead);
	return true;
}

指定目标结点删除

bool DoubleLList_DestDel(DoubleLList_t * Head,DataType_t destval)
{
	DoubleLList_t * Phead = Head->next;
	//判断链表是否为空
	if(Head->next == NULL){
		printf("this is empty list,do not delete head\n");
		return false;
	}
	//循环遍历查找目标元素
	while(Phead->next != NULL && Phead->data != destval){
		Phead = Phead->next;
	}
	//查找到链表尾部，还没有找到destval，则直接退出
	if(Phead->next == NULL && Phead->data != destval){
		printf("can not find this destval,do not delete\n");
		return false;
	}
	//只有头结点和首节点
	if(Head->next->next == NULL && Head->next->data == destval)
	{
		Head->next = NULL;
		Phead->prev = NULL;
		free(Phead);
	}
	//最后一个结点是目标结点
	else if(Phead->next == NULL && Phead->data == destval){
		Phead->prev->next = NULL;
		Phead->prev = NULL;
		free(Phead);
		//return true;
	}
	//目标结点在首结点
	else if(Head->next == Phead){
		Head->next = Phead->next;
		Phead->next = NULL;
		Head->next->prev = NULL;
		free(Phead);
		//return true;
	}
	//目标结点不在首尾结点
	else{
		Phead->prev->next = Phead->next;
	 	Phead->next->prev = Phead->prev;
		Phead->next = NULL;
	 	Phead->prev = NULL;
		free(Phead);
	}
	 // Phead->prev->next = Phead->next;
	 // Phead->next->prev = Phead->prev;
	 // Phead->next = NULL;
	 // Phead->prev = NULL;
	 // free(Phead);
	 return true;
}

循环打印

bool DoubleLList_Print(DoubleLList_t * Head)
{
	DoubleLList_t * Phead = Head;
	//判断链表是否为空
	if(Head->next == NULL){
		printf("this is empty DoubleList\n");
		return false;
	}
	//循环遍历链表
	while(Phead != NULL){
		Phead = Phead->next;
		printf("data = %d\n",Phead->data);
		if(Phead->next == NULL){
			break;
		}
		
	}
	return true;
}

来源链接：https://www.cnblogs.com/lradian/p/18804582

评分

欢迎为Ta评分