数据结构（初阶）（四）----双向链表

双向链表

链表分类:8种（2*2*2）

带头，不带头

单向，双向

循环，不循环

最常用的是两种：

单链表：不带头，单向，不循环链表

双链表：带头，双向，循环链表

带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥占位置，类似于“放哨的”。

双向链表由结点组成：结点中包含数据，指向下一个结点的指针以及指向前一个结点的指针

struct ListNode
{
	int data;
	struct ListNode* next;
	struct ListNode* prev;
}

初始化

单链表为空链表时，那么链表中没有节点，plist就指向NULL

双向链表为空时，此时链表只有一个头结点（哨兵位），如果没有哨兵位，那么它就不能被称为双向链表，于是我们在对双向链表初始化时，一定要创建一个哨兵位。

思考：在初始化时，是否可以将哨兵位的prev，next指针初始化为NULL？

答案是绝对不可以。

应该将哨兵位的prev，next指针都指向它自己。

#include"List.h"
//申请结点
LTNode* LTBuyNode(x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->prev = newnode->next = newnode;
	return newnode;
}
//以参数的形式返回哨兵位
//创建链表,创建一个哨兵位
//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}

//以返回值的形式返回哨兵位，推荐使用
//创建链表,创建一个哨兵位
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

调用的区别

参数形式的调用

List是指向节点的指针，节点指针，它存储的内容是结点的地址
//LTNode* plist = NULL;
&pList，是取指向节点的指针的地址，这样就可以修改指向节点的指针的地址
//LTInit(&plist);

返回值形式的调用

//在初始化中，创建节点，并返回指向节点的指针（推荐使用，原因末尾会讲）
LTNode* List = LTInit();

尾插

首先我们需要知道：哨兵位结点不能被删除，结点的地址也不能发生改变
哨兵位不能为空，否则链表无效，再操作就没有用了

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);

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

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

如果只有哨兵位，代码是否成立？

成立！

注意：

不能完全交换

如果交换，d3的地址丢失，代码会出问题

如果非要交换，可以先将d3的地址存储起来，保证之后可以正常使用

打印

哨兵位不是有效结点，直接从哨兵位的下一个结点打印，直到循环到哨兵位结束

//打印链表
void LTPrint(LTNode* phead)
{
	//哨兵位不再打印
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

尾删

1，首先我们在进行删除操作时，需要保证链表有效且不能为空（即只有一个哨兵位时）。

2，先找到最后一个结点位置，即phead->next;

将该节点保存下来，以便后续使用。

3，将最后一个结点的prev节点与哨兵位结点联系起来，使之成为新的最后结点

4，释放del节点，并置空。

//尾删
void LTPopBack(LTNode* phead)
{
	//assert(phead && phead->prav != phead);
	assert(phead && phead->next != phead);

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	
	free(del);
	del = NULL;
}

头插

插入到第一个有效结点之前，即哨兵位后面

操作和尾插极其相似，不再赘述。

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	//链表要有效
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

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

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

头删

和尾删非常相似。

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);

	LTNode* del = phead->next;

	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

查找

遍历双向链表

注意，循环条件是pcur != phead，因为双向链表是循环链表，如果不加该条件，循环将会一直成立，这点与单链表不同。

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur->next;
	}
	return NULL;
}

在pos位置之后插入数据

先修改新结点，不会影响原链表的结点

//在指定位置pos之后插入数据
void LTInsertBack(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);

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

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

在pos位置之前插入数据

与在之后插入数据相似。

不再详细写。

删除pos结点

//删除pos结点
void LTErase(LTNode* pos)
{
	//pos理论上来说不能为phead，但是此处并没有传phead，无法校验
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}

要将pos结点的空间释放并置空，为什么在这里不传二级指针？

在理论上参数是要传二级指针的，因为我们需要让形参的改变影响实参，

没有这样做的原因是为了保持接口的一致性。

在双向链表的方法中传的都是一级指针，可以大大降低使用方法的记忆成本。

正确解决方法是，在测试文件中调用方法后，将find置空

这就解释了为什么我们在最开始对双向链表初始化时，要以返回值的形式返回哨兵位。

销毁链表

与删除不同的是，销毁；链表要删除哨兵位。

此处依旧传一级指针，原因是保持接口一致性，统一参数，解决方法与上面一样。

//销毁链表
void LTDesTroy(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur已经循环到phead，即pcur指向phead，phead也要销毁
	free(phead);
	phead = NULL;
}

调试

跳出函数后，pcur销毁，所以在函数内部不置空也没有问题

但是调用时，plist没有置空，需要手动置空