带头双向循环链表：一种高效的数据结构

• 💓 博客主页：江池俊的博客
• ⏩ 收录专栏：数据结构探索
• 👉专栏推荐：✅cpolar ✅C语言进阶之路
• 💻代码仓库：江池俊的代码仓库
• 🔥编译环境：Visual Studio 2022
• 🎉欢迎大家点赞👍评论📝收藏⭐

双向循环链表是一种复杂的数据结构，它结合了双向链表和循环链表的优点。与单向链表相比，双向链表可以双向遍历，而循环链表则可以在尾部链接到头部，形成一个闭环。这种数据结构在某些应用场景下非常有用，比如事件处理、图形界面、内存管理等。

一、带头循环双向链表的概念及结构

双向循环链表是一种特殊类型的链表，它由一系列节点组成，每个节点包含一个数据域和两个指针域。其中一个指针指向下一个节点，另一个指针指向前一个节点。在双向循环链表中，首节点的前一个节点是尾节点，尾节点的下一个节点是首节点，形成一个闭环。

二、使用带头双向循环链表的优势及注意事项

【优势】：

1. 高效遍历：由于带头双向循环链表可以双向遍历，因此可以在O(1)时间内访问任何节点。
2. 内存高效：与双向链表相比，带头双向循环链表不需要额外的内存来存储头部节点。
3. 插入和删除操作高效：在带头双向循环链表中插入和删除节点时，只需调整指针即可，无需移动大量数据。

【注意事项】：

1. 初始化：在创建带头双向循环链表时，需要正确初始化所有节点的指针。
2. 异常处理：在进行插入、删除等操作时，需要处理指针异常情况，如空指针或无效指针。
3. 内存管理：在使用带头双向循环链表时，需要正确管理内存，避免内存泄漏或野指针。

三、带头双向链表的创建

✨3.1 准备工作✨

将代码分成三个文件可以提高代码的可读性、可维护性和可重用性。具体来说，三个文件可以分别关注以下方面：

1. 配置文件：用于存储应用程序的配置信息，如数据库连接信息、应用程序名称、应用程序版本等。该文件可以在应用程序的整个生命周期内进行维护和管理，并且可以轻松地与其他开发人员共享。
2. 模块文件：用于存储应用程序的各个模块，如用户管理、订单管理、产品管理等。每个模块都可以单独维护和测试，并且可以在不同的应用程序中重复使用。这有助于降低代码冗余和提高代码的可重用性。
3. 入口文件：用于定义应用程序的入口，如路由、请求处理等。该文件可以控制应用程序的整个流程，并且可以轻松地与其他开发人员共享。

通过将代码分成三个文件，可以更好地组织代码结构，使其更加清晰和易于维护。同时，这也使得代码更易于测试和调试，并且可以更好地支持代码重构和优化。

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data; //节点存储的数据元素
	struct ListNode* next; //指向前驱节点
	struct ListNode* prev; //指向后继节点
}ListNode; //双链表结构

//几大接口
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

✨3.2 创建返回链表的头结点✨

动态申请一个节点作为双向链表的头节点。并将头节点的 prev 指向自己，next也指向自己，表明这是一个双向链表，且链表为空。

// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	if (head == NULL)
	{
		perror("ListCreate --> malloc");
		return;
	}
	head->data = -1;
	head->prev = head;
	head->next = head;
	return head;
}

✨3.3 双向链表销毁✨

从链表的第二个节点开始，逐个释放链表中的节点，直到回到头节点并释放头节点的内存空间。这样做可以确保链表中的所有节点都被正确释放，防止内存泄漏。

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next; 
	}
	free(pHead);
	printf("双链表销毁成功！\n");
}

✨3.4 双向链表打印✨

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	printf("哨兵位 <--> ");
	while (cur != pHead)
	{
		printf("%d <--> ", cur->data);
		cur = cur->next;
	}
	printf("哨兵位\n");
}

✨3.5 双向链表尾插✨

在进行插入节点之前，无论是头插还是尾插都需要申请一个新的节点，于是可以把此步骤成一个函数，减少代码的冗余。

//申请一个节点
ListNode* CreateLTNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("CreateLTNode --> malloc");
		return;
	}

	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

1. 首先，创建一个新的节点newnode，并将数据x存储在其中。
2. 将newnode的prev指针指向当前链表的第一个节点pHead的前一个节点，即pHead->prev。
3. 将newnode的next指针指向当前链表的第一个节点pHead。
4. 将当前链表的第一个节点pHead的前一个节点的next指针指向新节点newnode。
5. 将当前链表的第一个节点pHead的prev指针指向新节点newnode。

通过以上步骤，新节点被插入到双向链表的尾部，并且链表中的其他节点仍然保持其原始顺序和链接关系。这样做可以确保新节点被正确地添加到链表中，并且不会破坏链表的结构。

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = CreateLTNode(x);

	//pHead           pHead->prev  newnode
	newnode->prev = pHead->prev; 
	newnode->next = pHead;
	pHead->prev->next = newnode;
	pHead->prev = newnode;
}

✨3.6 双向链表尾删✨

1. 首先，获取链表的最后一个节点tail，它应该是头节点pHead的前一个节点（即pHead->prev）。
2. 接着，获取最后一个节点的前一个节点tailPrev。
3. 将头节点pHead的prev指针指向最后一个节点的前一个节点tailPrev，从而将最后一个节点从链表中间删除。
4. 将最后一个节点的前一个节点的next指针指向头节点pHead，从而将头节点和最后一个节点连接起来。
5. 最后，释放最后一个节点的内存空间。

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next!=pHead);//链表不能为空

	ListNode* tail = pHead->prev;
	ListNode* tailPrev = tail->prev;
	// pHead     tailPrev tail
	pHead->prev = tailPrev;
	tailPrev->next = pHead;

	free(tail);
}

✨3.7 双向链表头插✨

1. 首先，创建一个新的节点newnode，并将数据x存储在其中。
2. 将新节点的prev指针指向当前链表的第一个节点pHead。
3. 将新节点的next指针指向当前链表的第一个节点的下一个节点，即pHead->next。
4. 将当前链表的第一个节点的next指针指向新节点newnode。
5. 将当前链表的第一个节点的下一个节点的prev指针指向新节点newnode。

通过以上步骤，新节点被插入到双向链表的头部，并且链表中的其他节点仍然保持其原始顺序和链接关系。这样做可以确保新节点被正确地添加到链表中，并且不会破坏链表的结构。

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = CreateLTNode(x);

	ListNode* rear = pHead->next;
	pHead->next = newnode;
	newnode->prev = pHead;
	newnode->next = rear;
	rear->prev = newnode;
}

✨3.8 双向链表头删✨

1. 首先，获取链表的第一个节点cur，它应该是头节点pHead的下一个节点（即pHead->next）。
2. 将头节点的next指针指向第一个节点的下一个节点，从而将第一个节点从链表中间删除。
3. 将第一个节点的下一个节点的prev指针指向头节点pHead，从而将头节点和第一个节点连接起来。
4. 最后，释放第一个节点的内存空间。

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);

	ListNode* cur = pHead->next;
	pHead->next = cur->next;
	cur->next->prev = pHead;

	free(cur);
}

✨3.9 双向链表查找✨

1. 首先，从链表的第二个节点开始（即pHead->next），遍历链表的每个节点。
2. 对于每个节点，检查其存储的数据是否与要查找的数据x相等。
3. 如果找到了匹配的节点，则返回该节点。
4. 如果遍历完整个链表都没有找到匹配的节点，则返回空指针（NULL）。

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//如果没找到，返回空
}

✨3.10 双向链表在pos的前面进行插入✨

1. 首先，创建一个新的节点newnode，并将数据x存储在其中。
2. 获取要插入位置的前一个节点_prev。
3. 将前一个节点的next指针指向新节点newnode。
4. 将新节点的prev指针指向前一个节点_prev。
5. 将新节点的next指针指向当前节点pos。
6. 将当前节点的prev指针指向新节点newnode。

通过以上步骤，新节点被插入到指定位置的前面，并且链表中的其他节点仍然保持其原始顺序和链接关系。这样做可以确保新节点被正确地添加到链表中，并且不会破坏链表的结构。

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = CreateLTNode(x);
	ListNode* _prev = pos->prev;

	// _prev newnode pos
	_prev->next = newnode;
	newnode->prev = _prev;
	newnode->next = pos;
	pos->prev = newnode;
}

✨3.11 双向链表删除pos位置的节点✨

1. 首先，确保要删除的节点pos不是空指针。
2. 获取要删除节点的前一个节点_prev和后一个节点rear。
3. 将前一个节点的next指针指向后一个节点，从而将要删除的节点从链表中间删除。
4. 将后一个节点的prev指针指向前一个节点，从而将前一个节点和后一个节点连接起来。
5. 释放要删除的节点的内存空间。

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* _prev = pos->prev;
	ListNode* rear = pos->next;

	_prev->next = rear;
	rear->prev = _prev;

	free(pos);
}

四、源代码

🌅4.1 List.h 文件

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data; //节点存储的数据元素
	struct ListNode* next; //指向前驱节点
	struct ListNode* prev; //指向后继节点
}ListNode; //双链表结构

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

🌅4.2 List.c 文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

//申请一个节点
ListNode* CreateLTNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("CreateLTNode --> malloc");
		return;
	}

	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}
// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	if (head == NULL)
	{
		perror("ListCreate --> malloc");
		return;
	}
	head->data = -1;
	head->prev = head;
	head->next = head;
	return head;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next; 
	}
	free(pHead);
	printf("双链表销毁成功！\n");
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	printf("哨兵位 <--> ");
	while (cur != pHead)
	{
		printf("%d <--> ", cur->data);
		cur = cur->next;
	}
	printf("哨兵位\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = CreateLTNode(x);

	//pHead           pHead->prev  newnode
	newnode->prev = pHead->prev; 
	newnode->next = pHead;
	pHead->prev->next = newnode;
	pHead->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next!=pHead);//链表不能为空

	ListNode* tail = pHead->prev;
	ListNode* tailPrev = tail->prev;
	// pHead     tailPrev tail
	pHead->prev = tailPrev;
	tailPrev->next = pHead;

	free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = CreateLTNode(x);

	ListNode* rear = pHead->next;
	pHead->next = newnode;
	newnode->prev = pHead;
	newnode->next = rear;
	rear->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);

	ListNode* cur = pHead->next;
	pHead->next = cur->next;
	cur->next->prev = pHead;

	free(cur);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//如果没找到，返回空
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = CreateLTNode(x);
	ListNode* _prev = pos->prev;

	// _prev newnode pos
	_prev->next = newnode;
	newnode->prev = _prev;
	newnode->next = pos;
	pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* _prev = pos->prev;
	ListNode* rear = pos->next;

	_prev->next = rear;
	rear->prev = _prev;

	free(pos);
}

🌅4.3 Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "List.h"


void Test1()
{
	ListNode* plist = ListCreate();
	//尾插1、2、3
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPrint(plist);
	//头插5、4
	ListPushFront(plist, 5);
	ListPushFront(plist, 4);
	ListPrint(plist);
	//查找元素3，找到返回节点地址，没找到返回空
	ListNode* pos = ListFind(plist, 3);
	if (pos)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}
	//在3前面插入30
	ListInsert(pos, 30);
	ListPrint(plist); 
	//删除3
	if (pos)
	{
		ListErase(pos);
		pos = NULL;
	}
	ListPrint(plist);
	//尾删两次
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	//头删两次
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	//销毁链表
	ListDestory(plist);
	plist = NULL;
}


int main()
{
	Test1();
	return 0;
}

🌅4.4 测试结果

文章来源地址https://www.toymoban.com/news/detail-754373.html

到了这里，关于带头双向循环链表：一种高效的数据结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！