带头双向循环链表（最6的链表结构,数据结构必看）

发布于：2022-12-19 ⋅ 阅读:(356) ⋅ 点赞:(0)

之前我介绍了单向不带头链表，相信大家在敲完链表整体代码并且刷完那十一道经典题以后，肯定已经对链表了如指掌了。并且在这过程中，大家也能感受到比起顺序表，链表还是挺方便的，但是还是有美中不足的地方，比如说，插入结点时要判断是否是头插，传参时得传二级指针等等，这些如何去解决呢？我就再为大家介绍一个超级无敌巨好用的链表——带头双向循环链表。这个链表并不常见，这是某位大佬博览群书最终得出的结果，而我今天就站在巨人的肩膀上为大家剖析一下这个链表结构。

目录

1、链表结构 

1.1 链表结构解析

1.2 结点构建

2、链表功能介绍

3、功能的实现

3.1 创建返回链表的头结点

3.2 创建一个新的结点

3.3 打印带头双向循环链表 

3.4 链表结点查找

3.5 在pos之前插入结点

3.6 删除pos位置的结点

3.7 判断链表是否为空

3.8 链表的头删

3.9 链表的尾删

3.10 链表的头插和尾插

3.11 链表长度计算

3.12 链表的销毁

4、源代码 

1、链表结构 

1.1 链表结构解析

带头——带哨兵头结点（guard结点，这个我在经典十一题里面已经介绍过了） 

 双向——一个结点结构体中包含三个成员：val（记录有效数值）、next（指向下一个结点）、prev（指向上一个结点）

循环——首尾都是相连的（看图看图看图），并且整个链表中没有NULL。

1.2 结点构建

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

这一块跟普通链表没区别，我就不赘述了。

2、链表功能介绍

功能这一块也跟链表是一样的，对数据进行增删查改。

//创建返回链表的头结点
ListNode* ListCreate();
//创建一个新的结点
ListNode* NodeCreate(LTDataType x);
//打印带头双向循环链表
void ListPrint(ListNode* guard);
//双向链表头插
void ListPushFront(ListNode* guard,LTDataType x);
//链表尾插
void ListPushBack(ListNode* guard, LTDataType x);
//判断链表是否为空
bool ListEmpty(ListNode* guard);
//链表头删
void ListPopFront(ListNode* guard);
//链表尾删
void ListPopBack(ListNode* guard);
//链表长度
size_t ListSize(ListNode* guard);
//链表查找
ListNode* NodeFind(ListNode* guard, LTDataType x);
//在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
//删除pos位置的结点
void ListErase(ListNode* pos);
//双向链表销毁
void ListDestory(ListNode* guard);

3、功能的实现

唯有实践出真知，让我们一起在实现链表功能的过程中好好体会一下，这个王者链表有多好用。

同时大家可以边学习边检查自己到底学没学会如何创建普通链表，我如果没有特别说明，就证明这个知识点肯定在普通链表中讲解过。

3.1 创建返回链表的头结点

这里需要注意一下：创建头结点的时候，因为链表中没有其它的数据，我们在初始化的时候让guard的next和prev都要指向自己，这样才是一个循环链表（如下图所示 ↓↓↓ ）

ListNode* ListCreate()
{
	struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	guard->next = guard;
	guard->prev = guard;
	return guard;
}

3.2 创建一个新的结点

在VS2019中（准确来说在更高级一点的VS中），如果你在创建结点时不检验是否malloc成功，编译的时候就会报错，所以我们为了避免代码冗长，就单独写一个函数专门去创造一个新的结点。

ListNode* NodeCreate(LTDataType x)
{
	struct ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc newnode fail");
		exit(-1);
	}
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->val = x;
	return newnode;
}

3.3 打印带头双向循环链表 

我之前说过，这个王者链表中的结点是没有NULL的，因此在判断循环是否要结束的条件应该是判断cur是否等于guard（这里有点小区别！！！）

void ListPrint(ListNode* guard)
{
	assert(guard);
	printf("guard<->");
	ListNode* cur = guard->next;
	//这种链表cur永远不可能为空
	while (cur!=guard)
	{
		printf("%d<->", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

3.4 链表结点查找

这个地方也没什么好说的。

//链表查找
ListNode* NodeFind(ListNode* guard, LTDataType x)
{
	assert(guard);
	struct ListNode* cur = guard->next;
	while (cur != guard)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

3.5 在pos之前插入结点

emmm 我为什么要先介绍这个功能呢？因为等下就要施展魔法了。

//在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	struct ListNode* prev = pos->prev;
	struct ListNode* newnode = NodeCreate(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

3.6 删除pos位置的结点

注意：这个地方很容易就搞不清谁指向谁了，我建议大家可以先定义两个结点记录pos->prev和pos->next，不然很容易就会搞错的。

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

3.7 判断链表是否为空

这个功能是新增的，主要还是为之后头删和尾删做准备，如果链表中只有哨兵结点，那么就返回true，如果还有其它结点，那么就返回false。

//判断链表是否为空
bool ListEmpty(ListNode* guard)
{
	assert(guard);
	if (guard->next == guard)
	{
		return true;
	}
	else
		return false;
}

这个代码是很多人都会想到的，但是我们可以再简化一下代码，变成：

//判断链表是否为空
bool ListEmpty(ListNode* guard)
{
	assert(guard);
	return guard->next=guard;
}

另外还要提一嘴，我们也要学会在C语言中学会bool变量，bool变量的值就是true或者false，同时我们还不要忘记在引用bool变量的时候引入头文件——#include<stdbool.h>。 

3.8 链表的头删

我们印象中常规的头删是如下代码所示，大家可能会有疑惑的地方我也用注释标注出来了：

//链表头删
void ListPopFront(ListNode* guard)
{
	assert(guard);
	//万一链表中数据为空呢
    //如果List是Empty，则返回true，！ListEmpty（guard）为0,断言就会生效
	assert(!ListEmpty(guard));
	//如果链表中除了guard就只有一个元素也没关系
	//最后guard自己指向自己
	ListNode* node = guard->next;
	ListNode* next = node->next;
	guard->next = next;
	next->prev = guard;
	free(node);
	node = NULL;//这只是在形式上改变了node，实际上是改变不了node的
}

但其实我们可以用ListErase函数实现头删和尾删，如果是头删，则把guard->next传过去，如果是尾删，我们就把guard->prev传过去，头结点和尾结点的位置都很好找（不像普通链表，我们删除的时候还要找尾tail），于是代码就可以简化如下：

//链表头删
void ListPopFront(ListNode* guard)
{
	assert(guard);
	assert(!ListEmpty(guard));
	ListErase(guard->next);
}

3.9 链表的尾删

 常规：

//链表尾删
void ListPopBack(ListNode* guard)
{
	assert(guard);
	assert(!ListEmpty(guard));
	struct ListNode* tail = guard->prev;
	struct ListNode* prev = tail->prev;
	guard->prev = prev;
	prev->next = guard;
	free(tail);
	tail = NULL;
}

简单：

//链表尾删
void ListPopBack(ListNode* guard)
{
	assert(guard);
	assert(!ListEmpty(guard));
    ListErase(guard->prev);
}

3.10 链表的头插和尾插

 头插和尾插也都可以用ListInsert函数来实现。

//双向链表头插
void ListPushFront(ListNode* guard,LTDataType x)
{
	assert(guard);
	/*ListNode* next = guard->next;
	struct ListNode* newnode = NodeCreate(x);
	guard->next = newnode;
	newnode->prev = guard;
	newnode->next = next;
	next->prev = newnode;*/
	//其实头插可以更简单
	ListInsert(guard->next,x);
}

//链表尾插
void ListPushBack(ListNode* guard, LTDataType x)
{
	assert(guard);
	/*ListNode* newnode = NodeCreate(x);
	ListNode* tail = guard->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = guard;
	guard->prev = newnode;*/
	//其实尾插可以更简单
	ListInsert(guard, x);
}

3.11 链表长度计算

//链表长度
size_t ListSize(ListNode* guard)
{
	assert(guard);
	ListNode* cur = guard->next;
	size_t size = 0;
	while (cur != guard)
	{
		size++;
		cur = cur->next;
	}
	return  size;
}

链表长度计算的原理是很简单，但是这里有人可能会有疑惑：为什么不直接把链表的长度放到哨兵结点的val里面呢？何必要用函数的返回值记录链表的长度？

因为结点的val是有类型的——LTDataType，如果LTDataType为char型，它能存储的最大数为128，如果超过了128，最后再让guard->val++就会有问题了。

3.12 链表的销毁

销毁链表有两种销毁方式，第一种就是在函数里面把guard指针置空，传参的时候传二级指针；第二种就是在函数外面把guard置空，传参的时候传一级指针。我个人建议还是选择第二种写法，这样能保证接口一致性。

//双向链表销毁
void ListDestory(ListNode* guard)
{
	assert(guard);
	//可不能一开始就把guard free掉了，不然就没有循环结束的判断条件了
	ListNode* cur = guard->next;
	while (cur!=guard)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(guard);
}

最后我们只需要在调用ListDestroy函数处，将guard置空即可。

4、源代码 

DList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

//创建返回链表的头结点
ListNode* ListCreate();
//创建一个新的结点
ListNode* NodeCreate(LTDataType x);
//打印带头双向循环链表
void ListPrint(ListNode* guard);
//双向链表头插
void ListPushFront(ListNode* guard,LTDataType x);
//链表尾插
void ListPushBack(ListNode* guard, LTDataType x);
//判断链表是否为空
bool ListEmpty(ListNode* guard);
//链表头删
void ListPopFront(ListNode* guard);
//链表尾删
void ListPopBack(ListNode* guard);
//链表长度
size_t ListSize(ListNode* guard);
//链表查找
ListNode* NodeFind(ListNode* guard, LTDataType x);
//在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
//删除pos位置的结点
void ListErase(ListNode* pos);
//双向链表销毁
void ListDestory(ListNode* guard);

DList.c

#include"DList.h"

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

//创建一个新的结点
ListNode* NodeCreate(LTDataType x)
{
	struct ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc newnode fail");
		exit(-1);
	}
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->val = x;
	return newnode;
}


//打印带头双向循环链表
void ListPrint(ListNode* guard)
{
	assert(guard);
	printf("guard<->");
	ListNode* cur = guard->next;
	//这种链表cur永远不可能为空
	while (cur!=guard)
	{
		printf("%d<->", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

//双向链表头插
void ListPushFront(ListNode* guard,LTDataType x)
{
	assert(guard);
	/*ListNode* next = guard->next;
	struct ListNode* newnode = NodeCreate(x);
	guard->next = newnode;
	newnode->prev = guard;
	newnode->next = next;
	next->prev = newnode;*/
	//其实头插可以更简单
	ListInsert(guard->next,x);
}

//链表尾插
void ListPushBack(ListNode* guard, LTDataType x)
{
	assert(guard);
	/*ListNode* newnode = NodeCreate(x);
	ListNode* tail = guard->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = guard;
	guard->prev = newnode;*/
	//其实尾插可以更简单
	ListInsert(guard, x);
}

//链表头删
void ListPopFront(ListNode* guard)
{
	assert(guard);
	//万一链表中数据为空呢
    //如果List是Empty，则返回true，！ListEmpty（guard）为0,断言就会生效
	assert(!ListEmpty(guard));
	//如果链表中除了guard就只有一个元素也没关系
	//最后guard自己指向自己
	ListNode* node = guard->next;
	ListNode* next = node->next;
	guard->next = next;
	next->prev = guard;
	free(node);
	node = NULL;//这只是在形式上改变了node，实际上是改变不了node的
	//头删也可以很简单
	/*ListErase(guard->next);*/
}

//链表尾删
void ListPopBack(ListNode* guard)
{
	assert(guard);
	assert(!ListEmpty(guard));
	struct ListNode* tail = guard->prev;
	struct ListNode* prev = tail->prev;
	guard->prev = prev;
	prev->next = guard;
	free(tail);
	tail = NULL;
	//尾删也可以更简单
	//ListErase(guard->prev);
}

//判断链表是否为空
bool ListEmpty(ListNode* guard)
{
	assert(guard);
	/*if (guard->next == guard)
	{
		return true;
	}
	else
		return false;*/
	//这个更简单,相等也就是说链表没有结点，就返回true，不相等就是链表中有节点，返回false
	return guard->next == guard;
}

//链表长度
//有人可能会疑惑，为什么不把数据存放在哨兵结点的data里面
//因为LTDataType不确定，可能是char型，可能是int型，如果是char型
//当结点数超过了128，char就达到上限了，就会出现问题
size_t ListSize(ListNode* guard)
{
	assert(guard);
	ListNode* cur = guard->next;
	size_t size = 0;
	while (cur != guard)
	{
		size++;
		cur = cur->next;
	}
	return  size;
}

//链表查找
ListNode* NodeFind(ListNode* guard, LTDataType x)
{
	assert(guard);
	struct ListNode* cur = guard->next;
	while (cur != guard)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	struct ListNode* prev = pos->prev;
	struct ListNode* newnode = NodeCreate(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

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

//可以传二级，内部置空头结点
// 建议：也可以考虑用一级指针，让调用ListDetory的人置空，保持接口的一致性
//双向链表销毁
void ListDestory(ListNode* guard)
{
	assert(guard);
	//可不能一开始就把guard free掉了，不然就没有循环结束的判断条件了
	ListNode* cur = guard->next;
	while (cur!=guard)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(guard);
}

 带头双向循环链表是链表中的最牛的存在，所以大家一定要学会这种结构的写法！

好了，今天的博客就结束了，喜欢我的文章就点个赞再走吧！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布