【数据结构】解密链表之旅(双链表篇)
前言:
哈喽大家好,我是野生的编程萌新,首先感谢大家的观看。数据结构的学习者大多有这样的想法:数据结构很重要,一定要学好,但数据结构比较抽象,有些算法理解起来很困难,学的很累。我想让大家知道的是:数据结构非常有趣,很多算法是智慧的结晶,我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏,在这里我将把数据结构内容以有趣易懂的方式展现给大家。
1.双向循环链表
1.1循环链表
对于单向链表,由于每个节点只存储了向后的指针,到了尾标志就停止了向后的操作,这样,某一节点就无法找到它的前驱节点,就像我们无法回到从前。比如,你是一个业务员,在石家庄工作,你需要经常出差,行程就是石家庄到重庆一路上的城市。你从石家庄乘坐火车或者高铁出发,乘坐火车或者高铁途径多个城市停留后,到达重庆,再乘坐飞机回到石家庄。以后,每隔一段时间你基本按照这样的行程开展业务,大致流程图如下:
假设有一次,你在西安开会,加下来要把上面的城市都走一遍,这时候有人就和你说了:哎呀,你得先回石家庄,因为石家庄是第一站,我想你的表情是:
根本没有必要直接回石家庄,可以先从西安开始,下一站襄阳,直到重庆,之后再考虑走完石家庄、济南、郑州3个城市。很显然你这是从其中的一个节点开始遍历链表,这都是原来的单向链表结构解决不了的问题。事实上,把石家庄和重庆之间连接起来,形成一个环就解决了前面所面临的困难,就像第一张图中的下部分那样,这就是我们要介绍的循环链表。
将单链表中的终端节点的指针端由空指针改为指向头节点,就使整个单链表形成一个环,这种头尾相接的单链表成为单向循环链表,简称循环链表。为了使空链表和非空链表处理一致,我们通常设一个头节点,当然,这并不是说,循环链表一定带头结点。其实循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p->next指向是否为空,现在则是判断p->next不等于头节点,则循环结束。循环链表有以下几个特点:
-
头结点和尾节点相连:最后一个节点的下一个节点指向头节点,这样就能形成一个闭环。通过这种连接方式,可以轻松地在循环链表中从任何节点访问到其他节点。
-
遍历方式:由于循环链表是一个闭环,所以可以从任意节点开始遍历整个链表。可以选择从头节点开始遍历,也可以选择从任意节点开始。
-
插入和删除节点:在循环链表中插入和删除节点相对较为灵活。插入节点时,只需要更改相邻节点的指针即可;删除节点时,将待删除节点的前一个节点的指针指向待删除节点的下一个节点,然后释放待删除节点的内存即可。
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; }
在双向循环链表中进行销毁的具体步骤为:
- 从头节点开始,通过next指针遍历整个链表,直到再次回到头节点。
- 在遍历过程中,每次获取当前节点的下一个节点,并释放当前节点的内存空间。
- 将链表头节点的prev指针指向NULL,将链表尾节点的next指针指向NULL,确保链表已经断开。
- 最后,释放头节点的内存空间。
我们来实现一下双向循环链表的销毁:
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双向循环链表的尾插和尾删
双向循环链表的尾插具体操作步骤为:
- 创建一个新节点设置其数据域为要插入的值,指针域为空。
- 将尾节点的next指针指向新节点newNode。
- 将新节点的prev指针指向尾节点。
- 将新节点的next指针指向头节点。
- 将头节点的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; }
双向循环链表的尾删具体操作步骤为:
- 定义一个临时变量,用于存储指向链表最后一个节点的指针。
- 将临时变量的前一个节点的指针指向链表第一个节点,将链表第一个节点的前一个节点的指针指向临时变量的前一个节点。
- 释放临时变量所指向的节点的内存空间。
我们来具体实现一下双向循环链表的尾删操作:
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双向循环链表的头插和头删
双向循环链表的头插具体操作步骤为:
- 创建一个新的节点,并给新节点赋予待插入的值。
- 创建一个变量next储存头结点的下一个节点。
- 将新节点的next指针指向next变量。
- 将next的prev指针指向新节点。
- 将新节点的prev指针指向头节点。
- 将头结点的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; }
双向循环链表的头删具体操作步骤为:
- 创建一个临时变量cur存储头结点的下一个节点。
- 创建一个临时变脸next指向cur的下一个节点。
- 将头结点的next指针指向next变量。
- 将变量next的前驱指针prev指向头节点。
- 释放掉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接收查找函数的返回信息。双向循环链表的任意位置插入操作的具体步骤为:
- 创建一个临时变量tmp存储pos的前一个结点。
- 创建一个新的节点,并给新节点赋予待插入的值。
- 将变量tmp的next指针指向新节点。
- 将新节点的前驱指针prev指向tmp。
- 将新节点的后驱指针next指向pos.
- 将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; }
双向循环链表的任意位置删除的具体步骤为:
- 创建一个临时变量tmp存储pos的前一个结点。
- 创建一个临时变量next存储pos的后一个节点。
- 将tmp的后驱指针next指向next。
- 将next的前驱指针prev指向tmp。
- 释放掉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 #include #include 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; }
我们看看测试结果: