开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> C语言描述数据结构 —— 带头双向循环链表 -> 正文阅读

[数据结构与算法]C语言描述数据结构 —— 带头双向循环链表

1.链表的多种组合

链表的形态有很多，有不带头单向不循环链表、不带头单向循环链表、不带头双向不循环链表……那么带头或不带头、单向或双向、循环或不循环，能够组合成多种链表。其中最简单的链表是不带头单向不循环链表，最复杂的结构就是带头双向循环链表。当然我们也不要被复杂的结构而吓到，事实上带头双向循环链表的结构复杂，但是实现起来却是非常容易的。

2.带头双向循环链表的结构

我们在描述单链表时提到过哨兵卫的概念，这个哨兵卫就是链表的头，也就是说，带头的链表我们不需要单独定义一个指针用来存储头结点的地址，当然传参的时候也不需要使用二级指针了。

再次强调一点，哨兵卫是不存储任何有效数据的，链表的长度也不行。因为如果链表要存储的数据类型为 char 类型，当链表的长度超过 128 后，那么就会发生错误。

带头双向循环链表的各个结点有两个指针，分别为 prev 和 next，前者指向上一个结点，后者指向下一个结点。

3.带头双向循环链表的实现

3.1链表结点的声明

typedef int ListData;
typedef struct ListNode
{
	ListData val;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

3.2链表初始化

//链表初始化
ListNode* ListInit()
{
	ListNode* guard = (ListNode*)calloc(1, sizeof(ListNode));
	assert(guard);
	guard->prev = guard;
	guard->next = guard;
	return guard;
}

我们使用的带头的链表，所以我们只需要得到哨兵卫的地址就能操作链表。

3.3尾插和建立新结点

//建立新结点
static ListNode* CreateNode(ListData x)
{
	ListNode* node = (ListNode*)calloc(1, sizeof(ListNode));
	assert(node);
	node->prev = node;
	node->next = node;
	node->val = x;
	return node;
}
//尾插
void ListPushBack(ListNode* phead, ListData x)
{
	assert(phead);
	ListNode* newnode = CreateNode(x);
	ListNode* tail = phead->prev;
	phead->prev = newnode;
	newnode->next = phead;
	newnode->prev = tail;
	tail->next = newnode;
}

尾插的逻辑非常结点，我们不需要像单链表那样去遍历找尾结点或者单独一个存放尾结点地址的指针，可以看到我们的代码找尾结点只有简短的一句代码。事实上我们只需要理清逻辑关系，并且合理改变指针指向即可实现尾插的功能。

3.4链表的打印

//打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	printf("phead<->");
	while (cur != phead)
	{
		printf("%d<->", cur->val);
		cur = cur->next;
	}
	printf("phead\n");
}

我们需要注意的是，带头双向循环链表是没有空指针的，那么什么时候停止遍历链表呢？我们需要捋清楚一个逻辑关系，那就是链表的头在哪。??

3.4头插

//头插
void ListPushHead(ListNode* phead, ListData x)
{
	assert(phead);
	ListNode* newnode = CreatrNode(x);

	//这种写法需要注意链接顺序
	/*newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;*/

	//这种写法不需要刻意在意链接顺序
	ListNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

?头插的原理也非常简单，只需要找到链表的头结点即可。然后建立适当的链接关系。

?3.5判空

//判空 
bool ListEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

我们一定要注意，链表为空的情况下不是某个结点的next指针指向空，而是next指针指向了哨兵卫。

3.6尾删

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;
	phead->prev = prev;
	prev->next = phead;
	free(tail);
}

尾删的逻辑也非常的简单，我们不需要像单链表那样去遍历链表从而找到尾结点，在这个链表里面，我们仅用两句代码就找到了尾结点和倒数第二个结点，然后从新建立链接关系，即可达到尾删的效果。

3.7头删

//头删
void ListPopHead(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	ListNode* cur = phead->next;
	ListNode* next = cur->next;
	phead->next = next;
	next->prev = phead;
	free(cur);
}

?3.8查找

//查找
ListNode* ListFind(ListNode* phead, ListData x)
{
	assert(phead);
	assert(!ListEmpty(phead));
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
			return cur;
		cur = cur->next;
	}
}

查找的逻辑就非常简单了，我们不需要太多复杂的算法，只需要遍历一遍链表即可。即使链表的长度有几千或几万，但是对于计算机来说，每秒可以进行几亿次甚至几十亿次的运算，那么效率的损失是微乎其微的。

3.9在pos位置之前插入

//在pos位置之前插入
void ListInsert(ListNode* pos, ListData x)
{
	assert(pos);
	ListNode* newnode = CreateNode(x);
	ListNode* prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

在这里有一个问题，如果链表只存在哨兵卫，那么此时还能插入结点吗？当然可以，并且相当于尾插。根据这个原理，我们就可以复用代码，即将头插、尾插的代码做出调整。

//尾插
void ListPushBack(ListNode* phead, ListData x)
{
	assert(phead);
	//ListNode* newnode = CreateNode(x);
	//ListNode* tail = phead->prev;
	//phead->prev = newnode;
	//newnode->next = phead;
	//newnode->prev = tail;
	//tail->next = newnode;

	ListInsert(phead, x);
}

//头插
void ListPushHead(ListNode* phead, ListData x)
{
	assert(phead);
	ListNode* newnode = CreateNode(x);

	//这种写法需要注意链接顺序
	/*newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;*/

	//这种写法不需要刻意在意链接顺序
	/*ListNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;*/

	ListInsert(phead->next, x);
}

3.10删除pos位置的结点

//删除pos位置的结点
void ListErase(ListNode* pos)
{
	assert(pos);
	assert(!ListEmpty(pos));
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

这段代码的逻辑关系也非常简单，具体如图：

与上面一样，这段代码也可以复用，即将头删、尾删的代码做出调整。

//头删
void ListPopHead(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	//ListNode* cur = phead->next;
	//ListNode* next = cur->next;
	//phead->next = next;
	//next->prev = phead;
	//free(cur);

	ListErase(phead->next);
}

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	/*ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;
	phead->prev = prev;
	prev->next = phead;
	free(tail);*/

	ListErase(phead->prev);
}

3.11统计链表的结点个数

//结点个数
size_t ListSize(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	ListNode* cur = phead->next;
	size_t size = 0;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

3.12销毁链表

//销毁链表
void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* del = cur;
		cur = cur->next;
		free(del);
	}
	free(phead);
}

4.完整代码

4.1 List.h 头文件

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <stdbool.h>
typedef int ListData;
typedef struct ListNode
{
	ListData val;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

ListNode* ListInit();//链表初始化
void ListPushBack(ListNode* phead, ListData x);//尾插
void ListPushHead(ListNode* phead, ListData x);//头插
void ListPopBack(ListNode* phead);//尾删
void ListPopHead(ListNode* phead);//头删
ListNode* ListFind(ListNode* phead, ListData x);//查找
void ListInsert(ListNode* pos, ListData x);//在pos插入
void ListErase(ListNode* pos);//删除pos位置的结点
size_t ListSize(ListNode* phead);//统计结点个数
bool ListEmpty(ListNode* phead); // 判空
void ListPrint(ListNode* phead);//打印
void ListDestroy(ListNode* phead);

4.2 List.c 源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

//链表初始化
ListNode* ListInit()
{
	ListNode* guard = (ListNode*)calloc(1, sizeof(ListNode));
	assert(guard);
	guard->prev = guard;
	guard->next = guard;
	return guard;
}
//建立新结点
static ListNode* CreateNode(ListData x)
{
	ListNode* node = (ListNode*)calloc(1, sizeof(ListNode));
	assert(node);
	node->prev = node;
	node->next = node;
	node->val = x;
	return node;
}
//尾插
void ListPushBack(ListNode* phead, ListData x)
{
	assert(phead);
	//ListNode* newnode = CreateNode(x);
	//ListNode* tail = phead->prev;
	//phead->prev = newnode;
	//newnode->next = phead;
	//newnode->prev = tail;
	//tail->next = newnode;

	ListInsert(phead, x);
}
//打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	printf("phead<->");
	while (cur != phead)
	{
		printf("%d<->", cur->val);
		cur = cur->next;
	}
	printf("phead\n");
}
//头插
void ListPushHead(ListNode* phead, ListData x)
{
	assert(phead);
	ListNode* newnode = CreateNode(x);

	//这种写法需要注意链接顺序
	/*newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;*/

	//这种写法不需要刻意在意链接顺序
	/*ListNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;*/

	ListInsert(phead->next, x);
}
//判空 
bool ListEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	/*ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;
	phead->prev = prev;
	prev->next = phead;
	free(tail);*/

	ListErase(phead->prev);
}
//头删
void ListPopHead(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	//ListNode* cur = phead->next;
	//ListNode* next = cur->next;
	//phead->next = next;
	//next->prev = phead;
	//free(cur);

	ListErase(phead->next);
}
//查找
ListNode* ListFind(ListNode* phead, ListData x)
{
	assert(phead);
	assert(!ListEmpty(phead));
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
			return cur;
		cur = cur->next;
	}
}
//在pos位置之前插入
void ListInsert(ListNode* pos, ListData x)
{
	assert(pos);
	ListNode* newnode = CreateNode(x);
	ListNode* prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
//删除pos位置的结点
void ListErase(ListNode* pos)
{
	assert(pos);
	assert(!ListEmpty(pos));
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}
//结点个数
size_t ListSize(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	ListNode* cur = phead->next;
	size_t size = 0;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
//销毁链表
void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* del = cur;
		cur = cur->next;
		free(del);
	}
	free(phead);
}

4.3 test.c 源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"


void TestList()
{
	ListNode* plist = ListInit();
	//头插
	ListPushHead(plist, 10);
	ListPushHead(plist, 20);
	ListPushHead(plist, 30);
	//尾插
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPrint(plist);

	//在pos位置之前插入
	ListInsert(ListFind(plist, 10), 100);
	ListInsert(ListFind(plist, 20), 200);
	ListPrint(plist);

	printf("%u\n", ListSize(plist));//打印结点个数

	//尾删
	ListPopBack(plist);
	ListPopBack(plist);
	//头删
	ListPopHead(plist);
	ListPopHead(plist);
	ListPrint(plist);

	//销毁链表
	ListDestroy(plist);
}
int main()
{
	TestList();
	return 0;
}