C语言实现带头双向循环链表

文章目录

写在前面
1. 链表节点的定义
2. 链表的初始化
3. 插入数据
- 3.1 头插
- 3.2 尾插
- 3.3 在指定位置的前面插入数据
4 删除数据
- 4.1 头删
- 4.2 尾删
- 4.3 删除指定位置的数据
5 查找并修改数据
5. 链表的销毁

写在前面

上面文章用C语言实现了单链表的增删查改，我们知道，单链表只能从头结点开始正向遍历，而在单链表中插入或删除节点时，需要修改前一个节点的指针，因此在单链表中插入或删除节点时需要遍历链表找到前一个节点，导致插入和删除操作的效率较低。为了能够高效率解决类似的问题，本片文章继续用C语言来实现另一种线性存储结构——带头双向循环链表。
我们从它的逻辑结构来更深层次的理解一下带头双向循环链表：
在这里插入图片描述

1. 链表节点的定义

链表的结点分为三部分：指针域、数据域、指针域。
指针域：用于指向当前节点的直接前驱节点
数据域：链表要存储的数据所在的区域。
指针域：用于指向当前节点的直接后继节点。

链表节点的逻辑图：
在这里插入图片描述
链表节点的定义：

typedef int STDataType;
typedef struct ListNode
{
	struct ListNode* prev;//指针域， 指向上一个节点
	struct ListNode* next;//指针域， 指向下一个节点
	STDataType val;//数据域
}LTNode;

2. 链表的初始化

该链表在初始化的时候，只需要创建哨兵位的头节点即可，并将该节点的地址返回。该节点不存储有效数据，其prev 和 next指针指向自己。
在这里插入图片描述
由于后面的插入都需要创建新的节点，因此这里把创建节点封装成一个函数。

LTNode* BuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror(" BuyNode()");
	}

	newnode->val = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}

链表的初始化代码如下：

LTNode* LTInit()
{
	//创建哨兵位的头节点
	LTNode* newnode = BuyNode(-1);
	
	//prev 和 next指针指向自己
	newnode->next = newnode;
	newnode->prev = newnode;
	return newnode;
}

3. 插入数据

向链表插入数据时，根据插入位置的不同可以分为以下三种情况：

在头节点前插入一个元素，即头插。
在链表中间位置插入元素。
在最后一个节点后面插入一个元素，即尾插。

3.1 头插

头插数据步骤：

首先，创建一个新的节点，并用 val 初始化其数据域。
将新节点插入到链表的头部，更新指针。

代码如下：

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);//检查参数有效性
	LTNode* newnode = BuyNode(x);//创建新节点

	LTNode* next = phead->next;

	//修改指针链接关系
	newnode->next = next;
	next->prev = newnode;

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

3.2 尾插

尾插数据步骤：

首先，创建一个新的节点，并用 val 初始化其数据域。
将新节点插入到链表的尾部，更新指针。

在这里插入图片描述
代码如下：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//检查参数有效性
	LTNode* newnode = BuyNode(x);//创建新节点

	LTNode* tail = phead->prev;

	//修改指针链接关系
	newnode->prev = tail;
	tail->next = newnode;

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

3.3 在指定位置的前面插入数据

首先，创建一个新的节点，并用 val 初始化其数据域。
将新节点插入到链表的 pos 位置之前，更新指针。

代码如下：

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);//检查位置有效性
	LTNode* newnode = BuyNode(x);//创建新节点
	
	LTNode* posPrev = pos->prev;
	
	//修改指针链接关系
	pos->prev = newnode;
	newnode->next = pos;

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

4 删除数据

4.1 头删

头删的步骤如下：

判断链表是否为空，不为空在进行删除。
判断链表是否为空的代码如下：

bool LTEmpty(LTNode* phead)
{
	return phead->next == phead;
}

删除第一个节点，并更新指针。

在这里插入图片描述

代码如下：

void LTPopFront(LTNode* phead)
{
	assert(phead);//检查参数有效性
	assert(!LTEmpty(phead));//判断链表是否为空

	LTNode* pos = phead->next;
	LTNode* posNext = pos->next;

	free(pos);//删除第一个节点
	修改指针链接关系
	phead->next = posNext;
	posNext->prev = phead;
}

4.2 尾删

头删的步骤如下：

判断链表是否为空，不为空在进行删除。
删除最后一个节点，并更新指针。

代码如下：

void LTPopBack(LTNode* phead)
{
	assert(phead);//检查参数有效性
	assert(!LTEmpty(phead));//判断链表是否为空

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

	free(tail);//删除最后一个节点
	修改指针链接关系
	phead->prev = tailPrev;
	tailPrev->next = phead;
}

4.3 删除指定位置的数据

注意：删除指定位置的数据，需要传递正确的节点的地址，否则删除的结果是不确定的。

在这里插入图片描述
代码如下：

void LTErase(LTNode* pos)
{
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	free(pos);//删除指定位置的节点

	//修改指针链接关系
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

5 查找并修改数据

遍历链表若找到目标节点，就返回目标节点的地址，否则返回空指针(NULL)。
该函数兼并修改的功能，因为该函数返回的是目标节点的地址。
代码如下：

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);//检查参数有效性
	LTNode* cur = phead->next;
	//遍历链表
	while (cur != phead)
	{
		//找到返回，目标节点地址
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	//未找到，返回NLL
	return NULL;
}

5. 链表的销毁

依次释放链表的每个节点。
释放哨兵位的头节点。

注意：链表销毁以后，要在函数外面将头指针置空(NULL),以免造成野指针的问题。

代码如下：

void LTDestroy(LTNode* phead)
{
	assert(phead);//检查参数有效性
	LTNode* cur = phead->next;

	//依次释放链表的每个节点
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);//释放哨兵位的头节点
}