[数据结构]~双向+循环链表从(0~1）

 前言

作者：小蜗牛向前冲

名言：我可以接收失败，但我不能接收放弃

 如果觉的博主的文章还不错的话，还。请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

目录

一  认识带头双向循环链表

二实现带头双向循环链表

三实现List.h

四 实现List.c

1 初始化链表

2 申请新的节点

3 尾插

4 头插

5 头删和尾插

​编辑 6 求链表长度

 7 查找pos,在pos位置实现插入和删除、

8 销毁链表

 五 链表和顺序表的对比

我们知道对于链表来说是有八种类型，但是我们在实际过程中最常用的二种结构：

无头单向非循环链表

带头双向循环链表

其中在上篇博客我们已经了解过无头单向非循环链表是怎么实现的，下面我们继续来实现带头双向循环链表。

一  认识带头双向循环链表

 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。

二实现带头双向循环链表

在实现带头双向循环链表过程中，我们要特别注意分文件，完成链表功能的实现。

下面我们分为三个文件实现：

1 SList.h

在该文件中我们完成，单表的类型定义，接口函数的声明，引用的头文件。

2 SList.c

完成双向链表表接口函数的实现

3 Test.c

主函数，测试顺序表各接口的功能 

下面我们分文件为大家讲解

三实现List.h

#pragma once
 
#include
#include
#include
#include
 
//带头的双向+循环的链表
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
 
//初始化链表
LTNode* ListInit();
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//头插
void ListPushFront(LTNode* phead, LTDataType x);
//打印
void ListPrint(LTNode* phead);
//尾删
void ListPopBack(LTNode* phead);
//头删
void ListPopFront(LTNode* phead);
//求链表长度
size_t ListSize(LTNode* phead);
//查找
LTNode* ListFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(LTNode* pos);
//销毁
void ListDestory(LTNode* phead);

 在这个文件，我们要特别注意对双向循环链表结构体的定义，他不同于单链表仅仅只有一个指针。

//带头的双向+循环的链表
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

prev指针指向前一个节点

next指向下个节点

四 实现List.c

在这里我们要完成各类函数功能的实现.

实现我们要先实现对链表的初始化

1 初始化链表

//初始化链表
LTNode* ListInit()
{
	//为哨兵头申请一个空间
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	//判断申请空间是否成功
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);//申请失败，直接结束程序
	}
	//开始时哨兵头和尾都指向guard
	guard->next = guard;
	guard->prev = guard;
	return guard;

在这里我们注意区于单链表初始化时，我们要实现一个哨兵位的头节点 ，这个节点在初始时指向它自身构成循环。

我们有对链表的初始化，那我们为了能够插入数据还应该能够申请新的节点空间。

2 申请新的节点

LTNode* BuySLTNode(LTDataType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	if (newNode == NULL)
	{
		perror("maalloc fail");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

对于这个新节点来说，我们要注意的是在下面如何讲链表中节点连接起来构成循环。

 下面我们来实现链表的尾插

3 尾插

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	//申请新的节点
	LTNode* newNode = BuySLTNode(x);
	LTNode* tail = phead->prev;//尾指针
	//老节点的尾与和新节的头进行双向连接
	tail->next = newNode;
	newNode->prev = tail;
	//哨兵位的头与和新节的尾进行双向连接
	newNode->next = phead;
	phead->prev = newNode;
}

对于单链表的尾插来说，带头双向循环链的尾插简单许多，因为我们这里就不要在判断链表我否为NULL和找尾这二件事情了。

4 头插

这里的头插和尾插一样简单，实现过程我们来看代码。

//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	//申请新的节点
	LTNode* newNode = BuySLTNode(x);
	newNode->next = cur;
	cur->prev = newNode;
	phead->next = newNode;
	newNode->prev = phead;
}

为了更好从测试头插和尾插，我们还要实现对链表的打印。

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

在单链表中我们是通过直接遍历链表，从而打印。但是我们怎么就会遇到一个问题，但指针向最后一个节点时，又会回到phead节点处，这样就会出现死循环的情况，那么我们可以从存储数据的第1个节点开始遍历，指向phead时结束。

下面我们来测试函数的功能是否能够实现。

 可以看到是实现了的，那么我们就可以继续实现下个函数的功能，要养成每写写完一个函数的功能我们都应该去跑一下，看能否实现，这样我们在代码出现问题的时就能快速定位快速解决。

5 头删和尾插

尾删

//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));//链表不为空
	LTNode* tail = phead->prev;//尾指针
	LTNode*prev = tail->prev;//指向前一个节点
	//重新连接节点之间的关系
	prev->next = phead;
	phead->prev = prev;
	free(tail);
}

这里我们要这注意，在删除时，我们要判断链表是否存有数据，没有就不能删除，避免出现野指针。 

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

这里我们有个函数来实现即可。 

头删

//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));//链表不为空
	LTNode* cur = phead->next;
	LTNode* tail = cur->next;
	tail->prev = phead;
	phead->next = tail;
	free(cur);
}

下面我们继续来测试函数的功能：

 6 求链表长度

//求链表长度
size_t ListSize(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	size_t len = 0;
	while (cur != phead)
	{
		++len;
		cur = cur->next;
	}
	return len;
}

 有时候我们需要知道链表有多长，所以我们写个函数来实现它

测试

 7 查找pos,在pos位置实现插入和删除、

查找

//查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

当找到了就返回指向X的指针，没有就返回NULL

在pos之前插入

//在pos之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//申请新的节点
	LTNode* newNode = BuySLTNode(x);
	LTNode* first = pos;//指向pos节点
	LTNode* second = pos->prev;//指向pos的前一个节点
	first->prev = newNode;
	newNode->next = first;
	second->next = newNode;
	newNode->prev = second;
}

 这里只要注意链接关系就不会有大的问题。

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

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* first = pos->next;//指向pos下个节点
	LTNode* second = pos->prev;//指向pos的前一个节点
	first->prev = second;
	second->next = first;
	free(pos);//删除pos
}

其实这里的写法多样，但我推荐用本文中的写法，这样可以避免因为链接顺序有问题而出错。

测试

 最后实现链表的销毁

8 销毁链表

//销毁
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* des = phead->next;
	while (des != phead)
	{
		LTNode* cur = des->next;
		free(des);
		des = cur;
	}
	free(phead);
}

这里我们要注意：这里的销毁头节点的空间，但phead其实仍然是指向这里的，所以我们在销毁后，要手动将链表置空。

测试

 五 链表和顺序表的对比

下面我们对链表和顺序表对比一下：