【数据结构】解密链表之旅（双链表篇）

前言：

哈喽大家好，我是野生的编程萌新，首先感谢大家的观看。数据结构的学习者大多有这样的想法：数据结构很重要，一定要学好，但数据结构比较抽象，有些算法理解起来很困难，学的很累。我想让大家知道的是：数据结构非常有趣，很多算法是智慧的结晶，我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏，在这里我将把数据结构内容以有趣易懂的方式展现给大家。

 1.双向循环链表

1.1循环链表

对于单向链表，由于每个节点只存储了向后的指针，到了尾标志就停止了向后的操作，这样，某一节点就无法找到它的前驱节点，就像我们无法回到从前。比如，你是一个业务员，在石家庄工作，你需要经常出差，行程就是石家庄到重庆一路上的城市。你从石家庄乘坐火车或者高铁出发，乘坐火车或者高铁途径多个城市停留后，到达重庆，再乘坐飞机回到石家庄。以后，每隔一段时间你基本按照这样的行程开展业务，大致流程图如下：

假设有一次，你在西安开会，加下来要把上面的城市都走一遍，这时候有人就和你说了：哎呀，你得先回石家庄，因为石家庄是第一站，我想你的表情是：

根本没有必要直接回石家庄，可以先从西安开始，下一站襄阳，直到重庆，之后再考虑走完石家庄、济南、郑州3个城市。很显然你这是从其中的一个节点开始遍历链表，这都是原来的单向链表结构解决不了的问题。事实上，把石家庄和重庆之间连接起来，形成一个环就解决了前面所面临的困难，就像第一张图中的下部分那样，这就是我们要介绍的循环链表。

 将单链表中的终端节点的指针端由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表成为单向循环链表，简称循环链表。为了使空链表和非空链表处理一致，我们通常设一个头节点，当然，这并不是说，循环链表一定带头结点。其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next指向是否为空，现在则是判断p->next不等于头节点，则循环结束。循环链表有以下几个特点：

1. 头结点和尾节点相连：最后一个节点的下一个节点指向头节点，这样就能形成一个闭环。通过这种连接方式，可以轻松地在循环链表中从任何节点访问到其他节点。

2. 遍历方式：由于循环链表是一个闭环，所以可以从任意节点开始遍历整个链表。可以选择从头节点开始遍历，也可以选择从任意节点开始。

3. 插入和删除节点：在循环链表中插入和删除节点相对较为灵活。插入节点时，只需要更改相邻节点的指针即可；删除节点时，将待删除节点的前一个节点的指针指向待删除节点的下一个节点，然后释放待删除节点的内存即可。

1.2双向链表

继续刚才的例子，你平时都是一直从石家庄到重庆，可这一次你要到重庆开会，开完会后要例行公事，走访各个城市，此时你该怎么办呢？哪有那么麻烦，我一路从重庆坐火车或高铁倒着一个城市一个城市回去就好了嘛。

我们的单链表，总是从开头到尾找节点，难道就不可以正反遍历链表吗？这时候我们只需要加一点东西就可以，我们在单链表中，有了next指针，就可以使我们要查找下一节点的时间复杂度为O(1)。可是我们要查找的是上一个节点的话，那最坏的时间复杂度就是O(n)了，因为我们每次查找都要从头开始遍历查找。 为了解决单向性这一缺点，双向链表就被设计出来了。双向链表是在单链表的每个节点中，在设置一个前驱节点的指针域。所以在双向链表中的节点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

双向链表在某些情况下具有优势，例如：需要在某个节点之后或之前插入或删除节点的场景。需要注意的是，双向链表增加了指针的管理和维护，因此在插入、删除节点时需要额外的操作来维护前后指针的正确性。

1.3双向循环链表

双向循环链表是将循环链表和双向链表相结合的模式，它兼备两者的优点。双向循环链表在某些场景中具有优势，比如需要在一个环形结构中存储数据，并且需要双向遍历和操作节点。它可以方便地实现循环遍历，并且在插入和删除节点时具有灵活性。需要注意的是，在使用双向循环链表时，需要确保指针的正确性以避免出现死循环或空指针引用的问题。

2.双向循环链表的各个功能的实现

在上面我们已经详细介绍了双向循环链表，这里我们直接来对双向循环链表各个功能来实现，首先用C语言来描述单链表的结构指针：

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

在这里我们主要详细介绍双向循环链表的插入删除等操作。在双向循环链表中插入有尾插、头插、任意位置插入等操作，每次插入都需要申请空间，每次申请空间的操作都相同，我们干脆写一个函数来实现申请空间，这样能使我们的操作更加方便。这里我们来实现一下这个函数：

LTNode* CreatNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return -1;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

2.1双向循环链表的创建和销毁

我们主要是以函数的形式来实现各个功能，首先我们先来介绍一下双向循环链表的创建，在这里我们只要初始一下链表的头节点：创建一个头节点，并将头节点的prev和next指针都指向自身，表示链表为空。具体实现代码如下：

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

在双向循环链表中进行销毁的具体步骤为：

1. 从头节点开始，通过next指针遍历整个链表，直到再次回到头节点。
2. 在遍历过程中，每次获取当前节点的下一个节点，并释放当前节点的内存空间。
3. 将链表头节点的prev指针指向NULL，将链表尾节点的next指针指向NULL，确保链表已经断开。
4. 最后，释放头节点的内存空间。

我们来实现一下双向循环链表的销毁：

void LTDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	phead = NULL;
}

2.2双向循环链表的尾插和尾删

双向循环链表的尾插具体操作步骤为：

1. 创建一个新节点设置其数据域为要插入的值，指针域为空。
2. 将尾节点的next指针指向新节点newNode。
3. 将新节点的prev指针指向尾节点。
4. 将新节点的next指针指向头节点。
5. 将头节点的prev指针指向新节点。

我们来实现一下双向循环链表的尾插操作：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = CreatNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

双向循环链表的尾删具体操作步骤为：

1. 定义一个临时变量，用于存储指向链表最后一个节点的指针。
2. 将临时变量的前一个节点的指针指向链表第一个节点，将链表第一个节点的前一个节点的指针指向临时变量的前一个节点。
3. 释放临时变量所指向的节点的内存空间。

我们来具体实现一下双向循环链表的尾删操作：

void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* tmp = tail->prev;
	tmp->next = phead;
	phead->prev = tmp;
	free(tail);
	tail = NULL;
}

2.3双向循环链表的头插和头删

双向循环链表的头插具体操作步骤为：

1. 创建一个新的节点，并给新节点赋予待插入的值。
2. 创建一个变量next储存头结点的下一个节点。
3. 将新节点的next指针指向next变量。
4. 将next的prev指针指向新节点。
5. 将新节点的prev指针指向头节点。
6. 将头结点的next指针指向新节点。

我们来具体实现一下双向循环链表的头插操作：

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;
	LTNode* newnode = CreatNode(x);
	newnode->next = next;
	next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;
}

双向循环链表的头删具体操作步骤为：

1. 创建一个临时变量cur存储头结点的下一个节点。
2. 创建一个临时变脸next指向cur的下一个节点。
3. 将头结点的next指针指向next变量。
4. 将变量next的前驱指针prev指向头节点。
5. 释放掉cur所指向的空间。

我们来具体实现一下双向循环链表的头删操作：

void LTPopFront(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	LTNode* next = cur->next;
	phead->next = next;
	next->prev = phead;
	free(cur);
	cur = NULL;
}

2.4双向循环链表的任意位置插入和删除

双向循环链表的任意位置插入和单链表的任意位置插入相同，首先我们需要先编写一个链表数据元素的查找函数，然后输入一个节点值，接着返回相对应的节点，然后进行插入删除操作。双向循环链表数据元素查找函数实现如下：

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

我们创建一个双向循环链表节点指针变量pos接收查找函数的返回信息。双向循环链表的任意位置插入操作的具体步骤为：

1. 创建一个临时变量tmp存储pos的前一个结点。
2. 创建一个新的节点，并给新节点赋予待插入的值。
3. 将变量tmp的next指针指向新节点。
4. 将新节点的前驱指针prev指向tmp。
5. 将新节点的后驱指针next指向pos.
6. 将pos的前驱指针prev指向新节点。

我们来具体实现一下双向循环链表的任意位置插入的操作：

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* tmp = pos->prev;
	LTNode* newnode = CreatNode(x);
	tmp->next = newnode;
	newnode->prev = tmp;
	newnode->next = pos;
	pos->prev = newnode;
}

双向循环链表的任意位置删除的具体步骤为：

1. 创建一个临时变量tmp存储pos的前一个结点。
2. 创建一个临时变量next存储pos的后一个节点。
3. 将tmp的后驱指针next指向next。
4. 将next的前驱指针prev指向tmp。
5. 释放掉pos所指向的空间。

我们来具体实现一下双向循环链表的任意位置删除的操作：

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* tmp = pos->prev;
	LTNode* next = pos->next;
	tmp->next = next;
	next->prev = tmp;
	free(pos);
	pos = NULL;
}

3.多文件实现双向循环链表

List.h文件：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
LTNode* LTInit();//双链表的创建
void LTPrint(LTNode* phead);//双链表的打印
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsert(LTNode* pos, LTDataType x);//任意位置之前插入
void LTErase(LTNode* pos);//任意位置之前删除
void LTDestory(LTNode* phead);//双链表的销毁

List.c文件：

#include"List.h"
LTNode* CreatNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return -1;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
LTNode* LTInit()
{
	LTNode* phead = CreatNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = CreatNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* tmp = tail->prev;
	tmp->next = phead;
	phead->prev = tmp;
	free(tail);
	tail = NULL;
}
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;
	LTNode* newnode = CreatNode(x);
	newnode->next = next;
	next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;
}
void LTPopFront(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	LTNode* next = cur->next;
	phead->next = next;
	next->prev = phead;
	free(cur);
	cur = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* tmp = pos->prev;
	LTNode* newnode = CreatNode(x);
	tmp->next = newnode;
	newnode->prev = tmp;
	newnode->next = pos;
	pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* tmp = pos->prev;
	LTNode* next = pos->next;
	tmp->next = next;
	next->prev = tmp;
	free(pos);
	pos = NULL;
}
void LTDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	phead = NULL;
}

test.c文件（在这里测试函数功能）：

#include"List.h"
void Test1()
{
	LTNode* ps = LTInit();
	LTPushBack(ps, 1);
	LTPushBack(ps, 2);
	LTPushBack(ps, 3);
	LTPushBack(ps, 4);
	LTPushBack(ps, 5);
	LTPrint(ps);
	LTPopBack(ps);
	LTPrint(ps);
	LTPushFront(ps, 5);
	LTPrint(ps);
	LTPopFront(ps);
	LTPrint(ps);
	LTNode* pos = LTFind(ps, 1);
	LTInsert(pos, 20);
	LTPrint(ps);
	pos = LTFind(ps, 20);
	LTErase(pos);
	LTPrint(ps);
	LTDestory(ps);
}
int main()
{
	Test1();
	return 0;
}

我们看看测试结果：