数据结构——带头双向循环链表

目录

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

二、带头双向循环链表的增删查改接口实现

（1）创建新节点

（2）创建链表头节点

（3）链表销毁

（4）链表打印

（5）头部插入节点

（6）尾部插入节点

（7）头部删除节点

（8）尾部删除节点

（9）链表查找

（10）在pos前面插入节点

（11）删除pos位置节点

---

在上篇文章中，我们介绍了链表的概念、结构、分类和单链表的增删查改接口的实现，同时提到了带头双向循环链表这一结构。本篇文章中，我们来详细的学习带头双向循环链表和它的增删查改接口实现。

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

前文提到过，带头双向循环链表结构最复杂，一般用来单独存储数据。实际中使用的链表结构都是带头双向循环链表。另外，这个结构虽然复杂，但是会带来很多优势，后面我们进行增删查改接口实现的时候就会感受到这个结构的方便所在了。

带头，即链表中带哨兵位。哨兵位属于附加的链表节点，本身不存储有效数值，仅作为头节点用来简化边界条件和方便操作。如果一个链表带哨兵位（带头）的话，第一个元素就应该是链表的第二个节点。

双向和循环很好理解，看图即可。接下来我们直接开始进行增删查改接口的实现。

二、带头双向循环链表的增删查改接口实现

此次演示使用的是vs2019，我们先创建一个新工程，并新建一个头文件"DCList.h"和两个源文件"DCList.c"和"Test.c"，当然命名可以根据自己喜好，它们的具体作用为：

• DCList.h：带头双向循环链表的结构体定义，头文件的引用和接口函数的声明
• DCList.c：接口函数的实现
• Test.c：测试各个函数

首先我们展示"DCList.h"的完整代码，不要忘记在两个源文件中引用"DCList.h"

#pragma once//防止头文件被二次引用

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

typedef int LTDataType;//如果要修改存储的数据类型可直接在此修改

typedef struct ListNode
{
	struct ListNode* next; //指向后一个节点
	struct ListNode* prev; //指向前一个节点
	LTDataType data; //节点中存储的数据
}ListNode;

//带头双向循环链表增删查改接口实现

ListNode* ListCreate();//创建链表头节点

ListNode* CreateNewNode(LTDataType x);//创建新节点

void DListDestory(ListNode* plist);//链表销毁

void DListPrint(ListNode* plist);//链表打印

void DLTPushFront(ListNode* plist, LTDataType x);//头部插入节点

void DLTPushBack(ListNode* plist, LTDataType x);//尾部插入节点

void DLTPopFront(ListNode* plist);//头部删除节点

void DLTPopBack(ListNode* plist);//尾部删除节点

ListNode* DListFind(ListNode* plist, LTDataType x);//链表查找

void DListInsert(ListNode* pos, LTDataType x);//在pos前面插入节点

void DListErase(ListNode* pos);//删除pos位置节点

接下来我们逐步实现各个接口函数，每一步都进行注释说明，必须让你学会

（1）创建新节点

ListNode* CreateNewNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); //创建新节点
	if (newnode == NULL) //防止空间开辟失败
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x; //初始化新节点数据
	newnode->next = NULL;
	newnode->prev = NULL; //初始化新节点中的指针变量
	return newnode; //返回新节点地址
}

（2）创建链表头节点

ListNode* ListCreate()
{
	ListNode* phead = CreateNewNode(-1); //创建哨兵位
	phead->next = phead; //这里要形成循环，所以next和prev都要指向自己
	phead->prev = phead;
	return phead; //返回哨兵位地址
}

（3）链表销毁

void DListDestory(ListNode* plist)
{
	assert(plist); //断言，防止传入空指针
	ListNode* cur = plist->next; //后面的循环判断条件要用到哨兵位，所以要从第二个节点开始
	while (cur != plist) //当cur在链表中又循环回哨兵位时，说明链表销毁完毕
	{
		ListNode* next = cur->next; //保存cur的下一个节点地址
		free(cur); //销毁cur
		cur = next; //更新cur
	}
	free(plist); //最后销毁哨兵位
}

（4）链表打印

void DListPrint(ListNode* plist)
{
	assert(plist); //断言，防止传入空指针
	printf("head"); //打印哨兵位
	ListNode* cur = plist->next; //链表不为空的话跳过哨兵位
	if (cur != plist) //判断链表中是否只有哨兵位
	{
		while (cur != plist) //当cur在链表中又循环回哨兵位时，说明链表打印完毕
		{
			printf("<==>%d", cur->data); //打印节点数据
			cur = cur->next; //找到下一个节点
		}
	}
	printf("<==>"); //最后打印这个代表循环(当然你可以改成别的)
}

（5）头部插入节点

void DLTPushFront(ListNode* plist, LTDataType x)
{
	assert(plist); //断言，防止传入空指针
	ListNode* newnode = CreateNewNode(x); //创建新节点
	ListNode* first = plist->next; //新建一个指针指向原来的头节点，增强代码可读性(可选)
	newnode->next = first;
	first->prev = newnode; //这两步将新节点链接至原来的头节点前面
	newnode->prev = plist;
	plist->next = newnode; //这两步将新节点链接至哨兵位后面
}

测试一下

（6）尾部插入节点

void DLTPushBack(ListNode* plist, LTDataType x)
{
	assert(plist); //断言，防止传入空指针
	ListNode* newnode = CreateNewNode(x); //创建新节点
	ListNode* tail = plist->prev; //找到尾节点
	tail->next = newnode; 
	newnode->prev = tail; //这两步将新节点链接至原来的尾节点后面
	plist->prev = newnode;
	newnode->next = plist; //这两步将新节点链接至哨兵位前面(循环)
}

测试一下

（7）头部删除节点

void DLTPopFront(ListNode* plist)
{
	assert(plist); //断言，防止传入空指针
	assert(plist->next != plist); //断言，防止链表为空(只有哨兵位)
	ListNode* first = plist->next; //保存头节点地址
	ListNode* second = first->next; //保存第二个节点地址
	plist->next = second;
	second->prev = plist; //这两步将哨兵位和第二个节点链接
	free(first); //释放头节点
}

测试一下

（8）尾部删除节点

void DLTPopBack(ListNode* plist)
{
	assert(plist); //断言，防止传入空指针
	assert(plist->next != plist); //断言，防止链表为空(只有哨兵位)
	ListNode* tmp = plist->prev; //保存尾节点地址
	plist->prev = tmp->prev;
	tmp->prev->next = plist; //这两步将哨兵位和尾节点的上一个节点链接
	free(tmp); //释放尾节点
}

测试一下

（9）链表查找

ListNode* DListFind(ListNode* plist, LTDataType x)
{
	assert(plist); //断言，防止传入空指针
	ListNode* cur = plist->next; //查找前跳过哨兵位
	while (cur != plist) //判断，如果链表为空(只有哨兵位)则无法进入循环
	{
		if (cur->data == x) //如果找到目标数据
		{
			return cur; //返回目标节点地址
		}
		cur = cur->next; //迭代
	}
	return NULL; //链表为空或没找到则返回NULL
}

（10）在pos前面插入节点

void DListInsert(ListNode* pos, LTDataType x)
{
	assert(pos); //断言，防止传入空指针
	ListNode* newnode = CreateNewNode(x); //创建新节点
	ListNode* posprev = pos->prev; //保存pos的上一个节点地址
	newnode->prev = posprev; 
	posprev->next = newnode; //这两步将新节点链接到pos的上一个节点后面
	newnode->next = pos;
	pos->prev = newnode; //这两步将新节点链接到pos前面
}

测试一下

（11）删除pos位置节点

void DListErase(ListNode* pos)
{
	assert(pos); //断言，防止传入空指针
	assert(pos->next != pos); //断言，防止传入空链表的哨兵位
	ListNode* posprev = pos->prev; //保存pos的上一个节点地址
	ListNode* posnext = pos->next; //保存pos的下一个节点地址
	posprev->next = posnext;
	posnext->prev = posprev; //这两步将二者链接
	free(pos); //释放pos
}

测试一下

这里的代码有个缺陷，由于链表的结构原因，如果链表非空，我们无法判断pos是否是哨兵位。所以当我们传入非空链表的哨兵位时程序仍能运行，但一般来说我们并不希望删除链表的哨兵位。如果想解决这个问题，可以选择增加一个参数来输入哨兵位的地址进行判断，或者寻找更好的解决方法。

至于为什么free之后不将pos置空，是因为我们的参数是一个一级指针，而置空是要修改pos指针的内容。如果想在函数内部置空则需要传入二级指针。

完.

PS：最近也是到期末了，更新速度慢了很多😭希望本文对各位能有所帮助，如果有写错说错的地方欢迎评论区指出😊