数据结构：双向链表

2024-04-17 08:48:38

一.双向链表的结构

最常用的链表就是单链表和双向链表。我们首先要知道，链表有八种分类。单链表是不带头单向不循环链表。而此篇博客要讲的是带头双向循环链表。

结构如下：

注意：带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的” 。它存在的意义就是遍历循环链表避免死循环。

我们所说的双向链表为空，跟单链表不同，双向链表就是只存在哨兵位。双向链表的实现就比单链表简单的多了。

二.双向链表的实现

1.申请一个新节点和初始化

//创建一个新节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));//动态申请空间
	if (node == NULL)
	{
		perror("node");
		exit(1);
	}
	node->next = node;
	node->prev = node;//把新节点的next指针和prev指针都指向自己
	node->data = x;
	return node;//返回我们的新节点
}
//初始化
void LTInit(LTNode** pphead)
{
	//给双向链表创建一个哨兵位
	*pphead = LTBuyNode(-1);//初始化时我们需要改变首节点，用二级指针传参
}

注意在创建新节点的时候我们一定要把next指针和prev都指向自己。初始化其实就是给我们创建一个哨兵位。

其实初始化不用二级指针也可以做到初始话：

//不用二级指针的初始化
LTNode* LTInit(LTNode* phead)
{
	phead = LTBuyNode(-1);
	return phead;
}

返回指针就行了。

2.尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);//创建一个新节点
	newnode->prev = phead->prev;
	newnode->next = phead;//先把newnode的指向指针都给改了

	phead->prev->next = newnode;
	phead->prev = newnode;//这一行不能与上一行交换位置
}

为了方便查看我们写的代码是否有错误，我们可以打印出来：

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

这个是在后面的测试过程来用的。

3.头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = phead;
	newnode->next = phead->next;//先改变newnode节点指针的指向

	phead->next->prev = newnode;
	phead->next = newnode;//同样这两个的位置也不可以调换
}

4.尾删

尾删就更简单了：

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead&&phead->next!=NULL);//链表必须不能为NULL，且必须有效
	LTNode* del = phead->prev;//把尾节点存起来
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;//释放后置为NULL，这是习惯
}

5.头删

头删的时候一定要注意，我们删的可不是哨兵位，是有效位的头。

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != NULL);
	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;//这两行代码可以互换，因为我们已经提前把phead->next的值存起来了
	free(del);
	del = NULL;
}

6.指定位置之后插入

在指定位置插入，我们可以先写一个函数来找到指定位置：

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)//遍历双向链表
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

然后执行插入：

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);

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

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

7.删除指定节点

//删除pos节点
void LTErase(LTNode* pos)
{
	//pos理论上来说不能为phead，但是没有参数phead，无法增加校验
	assert(pos);
	
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}

8.销毁链表

void LTDesTroy(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur指向phead，而phead还没有被销毁
	free(phead);
	phead = NULL;
}

三.双向链表功能实现的测试

void text1()
{
	//初始化
	LTNode* plist = LTInit();
	//尾插
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印
	LTPrint(plist);
	//头插
	LTPushFront(plist, 100);
	LTPushFront(plist, 200);
	LTPushFront(plist, 300);
	LTPrint(plist);
	//尾删
	LTPopBack(plist);
	LTPrint(plist);
	//头删
	LTPopFront(plist);
	LTPrint(plist);
	//查找
	LTNode* find = LTFind(plist, 1);
	//在指定位置之后插入数据
	LTInsert(find, 66);
	LTPrint(plist);
	//删除指定位置的数据
	LTErase(find);
	find = NULL;
	LTPrint(plist);
	//销毁链表
	LTDesTroy(find);
    plist=NULL;
}
int main()
{
	text1();
	return 0;
}

为了保证接口的一致性，即使是LTErase和LTDesTory这些理论上需要传递二级指针的函数，我们也给它传递了一级指针。但是我们一定要注意 LTDesTory和LTErase当我们在函数内部把节点给释放掉之后，在函数的内部我们把释放掉的指针给置为了NULL，但是在出了函数的时候，我们是实参并没有置为NULL，所以我们需要多加一步对实参置为NULL，这样代码才完整。

关于双向链表是比单向链表要简单的多的。感谢大家的观看，如有错误，请多多指出。

码农公寓