hello！这里是敲代码的小董，很荣幸您阅读此文，期待您的评论指点和关注，欢迎欢迎~~

✨✨个人主页：敲代码的小董

💗💗系列专栏：数据结构

没学单链表的先去学单链表！！！

目录

一、引言

1.链表的重要地位

2.带头双向循环链表的独特魅力

二、基础概念详解 

1.节点结构剖析

2.链表整体结构

三、核心操作原理 

1.初始化链表

2.插入节点

2.1 尾插

2.2 头插

2.3 在pos位置之前插入一个值

3.删除节点

3.1 尾删

3.2 头删

3.3 在pos位置删除

4.打印链表

5.查找节点

6.销毁链表

四、完整代码

1.List.h

2.List.c

---

一、引言

1.链表的重要地位

链表之所以占据重要地位，要点如下：

• 突破数组连续存储局限，可按需灵活分配内存，实现数据动态管理。
• 插入、删除操作高效，适应频繁变动的数据集合场景。
• 广泛应用于操作系统、编译器、图形界面软件等众多领域，像操作系统进程调度信息维护、编译器符号表构建、图形界面菜单组件管理等都离不开它。

2.带头双向循环链表的独特魅力

带头双向循环链表具有诸多独特魅力：

• 双向遍历便捷性：既可以轻松地从表头正向遍历至表尾，也能迅速从表尾反向遍历至表头，为数据查找、对比等操作提供双向通路，极大提升操作灵活性，例如在一些需要频繁前后对比相邻元素的算法场景中优势尽显。

• 循环特性优势：链表形成闭环，不存在普通链表的尾节点特殊处理情况，任何节点都能作为操作起始点，代码实现上逻辑更统一，像在实现环形缓冲区、循环任务调度器等功能时能无缝贴合需求。

• 头节点简化操作：作为固定的 “锚点”，头节点不存放实际数据却让链表初始化、插入删除操作的边界处理得以简化，减少代码的复杂分支判断，降低出错概率，让程序结构更加清晰易维护。

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

二、基础概念详解 

1.节点结构剖析

数据域：这是链表节点的核心存储区域，用于存放节点所代表的实际数据元素，可以是整数、字符串、结构体等各种数据类型。

前驱指针：指向当前节点的前一个节点，在双向链表结构里起着关键作用。通过前驱指针，能够轻松回溯到前序节点，实现反向遍历。当需要查找当前节点的前一相邻元素，或者在删除、插入节点操作涉及调整前序节点关联时，前驱指针提供了直接的访问路径。

后继指针：与前驱指针相对应，它指向当前节点的后一个节点，是链表实现顺序遍历的基础。从表头开始，顺着后继指针一路前行，便能依次访问链表中的每一个节点，完成诸如数据输出、搜索特定元素等正向操作任务。

2.链表整体结构

        带头双向循环链表整体呈现出一个闭环结构，各个节点通过前驱与后继指针相互连接，形成一个紧密的链条。头节点作为整个链表的特殊标识，虽通常不存放实际业务数据，但却为链表的操作提供了极大便利。

typedef struct ListNode
{
	LTDateType data;                      //存放数据
	struct ListNode* next;                //存放下一个节点地址
	struct ListNode* prev;                //存放上一个节点地址
}LTNode;

 头节点的作用与意义：

• 标识起始：作为固定起始标记，是遍历链表的明确起点，链表空或非空时都可由此开始操作。
• 简化操作：在头部插入节点时，无需特殊处理空链表情况，统一操作逻辑。删除第一个节点时，不用单独考虑特殊情况，操作逻辑统一。
• 维护结构：其前驱指向尾节点，尾节点后继指向它，保持链表循环结构完整，便于循环操作。

三、核心操作原理 

1.初始化链表

        在讲初始化链表之前，需要先写一个创建节点的函数，因为在后边的很多操作中都会用到，所以在这里单独将它封装成一个函数。

LTNode* BuyListNode(LTDateType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode)); //开辟一个新的节点
	if (node == NULL)                               //如果开辟失败
	{
		perror("malloc Fail");
		return NULL;                                //返回空
	}
	node->next = NULL;                              //在这里先把它置成空，等使用时指向别的节点
	node->prev = NULL;
	node->data = x;                                 //把新节点的数据的置成我们想要的
	return node;                                    //返回新节点的地址
}

        在之前的单链表中呢，因为没有头节点，所以不需要初始化，而在带头双向循环链表中，因为头结点比较复杂，需要初始化一下。

        带头双向循环链表的初始化就是生成一个节点，让头结点的前驱指向头结点本身，头结点的后继也指向它本身，形成环路。

LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.插入节点

2.1 尾插

         在进行尾插时，首先要生成一个新节点，然后找到链表的最后一个节点tail（找尾）tail=phead->prev，让后让最后一个节点tail的next指向新生成的节点，让新节点的prev指向tail形成循环，在此时，新节点就为链表的最后一个节点了。新节点需要与头结点建立链接，就是新节点的next指向头结点，头结点的prev指向新节点。

void LTPushBack(LTNode* phead, LTDateType x)
{
	//phead一定不为空，如果为空就是传错了
	assert(phead);
	LTNode* newnode = BuyListNode(x);            //生成一个新的节点
	
	LTNode* tail = phead->prev;                  //找尾

	tail->next = newnode;                        //链表最后一个节点的next指向新节点
	newnode->prev = tail;                        //新节点的前驱指向之前链表最后一个节点
	newnode->next = phead;                       //新节点的后继指向头结点
	phead->prev = newnode;                       //头结点的前驱指向新节点
}

  测试：尾插成功

2.2 头插

大致思路：

• 首先找到头结点指向的下一个节点，这里面称这个节点为first，并存起来。
• 生成一个新的节点newnode。
• 让头结点的next指向新节点（phead->next=newnode）。
• 让新节点的prev指向头结点（newnode->prev=phead）。
• 让新节点的next指向之前提到的first节点。
• 让first节点的prev指向新节点。

void LTPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* first = phead->next;                        //找到头结点指向的下一个节点
	LTNode* newnode = BuyListNode(x);                   //生成一个新节点

	phead->next = newnode;                              //让头结点的next指向新节点
	newnode->prev = phead;                              //新节点的prev指向头结点

	newnode->next = first;                              //新节点的next指向之前的第一个节点
	first->prev = newnode;                              //之前第一个节点的prev指向新节点
}

 头插成功！！！

2.3 在pos位置之前插入一个值

大致思路：

• 找到pos位置之前的节点。
• 生成新节点。
• 链接新阶段，形成循环链表。

void LTInsert(LTNode* pos, LTDateType x)
{
	assert(pos);

	LTNode* prev = pos->prev;                //找到pos位置的前一个节点prev
	LTNode* newnode = BuyListNode(x);        //生成一个新的节点

	prev->next = newnode;                    //让prev结点的next指向新节点
	newnode->prev = prev;                    //新节点的prev指向prev节点

	newnode->next = pos;                     //新节点的next指向pos节点
	pos->prev = newnode;                     //pos的prev指向新节点
}

注意：pos为某个节点的地址，在后面我们会学到查找链表某个节点并返回其地址。 

3.删除节点

         无论是头删，还是尾删，或者在某个位置删除节点，我们都需要提前判断链表是否为空，所以我们可以判断链表是否为空单独封装成一个函数，很简单直接看代码。

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next != phead;            //不为空则返回真，为空返回假
}

•  如果phead的next还是phead那么链表就为空。
•  如果phead的next不是phead而是其它的节点，那么链表不为空。 

3.1 尾删

        尾删还是找到尾节点和尾节点之前的那个节点，因为现在是带头双向循环链表，所以找起来很方便！找到尾节点之前的那个节点，并让它与头结点做链接，形成双向循环，释放之前的尾节点。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(LTEmpty(phead));

	LTNode* tail = phead->prev;            //找尾
	LTNode* tailprev = tail->prev;         //找到尾节点前面的那个节点tailprev
	tailprev->next = phead;                //让tailprev的next指向头结点
	phead->prev = tailprev;                //头结点的prev指向tailprev
	free(tail);                            //是否之前的尾节点tail
	tail = NULL;
}

3.2 头删

        头删第一个节点，那么需要找到除头结点之外的第二个节点，头结点与第二个节点链接，释放第一个节点。

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(LTEmpty(phead));

	LTNode* second = phead->next->next;        //找到头结点的下一个节点的下一个节点
	free(phead->next);                         //释放掉头结点的下一个节点
	second->prev = phead;                      //连接
	phead->next = second;
}

3.3 在pos位置删除

        删除pos位置的节点，需要找到pos位置之前的节点posprev和pos之后的节点posnext，释放掉pos位置的节点，链接posprev和posnext，形成双向循环。

void LTErase(LTNode* pos)			//可能会把哨兵位删除
{
	assert(pos);

	LTNode* posprev = pos->prev;    //找到pos位置之前的那个节点posprev
	LTNode* posnext = pos->next;    //找到pos位置之后的那个节点posnext
	posprev->next = posnext;        //posprev与posnext连接，形成双向循环
	posnext->prev = posprev;
	free(pos);                      //释放pos位置的节点
}

 

4.打印链表

        打印链表很简单，可以正向打印，也可以反向打印，都很简单，带头双向循环链表结构虽然复杂，但是用起来针对很简单，直接看代码。

void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("<=head=>");
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

5.查找节点

        遍历整个链表，如果在链表中找到了要找的值，那么返回这个节点，没有找到返回空。

LTNode* LTFind(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		if (cur->data==x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;		//如果遍历链表还没有找到
}

6.销毁链表

void LTDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;                
	while (cur != phead)            //从前往后释放
	{
		LTNode* next = cur->next;   //找到下一个节点        
		free(cur);                  //释放当前节点
		cur = next;                 //当前节点指向下一个节点
	}
	free(phead);                    //最后释放哨兵位
}

四、完整代码

1.List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDateType;
typedef struct ListNode
{
	LTDateType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
//初始化
LTNode* LTInit();
//销毁
void LTDestory(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDateType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDateType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDateType x);
//在pos位置之前插入一个值
void LTInsert(LTNode* pos, LTDateType x);
//删除pos位置
void LTErase(LTNode* pos);

2.List.c

#include"List.h"

LTNode* BuyListNode(LTDateType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc Fail");
		return NULL;
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}
//初始化
LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

//销毁
void LTDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);//最后释放哨兵位
}

//打印链表
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("<=head=>");
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	/*if (phead->next=phead)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return phead->next != phead;
}

//尾插
void LTPushBack(LTNode* phead, LTDateType x)
{
	//phead一定不为空，如果为空就是传错了
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	//找尾
	LTNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//LTInsert(phead, x);
}

//头插
void LTPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyListNode(x);

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

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

	//LTInsert(phead->next, x);
}

//在pos位置之前插入一个值
void LTInsert(LTNode* pos, LTDateType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);

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

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

//删除pos位置
void LTErase(LTNode* pos)			//可能会把哨兵位删除
{
	assert(pos);

	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	posprev->next = posnext;
	posnext->prev = posprev;
	free(pos);
}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(LTEmpty(phead));

	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
	tail = NULL;
	//LTErase(phead->prev);
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(LTEmpty(phead));

	LTNode* second = phead->next->next;
	free(phead->next);
	second->prev = phead;
	phead->next = second;
	//LTErase(phead->next);
}

//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		if (cur->data==x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;		//如果遍历链表还没有找到
}