C语言中的数据结构--双向链表

前言

上一节我们已经学习完了单链表（单向不带头不循环链表）的所有内容，我们在链表的分类里面知道了，链表分为单向的和双向的，那么本节我们就来进行双向链表（带头双向循环链表）的学习，那么废话不多说，我们正式进入今天的学习

双向链表的结构

（该图片来源于网络）

通过之前的学习我们知道，链表是由节点组成的。那么双向链表也同样如此，只是双向链表的节点与单链表的节点存在一些不同：

1.双向链表节点包含数据 [int data]；

2.双向链表节点包含指向下一个节点的指针 [struct ListNode* next]；

3.双向链表节点包含指向上一个节点的指针 [struct ListNode* prev]；

因为双向链表可以从后往前或者从前往后遍历，所以双向链表里面的节点不仅需要有包含指向下一个节点的指针，还需要有指向上一个节点的指针

那么我们就可以定义双向链表里面的节点的结构了：

typedef int LTDataType;
//定义双向链表的结构
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

之前我们在学习单链表的时候，我们在使用时直接创建一个空链表，然后让空链表直接等于空指针，再将节点依次连接在新链表的尾部

而双向链表不可以是一个空链表，在创建双向链表的时候必须要初始化一个哨兵位，然后再执行节点的插入删除

双向链表的初始化

在双向链表中修改数据之前，我们必须保证双向链表中初始化了一个头节点，所以我们先要进行双向链表的初始化；

因为我们要对双向链表里面的数据进行修改，所以我们传入的变量应该是一个二级指针；

我们先定义一个函数用于申请节点，在申请节点的时候我们需要考虑一个问题：在初始化的时候我们不能把next指针和prev指针都初始化为空指针，因为这样会导致链表不循环。正确的初始化过程应该是让next指针和prev指针都指向自己，所以据此我们可以写出双向链表申请节点的代码：

LTNode* LTBuyNode(LTDataType x)
{
	//申请节点
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;
	return node;
}

在初始化时，我们需要给双向链表创建一个哨兵位，我们随便传入一个合格的数据就行：

//初始化
void LTInit(LTNode** pphead)
{
	//给双向链表创建一个哨兵位
	*pphead = LTBuyNode(-1);
}

双向链表的打印

要实现双向链表的打印，我们需要遍历双向链表。因为双向链表是循环链表，所以我们该采取什么方法去遍历呢?

此时我们不能采取之前单链表的遍历方法，不然就会造成死循环。此时我们发现了一个特殊节点--哨兵位，我们可以从第一个有效的节点处开始遍历，直到遍历到哨兵位跳出循环；

所以根据这些，我们可以写出代码：

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

双向链表的尾插

在实现尾插之前，我们首先需要考虑要往尾插代码之中传入什么变量；

因为我们不管是尾插还是头插，哨兵位的位置都不能被修改，都必须在链表中的第一位，所以此时我们传入的变量类型与不带头的链表不同，我们只需要传入一级指针就行了（也可以传二级指针，但是前提是不能修改哨兵位）

1.一级指针 LTNode* phead

2.传入的数据 LTDataType x

尾插的实现

当我们申请了一个新节点的时候，此时该节点的next指针和prev指针都是指向自己的；

我们先来分析一下：当我们申请了一个新节点，并且需要把它尾插到原双向链表之中去，那么它将会影响到原双向链表的头节点和尾节点，所以我们需要对原双向链表的头节点和尾节点进行修改；

我们可以通过phead->prev指针找到原双向链表的尾节点，所以我们不需要遍历链表；

因为先修改newnode的next和prev指针不会对原双向链表产生影响，所以我们首先对newnode进行修改。我们让newnode的prev指针指向原双向链表的尾节点，再把newnode的next指针指向双向链表的哨兵位；

接下来我们让原双向链表的头节点和尾节点去指向newnode。我们先让尾节点的next指针指向newnode，再让哨兵位的prev指针指向newnode；

我们最后来考虑一下特殊情况，若双向链表为空链表，此时链表中只有哨兵位。此时我们将该条件代入代码中去，我们发现仍然没有错误；

有了这些理论基础，我们可以尝试写一下代码：

//尾插
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;
}

注意：以下两行代码的顺序不能发生改变，因为要是改了，phead->next指针找到的节点就不是尾节点了，而是newnode节点

下面我们来测试一下：

void ListTest01()
{
	LTNode* plist = NULL;
	LTInit(&plist);
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
}

int main(void)
{
	ListTest01();
	return 0;
}

代码运行正确，编写成功

双向链表的头插

在进行头插之前，我们首先要保证哨兵位不能为空；

我们在进行头插的时候，不是直接把节点插入到哨兵位前面，而是把节点插入到第一个有效的数据前面，把节点插入到哨兵位的前面本质上是尾插；

我们首先来分析一下，如果我们把节点头插到第一个有效数据的前面将会影响到哪些节点：我们需要把哨兵位的next指针指向新节点，原链表中的第一个有效数据的prev指针需要指向新节点，同时我们需要把新节点的prev指针指向哨兵位，next指针指向原链表中的第一个有效数据；

因为先修改newnode的next和prev指针不会对原双向链表产生影响，所以我们首先对newnode进行修改。我们把新节点的prev指针指向哨兵位，next指针指向原链表中的第一个有效数据；

然后我们需要把第一个有效数据的prev指针指向新节点，不能先改变哨兵位的next指针，因为这样会导致找不到第一个有效数据。然后我们让第哨兵位的next指针指向新节点；

我们梳理完思路以后就可以开始代码的编写了：

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;

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

我们来测试一下代码：

void ListTest01()
{
	LTNode* plist = NULL;
	LTInit(&plist);
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);
}
int main(void)
{
	ListTest01();
	return 0;
}

代码成功运行，编写成功

双向链表的尾部删除

我们首先来分析一下尾部删除需要传入哪些变量：

因为哨兵位不能被删除，所以我们只需要传入一个一级指针 LTNode* phead；

我们需要保证双向链表的哨兵位不能为空且有效。注意空链表指的是双向链表仅有头节点，而双向链表无效则表示双向链表没有头节点；

我们再来考虑一下删除尾节点会影响到哪些节点：删除尾节点会影响到尾节点的上一个节点以及哨兵位，所以我们在删除尾节点之前，先得修改哨兵位的prev指针和尾节点的上一个节点的next指针

我们先对尾节点的前一个节点进行修改，我们让尾节点的上一个节点的next指针直接指向哨兵位，我们再把哨兵位的prev指针指向尾节点的上一个节点；

此时尾节点对原双向链表没有任何影响，我们直接释放掉尾节点；

据此，我们可以写出代码如下：

//尾删
void LTPopBack(LTNode* phead)
{
	//链表不能为空且有效
	assert(phead && phead->next != phead);
	//尾节点
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	//删除del节点
	free(del);
	del = NULL;
}

下面我们来测试一下：

void ListTest01()
{
	LTNode* plist = NULL;
	LTInit(&plist);
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
}
int main(void)
{
	ListTest01();
	return 0;
}

代码成功运行，编写成功

双向链表的头部删除

与双向链表的尾部删除一样，我们需要保证双向链表的哨兵位不能为空且有效；

同样的我们也只需要传入一个参数-----一级指针 LTNode* phead；

我们首先来分析一下，进行头部删除会影响哪些节点：进行头部删除将会影响到哨兵位和第一个有效节点的下一个节点；

为了方便，我们创建一个del变量用来存放第一个有效节点，del节点可以通过哨兵位的next指针找到，所以第一个有效节点的下一个节点可以表示为del->next；

我们需要把第一个有效节点的下一个节点的prev指针指向哨兵位，再把哨兵位的next指针指向第一个有效节点的下一个节点，此时对第一个节点修改将不会影响双向链表，所以我们直接释放掉第一个节点；

注意：如果我们不用保存del保存第一个节点，那么当我们在修改了哨兵位以后，将找不到第一个有效节点的下一个节点；

//头删
void LTPopFront(LTNode* phead)
{
	//链表不能为空且有效
	assert(phead && phead->next != phead);
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	//删除del
	free(del);
	del = NULL;
}

我们来测试一下头删代码：

代码成功运行，编写成功

在双向链表的指定位置之后插入数据

要想实现在指定的位置插入数据，我们就要先实现查找的功能

双向链表的查找功能

我们来分析一下要想实现查找的功能需要需要传入哪些变量：

1.头节点 LTNode* phead

2.要查找的数据x

查找数据的需要我们遍历双向链表，我们从第一个有效节点开始遍历，直到遍历到哨兵位；

据此我们可以写出代码如下：

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

实现在双向链表的指定位置之后插入数据

在开始编写在双向链表的指定位置插入数据的代码之前，我们首先需要考虑要传入哪些参数：

1.指定位置 LTNode* pos

2.插入的数据 LTDataType x

我们先来分析一下要想实现在双向链表的指定位置之后插入数据，会对哪些节点产生影响：在指定位置pos之后插入数据会影响pos处的节点和pos->next指向的节点；

我们先对newnode节点进行修改，因为修改newnode节点不会影响到原双向链表。我们把newnode的prev指针指向pos处的节点，再把newnode的next指针指向pos的后一个节点；

然后我们需要先修改pos的下一个节点，因为要是先修改pos节点，那么将无法找到pos的下一个节点。所以我们把pos的下一个节点的prev指针指向newnode，再把pos节点的next指针指向newnode；

我们再来考虑一下特殊情况：假设pos的位置是原双向链表的尾节点，此时我们能不能直接调用尾插的方法呢？答案是否定的，因为尾插需要使用的参数是phead，但是我们在该函数中并没有传入phead。我们将这个条件直接带入到我们之前的思路里面，发现我们之前的思路也满足该特殊情况，所以代码不用做任何增加或者修改

所以据此我们可以写出代码如下：

//在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;
}

我们来测试一下：

void ListTest01()
{
	LTNode* plist = NULL;
	LTInit(&plist);
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTNode* find = LTFind(plist, 3);
	LTInsert(find, 666);
	LTPrint(plist);
}
int main(void)
{
	ListTest01();
	return 0;
}

代码成功运行，编写成功

删除指定位置的节点

要想删除指定位置的节点，我们只需要传入指定的位置pos

我们首先需要保证pos处的数据不为空，pos理论上来说不能为phead，但是没有参数phead，无法增加校验，故忽略

我们先思考一下要想删除指定位置的节点会影响到哪些节点：

1.pos的前一个节点

2.pos的后一个节点

我们需要把pos前一个节点的next指针指向pos的后一个节点，再把pos的后一个节点的prev指针指向pos的前一个节点，此时可以直接释放掉pos节点，不会对链表产生影响；

据此我们可以写出代码如下：

//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

我们来测试一下代码：

void ListTest01()
{
	LTNode* plist = NULL;
	LTInit(&plist);
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTNode* find = LTFind(plist, 3);
	LTErase(find, 666);
	LTPrint(plist);
}
int main(void)
{
	ListTest01();
	return 0;
}

代码成功运行，编写成功

销毁链表

销毁链表仅需要传入头节点（LTNode* phead）就行

我们先定义一个变量pcur用于遍历链表，再创建一个变量next用于存储pcur的下一个节点，以免pcur找不到后面的节点，然后我们从第一个有效节点处开始逐一向下销毁链表，直到销毁到哨兵位时跳出循环，然后销毁哨兵位；

据此我们可以写出代码如下：

//销毁链表
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;
}

结尾

本节我们学习了双向链表，该结构相较于单链表会更加有优势，而且实现起来相对更简单，那么有关双向链表的所有内容就到此为止了，谢谢您的浏览