数据结构-双向循环链表

1个月前发布

双向循环链表和双向链表相比，可以直接从首结点找到尾结点，不需要再通过遍历来查找尾结点了，方便数据的增删，降低了程序的时间复杂度，其在插入删除的时候不需要定义太多的变量，减少了程序的空间复杂度。

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

创建一个头结点

//构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleCriLinkedList
{
	DataType_t  		     data; //结点的数据域
	struct DoubleCriLinkedList	*prev; //直接前驱的指针域
	struct DoubleCriLinkedList	*next; //直接后继的指针域

}DoubleCriLList_t;

创建双向循环空链表

//创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
DoubleCriLList_t * DoubleCriLList_Create(void)
{
	//1.创建一个头结点并对头结点申请内存
	DoubleCriLList_t *Head = (DoubleCriLList_t *)calloc(1,sizeof(DoubleCriLList_t));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	//2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL
	Head->prev = Head;
	Head->next = Head;

	//3.把头结点的地址返回即可
	return Head;
}

创建新结点

//创建新的结点，并对新结点进行初始化（数据域 + 指针域）


DoubleCriLList_t * DoubleCriLList_NewNode(DataType_t data)
{
	//1.创建一个新结点并对新结点申请内存
	DoubleCriLList_t *New = (DoubleCriLList_t *)calloc(1,sizeof(DoubleCriLList_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	//2.对新结点的数据域和指针域（2个）进行初始化
	New->data = data;
	New->prev = New;
	New->next = New;

	return New;
}

在链表头部插入元素

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

}

在链表尾部插入

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

在链表指定元素后边插入

bool DoubleCriLList_DestInsert(DoubleCriLList_t * Head,DataType_t destval,DataType_t data)
{
	DoubleCriLList_t * Phead = Head->next;
	//创建新结点
	DoubleCriLList_t * New= DoubleCriLList_NewNode(data);
	//判断新结点创建是否成功
	if(NULL == New){
		printf("DestInsert create new node failed\n ");
		return false;
	}
	//链表为空
	if(Head->next == Head){
		Head->next = New;
		New->next = New;
		New->prev = New;
		return true;
	}
	//循环遍历查找目标结点 在中间的情况
	while(Phead->next != Head->next){
		if(Phead->data == destval){
			New->next = Phead->next;
			New->prev = Phead;
			Phead->next->prev = New;
			Phead->next = New;
			return true;
		}
		Phead = Phead->next;
	}
	//尾结点是目标结点时
	if(Phead->data == destval){
		New->prev = Head->next->prev;
		Head->next->prev->next = New;
		New->next = Head->next;
		Head->next->prev = New;
	}
	return true;
}

在链表头部删除元素

bool DoubleCriLList_HeadDel(DoubleCriLList_t * Head)
{
	DoubleCriLList_t * Phead = Head->next;
	//判断链表是否为空
	if(Head->next == Head){
		printf("this is empty list,do not delete head\n");
		return false;
	}
	//只有头首结点时
	if(Head->next->next == Head->next){
		Head->next->next = NULL;
		Head->next->prev = NULL;
		free(Head->next);
		Head->next = Head;
	}
	else{
		Head->next->prev->next = Head->next->next;
		Head->next->next->prev = Head->next->prev;
		Head->next = Head->next->next;
		Phead->next = NULL;
		Phead->prev = NULL;
		free(Phead);
	}
	return true;

}

在链表尾部删除元素

bool DoubleCriLList_TailDel(DoubleCriLList_t * Head)
{
	DoubleCriLList_t * Phead = Head->next->prev;//记录尾结点
	//判断链表是否为空
	if(Head->next == Head){
		printf("this is empty list,do not delete tail\n");
		return false;
	}
	//只有头首结点时
	if(Head->next->next == Head->next){
		Head->next->next = NULL;
		Head->next->prev = NULL;
		free(Head->next);
		Head->next = Head;
	}
	else{
		Phead->prev->next = Head->next;//Head->next->prev->prev->next = Head->next;
		Head->next->prev = Phead->prev;//Head->next->prev = Head->next->prev->prev;
		Phead->prev = NULL;
		Phead->next = NULL;
		free(Phead);
	}
	return true;

}

删除指定元素

bool DoubleCriLList_DestDel(DoubleCriLList_t * Head,DataType_t destval)
{
	DoubleCriLList_t * Phead = Head->next;
	//判断链表是否为空
	if(Head->next == Head){
		printf("this is empty list,do not delete tail\n");
		return false;
	}
	//只有头首结点,首结点为目标结点时
	if(Head->next->next == Head->next && Phead->data == destval){
		Head->next->next = NULL;
		Head->next->prev = NULL;
		free(Head->next);
		Head->next = Head;
	}
	//目标元素在首结点
	else if(Phead->data == destval){
		Head->next->prev->next = Head->next->next;
		Head->next->next->prev = Head->next->prev;
		Head->next = Head->next->next;
		Phead->next = NULL;
		Phead->prev = NULL;
		free(Phead);
	}
	else{
		//目标元素在中间时
		while(Phead->next != Head->next){
			if(Phead->data == destval){
				Phead->next->prev = Phead->prev;
				Phead->prev->next = Phead->next;
				Phead->next = NULL;
				Phead->prev = NULL;
				free(Phead);
				return true;
			}
			Phead = Phead->next;
		}
	}
	//目标元素在尾结点
	if(Phead->data == destval){
		Phead->prev->next = Head->next;//Head->next->prev->prev->next = Head->next;
		Head->next->prev = Phead->prev;//Head->next->prev = Head->next->prev->prev;
		Phead->prev = NULL;
		Phead->next = NULL;
		free(Phead);
	}
	else if(Phead->data != destval){
		printf("do not find this value\n");
	}
	return true;
}

循环遍历打印链表

bool DoubleCriLList_Print(DoubleCriLList_t * Head)
{
	DoubleCriLList_t * Phead = Head;
	//判断链表是否为空
	if(Head->next == Head){
		printf("this is empty DoubleCriList\n");
		return false;
	}
	//循环遍历链表
	while(Phead->next)
	{
		//把头结点的直接后继作为新的头结点
		Phead = Phead->next;

		//输出头结点的直接后继的数据域
		printf("data = %d\n",Phead->data);

		//判断是否到达尾结点，尾结点的next指针是指向首结点的地址
		if (Phead->next == Head->next)
		{
			break;
		}	
	}

	return true;
}

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

评分

欢迎为Ta评分