【链表】双向带头循环链表的实现（代码附详细注释）

✨ 写在前面

 哈喽大家好
 作为一个初入编程的大学生，知识浅薄
 写文章的同时也是在巩固自己，同时希望我的文章对你有所帮助！

 我的其他文章
       1.【数据结构】时间复杂度&&空间复杂度
       2.【数据结构】顺序表接口实现及详解
       3.【数据结构】带你手撕单链表！
       4.【链表经典面试题 】-环形链表

 初入编程的世界 前方"路漫漫"️ 每天我们都要进步一点点
 希望分享知识的同时可以和你们一起进步

文章目录

• 前言
• 链表结构&&各种接口的声明
• 接口函数的实现
• • 初始化函数
  • 打印链表
  • 创建新节点
  • 尾插
  • 头插
  • 尾删
  • 头删
  • 找到某一个元素并返回下标
  • 在某个位置之前插入元素
  • 删除pos位置的节点
  • 插入和删除节点的复用问题
  • • 头插
    • 尾插
    • 头删
    • 尾删
  •  链表销毁
• 总结
• 源代码
• Dlist.h
• Dlist.c
• test.c

前言

之前我们已经学习了单链表，单链表也叫做：单向不循环链表

• 链表的结构中没有带哨兵卫的头节点
• 并且每一个节点中有一个指针可以找到下一个节点的位置
  如图所示：

那么什么是双向带头循环链表呢？

• 首先带头 是带有哨兵卫的头节点
• 然后循环链表 是每一个节点不仅有next可以找到下一个节点
  还有prev找到上一个节点，最后一个节点和头节点链接起来 形成了循环

如图：

可以看到这种链表的结构还是比较复杂的，但是虽然结构比较复杂，但是，在实际使用中这种结构会带来很多优势，比如:

• 不需要遍历找尾节点
• 随时可以找到每个节点的上一个节点
• 不用考虑链表是否为空

具体的我们在结构实现的时候就知道了！

链表结构&&各种接口的声明

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)

#include
#include
#include
#include
//定义链表的结构
typedef int DLDataType;
typedef struct DListNode {

	struct DListNode* prev;
	struct DListNode* next;
	DLDataType val;
}DListNode;


//初始化链表---不需要参数（返回开辟的节点）
DListNode* DListNodeInit();
//打印链表
void DListNodePrint(DListNode* phead);

//尾插
void DListNodePushBack(DListNode* phead,DLDataType x);

//头插
void DListNodePushFront(DListNode* phead, DLDataType x);

//尾删
void DListNodePopBack(DListNode* phead);

//头删

void DListNodePopFront(DListNode* phead);

//查找
DListNode* DListNodeFind(DListNode* phead, DLDataType x);

//插入

void DListNodeInsert(DListNode* pos,DLDataType x);

//删除
 
void DListNodeErase(DListNode* pos);

//链表的判断为空

//链表的销毁

void DlistNodeDestory(DListNode* phead);

接口函数的实现 初始化函数

注意双向带头循环链表的初始化是和之前不一样的:
我们首先需要malloc一个哨兵卫头节点phead（不存储有效数据）
phead里面有一个指向下一个节点的指针next 和一个指向前一个节点的指针prev
而因为是循环 这个头节点的next和prev都要指向phead自己
然后返回我们开辟的这个节点就可以了

如图:

代码：

//链表初始化
DListNode* DListNodeInit()
{
	
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	assert(head);
	//头结点的前后指针都指向自己
	head->prev = head;
	head->next = head;

	return head;
}

打印链表

• 利用cur遍历去遍历链表
• cur的初始值是phead的next（哨兵卫的下一个节点才是有效节点，哨兵只是站岗的！）
• 结束条件与之前不一样 不能等于NULL 由于是循环链表 所以不会有NULL，而什么时候遍历结束呢？如果cur走到了尾节点 那么下一个就是phead 所以 结束条件自然就是：cur等于phead

代码：

//打印链表
void DListNodePrint(DListNode* phead)
{
	assert(phead);
	//打印链表和单链表不一样 
	//这里循环的判断条件是：cur不等于head
	DListNode* cur = phead->next;//cur从头节点的下一个开始
	while (cur != phead)
	{
		printf("%d  ", cur->val);
		cur = cur->next;
	}
	printf("n");
}

创建新节点

我们可能需要频繁地malloc新的节点，因此我们封装成一个函数

//创建新节点
DListNode* BuyNewNode(DLDataType x)
{
	
	//开辟一个新节点
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	//检查是否开辟成功
	assert(newnode);
	//开辟的新节点初始化为NULL,值初始化为X
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

尾插

• 双向循环链表尾插比单链表简单多了
• 首先我们直接可以用头节点找到尾 :phead->prev
• 然后只需要把 原来的尾tail 和 新节点 newnode 链接起来
• 最后newnode作为新的尾–>把newnode和phead链接起来

画图分析：

代码：

//由于有带哨兵卫的头节点 所以不需要传递二级指针
void DListNodePushBack(DListNode* phead, DLDataType x)
{
	//尾插的话直接在后面进行链接
	DListNode* newnode = BuyNewNode(x);
	//找到尾
	DListNode* tail = phead->prev;
	//尾的下一个为newnode
	tail->next = newnode;
	//newnode的前一个等于tail
	newnode->prev = tail;
	//newnode的下一个为头（phead)
	newnode->next = phead;
	//更新尾
	tail = newnode;
	//头部指向新的尾
	phead->prev = tail;

头插

• 头插我们需要先找到真正有效的头节点head=phead->next
• 然后把新节点newnode插入到phead和head的之间，这样newnode就作为了新的有效头节点

如图所示

代码：

void DListNodePushFront(DListNode* phead, DLDataType x)
{
	DListNode* newnode = BuyNewNode(x);
	//头插，也就是需要插入到head 的后面
	DListNode* next = phead->next;

	//phead newnode next 这三个链接起来就可以了
	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = next;
	next->prev = newnode;

	
}

尾删

• 首先需要找到尾tail 和 尾的前一个prevTail
• 然后 让prevPos与phead连接起来
• 释放掉原来的尾就可以了

如图所示：

代码：

void DListNodePopBack(DListNode* phead)
{
	//如果phead的next就是他自己 说明实际上的链表已经空了
	//只有这个哨兵卫了
	assert(phead->next!=phead);

	//先找到尾
	DListNode* tail = phead->prev;
	//找到尾的前一个
	DListNode* preTail = tail->prev;
	//preTail作为新的尾
	phead->prev = preTail;
	preTail->next = phead;
	//释放掉原来的尾
	free(tail);
}

头删

• 对于头删，也就是把phead的下一个节点删除
• 我们把phead的下一个节点标记为head 然后只需要让head的next充当新的head就可以了
• 不要忘了free掉原来的head!

话不多说，上图：

代码

void DListNodePopFront(DListNode* phead)
{
	//如果有效节点为空的话 警告一下
	assert(phead->next != phead);

	//先找到真正的头
	DListNode* head = phead->next;
	//真正的头的下一个 
	DListNode* next = head->next;
	// 把 phead和新头连接起来
	phead->next = next;
	next->prev = phead;
	//释放原来的头
	free(head);
}

找到某一个元素并返回下标

• 老套路，找元素不就是遍历嘛
• 但是这里需要注意的是：用临时遍历cur遍历的结束条件不再是cur等于NULL了
• 而是cur！=phead，因为尾节点的后面就是哨兵卫头节点！

如图分析：

这里比较简单，直接上代码！

//查找
DListNode* DListNodeFind(DListNode* phead, DLDataType x)
{
	DListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	printf("找不到 %d n",x);
	return NULL;
	
}

在某个位置之前插入元素

• 这里我们需要和上面的查找某个元素结合使用
• 利用找到的节点的地址pos 来进行pos前面的插入

我们只需要找到pos的前一个位置prevPos，和开辟一个newnode
然后把prevPos newnode pos 连接起来就可以了

代码：

//(pos位置之前） 插入
//这里不用传递phead了
void DListNodeInsert(DListNode* pos,DLDataType x)
{

	//如果找不到目标的x 也就是pos为空的时候 断言一下
	assert(pos);
	DListNode* newnode = BuyNewNode(x);

	DListNode* posPrev = pos->prev;
	// 然后把 prev newnode  pos 链接起来就可以了
	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;

	//如果链表只有一个有效节点
	// 那么posPrev 和 posNext都是 phead ----> 符合最初的情况 满足！



}

删除pos位置的节点

这个应该是最简单的
为啥？
我们要删除 pos位置的节点，只需要把pos的前一个位置和后一个位置连接起来就可以了，中间的pos位置free到
（因为我们这是双向循环链表，所以可以找得到节点的前一个和后一个，自然十分简单！）

是不是十分简单！
代码：

//指定位置删除 也不需要传递phead了 因为如果找不到pos 那么断言直接出去了
void DListNodeErase(DListNode* pos)
{
	//删除指定位置 如果pos找不到 那么直接断言报错就可以了！
	assert(pos);
	//找到pos位置的前一个和后一个 链接起来
	DListNode* prevPos = pos->prev;
	DListNode* nextPos = pos->next;

	prevPos->next = nextPos;
	nextPos->prev = prevPos;
	//把pos节点给free掉
	free(pos);


}
}

插入和删除节点的复用问题

我们既然写出了任意位置pos的删除和插入
那么可不可以 直接复用Insert和Erase函数 实现头删尾删，头插尾插的复用呢？
毕竟头插头删，尾插尾删 不就是pos取的特殊位置嘛？？

头插

那么要删除的位置pos就是phead->next
比较简单 看代码把（代码有详细注释的）

void DListNodePushFront(DListNode* phead, DLDataType x)
{
	assert(phead);
	//phead 和 phead的下一个之间插入节点 新节点作为新的有效头
	DListNodeInsert(phead->next, x);

}

尾插

尾插 那么我们定义的插入函数是在pos位置之前插入
尾插是想在尾节点的后面插入
因为这是循环链表，尾节点的后一个就是哨兵卫头节点phead
所以pos就是phead

代码：

/
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	assert(head);
	//头结点的前后指针都指向自己
	head->prev = head;
	head->next = head;

	return head;
}
//打印链表
void DListNodePrint(DListNode* phead)
{
	assert(phead);
	//打印链表和单链表不一样 
	//这里循环的判断条件是：cur不等于head
	DListNode* cur = phead->next;//cur从头节点的下一个开始
	while (cur != phead)
	{
		printf("%d  ", cur->val);
		cur = cur->next;
	}
	printf("n");
}

//创建新节点
DListNode* BuyNewNode(DLDataType x)
{
	
	//开辟一个新节点
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	//检查是否开辟成功
	assert(newnode);
	//开辟的新节点初始化为NULL,值初始化为X
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//尾插
// 
//由于有带哨兵卫的头节点 所以不需要传递二级指针
 

/




void DListNodePushFront(DListNode* phead, DLDataType x)
{
	assert(phead);
	//phead 和 phead的下一个之间插入节点 新节点作为新的有效头
	DListNodeInsert(phead->next, x);

}

// 利用一个函数判断是否还有有效节点！
bool DListNodeEmpty(DListNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//尾删

//尾删 复用！
void DListNodePopBack(DListNode* phead)
{
	assert(phead);
	//尾删 那么尾部就是 phead的prev
	//检查 是不是只有哨兵卫一个节点
	assert(!(DListNodeEmpty(phead)));

	DListNodeErase(phead->prev);

}

//头删


//头删的复用Erase

void DListNodePopFront(DListNode* phead)
{
	assert(phead);

	//既然是头删 就需要检查 是否还有有效的节点？
	
	//assert(phead->next !=phead);
	assert(!DListNodeEmpty(phead));

	//如果还有有效节点，那么就删除第一个有效节点 pos就是phead->next
	//如果没有有效节点了，phead->next就是哨兵卫头节点了 这个不需要删除！
	DListNodeErase(phead->next);

}
//查找
DListNode* DListNodeFind(DListNode* phead, DLDataType x)
{
	assert(phead);
	DListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	printf("找不到 %d n",x);
	return NULL;
	
}

//统计链表节点个数
//1. 利用一个包含DListNode的结构体：DListNode* phead 和 int size
//   注意不可以使用 哨兵卫头节点中的val来记录size  因为链表的数据类型不一定是 int类型 char类型->最多存127 容易溢出 double就更不用说了！
// 2. 利用一个全局变量 size记录
int DListNodeCount(DListNode* phead)
{
	assert(phead);
	DListNode* cur = phead->next;
	int size = 0;
	while (cur!=phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

//(pos位置之前） 插入
//这里不用传递phead了
void DListNodeInsert(DListNode* pos,DLDataType x)
{

	//如果找不到目标的x 也就是pos为空的时候 断言一下
	assert(pos);
	DListNode* newnode = BuyNewNode(x);

	DListNode* posPrev = pos->prev;
	// 然后把 prev newnode  pos 链接起来就可以了
	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;

	//如果链表只有一个有效节点
	// 那么posPrev 和 posNext都是 phead ----> 符合最初的情况 满足！



}

//指定位置删除 也不需要传递phead了 因为如果找不到pos 那么断言直接出去了
void DListNodeErase(DListNode* pos)
{
	//删除指定位置 如果pos找不到 那么直接断言报错就可以了！
	assert(pos);
	//找到pos位置的前一个和后一个 链接起来
	DListNode* prevPos = pos->prev;
	DListNode* nextPos = pos->next;

	prevPos->next = nextPos;
	nextPos->prev = prevPos;
	//把pos节点给free掉
	free(pos);


}

//链表的销毁
void DlistNodeDestory(DListNode* phead)
{
	assert(phead);
	//遍历 把每一个节点都利用erase删除

	DListNode* cur = phead->next;
	while (cur!=phead)
	{
		DListNode* next = cur->next;
		DListNodeErase(cur);
		cur = next;
	}
	//最后要把头节点Phead释放掉
	free(phead);
	phead = NULL;//这一句加不加都可以，因为调用完函数之后 这个形参phead会被操作系统回收 又会变成随机值！
	// 这里最好在 函数的外面置空，否则如果继续使用实参指针，可能会出现野指针问题！
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include"DList.h"


void test1()
{
	DListNode* Dlist = NULL;
	Dlist=DListNodeInit();

	//尾插
	printf("插入数据t");
	DListNodePushBack(Dlist, 1);
	DListNodePushBack(Dlist, 2);
	DListNodePushBack(Dlist, 3);
	DListNodePushBack(Dlist, 4);
	DListNodePrint(Dlist);

	//头插
	printf("头插12345t");
	DListNodePushFront(Dlist, 5);
	DListNodePushFront(Dlist, 4);
	DListNodePushFront(Dlist, 3);
	DListNodePushFront(Dlist, 2);
	DListNodePushFront(Dlist, 1);
	DListNodePrint(Dlist);


	//尾删
	printf("尾删t");
	DListNodePopBack(Dlist);
	DListNodePopBack(Dlist);
	DListNodePopBack(Dlist);
	DListNodePrint(Dlist);

	//头删
	printf("头删t");
	DListNodePopFront(Dlist);
	DListNodePopFront(Dlist);
	DListNodePrint(Dlist);

	//找到5 插入50
	printf("5的前面插入50t");
	DListNode* pos = DListNodeFind(Dlist, 5);
	DListNodeInsert(pos,50);
	DListNodePrint(Dlist);

	//找到50 删除50
	printf("删除50t");
	pos = DListNodeFind(Dlist, 50);
	DListNodeErase(pos);
	DListNodePrint(Dlist);

	DListNodePopBack(Dlist);
	DListNodePrint(Dlist);

	DListNodePopBack(Dlist);
	DListNodePrint(Dlist);

	DListNodePopBack(Dlist);
	DListNodePrint(Dlist);

	DListNodePopBack(Dlist);
	DListNodePrint(Dlist);

	DlistNodeDestory(Dlist);
	Dlist = NULL;

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

     感谢阅读哦 给个赞把~~