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

来源：叨叨游戏网

❤️‍🔥：樱花掉落的速度是五厘米那么两颗心需要多久才能靠近——《秒速五厘米》

前言

带头双向循环链表是性能非常好的线性表，它在增删查改时不需要很多其他操作，直接就可以进行，虽然实现比其他复杂，但是如果和用起来相比，那双向链表肯定是舒服的，本篇将讲述带头双向循环链表的实现。

本篇链表为双向带头循环链表，所以会用到哨兵位头节点，哨兵位头节点只会用到前（最后一个结点地址）后（第二个结点，也就是存储数据的第一个结点）结点地址，所以只存储前后结点地址，该位置的数据成员不会用到，所以可以给随机值。
哨兵位头结点最大的优势就是不需要动不动就判度是否为空这种分情况，它使得为空和不为空都能用一个代码。看完本篇你会了解到哨兵位头结点的方便。

一、创建结点的结构体

//重命名数据类型
typedef int ListNodeDate;

//创建结点的结构体并重命名
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	ListNodeDate date;
}ListNode;

二、创建新结点

每次增加结点，都需要创建一个新节点（哨兵位头节点也是这样，只不过需要特殊初始化，下面会写）。

//创建新节点
ListNode* BuyNewnode(ListNodeDate x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->date = x;
	return newnode;
}

三、初始化双向链表（创建哨兵位头节点）

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode()
{
	ListNode* phead = BuyNewnode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

四、双链表销毁

创建了链表，而且是动态开辟的，那肯定要手动释放，当我们弄完时手动释放申请的空间。

//双链表的销毁
void DestoryListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	ListNode* next = NULL;
	while (cur!=phead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

注意出函数后要让指针指向空，因为指向已经释放了，所以是野指针。因为传的是自己（一级指针），而不是自己的指针（二级指针），所以在函数里无法改变实参，只能出函数后再改变指向位置。

五、判断链表是否为空

后面删除元素我们需要先判断是否为空，如果为空（也就是只有哨兵位头结点，没有存储数据的结点），那就没有删除的必要了。

//判断双向链表是否为空（只有哨兵位头节点）
bool EmptyListNode(ListNode* phead)
{
	if (phead->next == phead)
	{
		return true;
	}
	else
		return false;
}

六、双向链表打印

//双向链表打印
void PrintListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next; 
	while (cur != phead)
	{
		if (cur == phead->next)
			printf("<=>");
		printf("%d<=>",cur->date);
		cur = cur->next;
	}
}

七、双向链表尾插

尾插很简单，直接改变尾部结点、尾插的节点、哨兵位头结点三者之间的指向关系就OK了。

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyNewnode(x);
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}

八、双向链表尾删

首先判断是否为空，然后开始删，记着释放删除结点的空间。

//双向链表尾删
void PopBackListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* newtail = phead->prev->prev;
	free(phead->prev);
	newtail->next = phead;
	phead->prev = newtail;
}

九、双向链表头插

改变哨兵位头结点、插入节点和第二个结点的指向关系。

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x)
{
	assert(phead);
	ListNode* plist = phead;
	ListNode* newnode = BuyNewnode(x);	
	newnode->next = plist->next;
	newnode->prev = plist;
	plist->next->prev = newnode;
	plist->next = newnode;
}

十、双向链表头删

首先判断是否为空，然后就是改变指向，释放删除的结点空间。

//双向链表头删
void PopFrontListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* plist = phead;
	ListNode* next = plist->next->next;
	free(plist->next);
	next->prev = plist;
	plist->next = next;
}

十一、双向链表查找

//双向链表查找
ListNode* FindListNode(ListNode* phead,ListNodeDate x)
{
	ListNode* plist = phead->next;
	assert(!EmptyListNode(plist));
	while (plist != phead)
	{
		if (plist->date == x)
			return plist;
		plist = plist->next;
	}
	return NULL;//找不到或者空链表都返回NULL
}

十二、双向链表插入

在pos位置前插入，也就是正常逻辑的插入，然后我们需要用到上面的那个查找函数，先查找出想要插入的位置，然后插入。

//双向链表在pos前面插入
void InsertListNode(ListNode* phead,ListNodeDate x, ListNode* pos)
{
	assert(phead);
	assert(pos);
	ListNode* ListPrev = pos->prev;
	ListNode* newnode = BuyNewnode(x);
	ListPrev->next = newnode;
	newnode->prev = ListPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

十三、双向链表删除

删除并释放某个数据所对应的结点，首先需要判断是否为空链表，如果只有哨兵位头结点肯定不能删，所以需要判断是否为空链表。

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos);
	assert(!EmptyListNode(phead));
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);//让pos出函数后置空。
}

十五、总代码

ListNode.h

ListNode.h

#pragma once

//带头双向循环链表

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

//重命名数据类型
typedef int ListNodeDate;

//创建结点的结构体并重命名
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	ListNodeDate date;
}ListNode;

//创建新节点
ListNode* BuyNewnode(ListNodeDate x);

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode();

//双链表的销毁
void DestoryListNode(ListNode* phead);

//双向链表打印
void PrintListNode(ListNode* phead);

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x);

//双向链表尾删
void PopBackListNode(ListNode* phead);

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x);

//双向链表头删
void PopFrontListNode(ListNode* phead);

//双向链表查找
ListNode* FindListNode(ListNode* phead, ListNodeDate x);

//双向链表在pos前面插入
void InsertListNode(ListNode* phead, ListNodeDate x, ListNode* pos);

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos);

ListNode.c

ListNode.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "ListNode.h"

//创建新节点
ListNode* BuyNewnode(ListNodeDate x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->date = x;
	return newnode;
}

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode()
{
	ListNode* phead = BuyNewnode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

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

//判断双向链表是否为空（只有哨兵位头节点）
bool EmptyListNode(ListNode* phead)
{
	if (phead->next == phead)
	{
		return true;
	}
	else
		return false;
}

//双向链表打印
void PrintListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next; 
	while (cur != phead)
	{
		if (cur == phead->next)
			printf("<=>");
		printf("%d<=>",cur->date);
		cur = cur->next;
	}
}

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyNewnode(x);
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}

//双向链表尾删
void PopBackListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* newtail = phead->prev->prev;
	free(phead->prev);
	newtail->next = phead;
	phead->prev = newtail;
}

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x)
{
	assert(phead);
	ListNode* plist = phead;
	ListNode* newnode = BuyNewnode(x);	
	newnode->next = plist->next;
	newnode->prev = plist;
	plist->next->prev = newnode;
	plist->next = newnode;
}

//双向链表头删
void PopFrontListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* plist = phead;
	ListNode* next = plist->next->next;
	free(plist->next);
	next->prev = plist;
	plist->next = next;
}

//双向链表查找
ListNode* FindListNode(ListNode* phead,ListNodeDate x)
{
	ListNode* plist = phead->next;
	assert(!EmptyListNode(plist));
	while (plist != phead)
	{
		if (plist->date == x)
			return plist;
		plist = plist->next;
	}
	return NULL;//找不到或者空链表都返回NULL
}

//双向链表在pos前面插入
void InsertListNode(ListNode* phead,ListNodeDate x, ListNode* pos)
{
	assert(phead);
	assert(pos);
	ListNode* ListPrev = pos->prev;
	ListNode* newnode = BuyNewnode(x);
	ListPrev->next = newnode;
	newnode->prev = ListPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos);
	assert(!EmptyListNode(phead));
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);//让pos出函数后置空。
}

Test.c

Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "ListNode.h"

int main()
{
	//创建哨兵位头节点
	ListNode* plist = InitListNode();//pointer List

	//尾插尾删打印
	//PushBackListNode(plist, 0);
	//PushBackListNode(plist, 1);
	//PushBackListNode(plist, 2);
	//PushBackListNode(plist, 3);
	//PushBackListNode(plist, 4);
	//PopBackListNode(plist);
	//PopBackListNode(plist);
	//PopBackListNode(plist);
	//PrintListNode(plist);
	//头插头删打印
	//PushFrontListNode(plist, 0);
	//PushFrontListNode(plist, 1);
	//PushFrontListNode(plist, 2);
	//PushFrontListNode(plist, 3);
	//PushFrontListNode(plist, 4);
	//PopFrontListNode(plist);
	//PrintListNode(plist);

	//综合验证
	PushBackListNode(plist, 0);
	PushBackListNode(plist, 1);
	PushBackListNode(plist, 2);
	PushFrontListNode(plist, 3);
	PushFrontListNode(plist, 4);
	PushFrontListNode(plist, 5);
	PopBackListNode(plist);
	PopFrontListNode(plist);
	
	//插入
	ListNode* pos = FindListNode(plist,0);
	InsertListNode(plist, 10, pos);

	//删除
	pos = FindListNode(plist, 10);
	EraseListNode(plist,pos);
	pos = NULL;

	PrintListNode(plist);
	DestoryListNode(plist);
	plist = NULL;
	return 0;
}

十四、总结

结尾

博主长期更新，博主的目标是不断提升阅读体验和内容质量，如果你喜欢博主的文章，请点个赞或者关注博主支持一波，我会更加努力的为你呈现精彩的内容。

🌈专栏推荐

更新不易，希望得到友友的三连支持一波。收藏这篇文章，意味着你将永久拥有它，无论何时何地，都可以立即找到重新阅读；关注博主，意味着无论何时何地，博主将永久和你一起学习进步，为你带来有价值的内容。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部频道

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

前言

一、创建结点的结构体

二、创建新结点

三、初始化双向链表（创建哨兵位头节点）

四、双链表销毁

五、判断链表是否为空

六、双向链表打印

七、双向链表尾插

八、双向链表尾删

九、双向链表头插

十、双向链表头删

十一、双向链表查找

十二、双向链表插入

十三、双向链表删除

十五、总代码

ListNode.h

ListNode.c

Test.c

十四、总结