本文图皆为作者手绘,所有代码基于vs2022运行测试

系列文章目录

数据结构初探: 顺序表
数据结构初探:链表之单链表篇

---

---

前言

在前文的单链表学习中,我们已经深刻的认识到单链表的方方面面,我们知道单链表适合用于其他数据结构的子结构,那双向链表又是怎么样的呢,现在我们继续来讲双向链表的强大之处.
双向带头循环链表:融合了双向指针、头节点以及循环特性，这三大特性相互交织，赋予了链表强大的功能。双向指针让我们能够在链表中自由往返，无论是向前追溯还是向后探寻，都能轻松实现；头节点的存在，为链表的操作提供了一个稳定的起点，简化了边界条件的处理；而循环特性，则让链表成为一个无始无终的环，使遍历操作更加流畅，也为一些复杂算法的实现提供了便利。

在这篇博客中，我将带你深入剖析双向带头循环链表的奥秘。从其精妙的结构设计，到具体的代码实现，再到实际应用场景的探讨，我会一步一步揭开它神秘的面纱，带你领略它在数据结构领域的独特魅力，让你掌握这一强大的数据结构工具。

---

以下所称双向链表,均为双向带头循环链表

一.双向链表的概念

定义

• 双向带头循环链表是在双向链表的基础上，增加了头节点和循环特性。链表中存在一个特殊的头节点，它不存储实际数据，其前驱指针指向链表的最后一个节点，后继指针指向第一个真正存储数据的节点。而链表的最后一个节点的后继指针指向头节点，头节点的前驱指针也指向最后一个节点，形成一个循环的结构。

组成

• 头节点：是链表的起始标志，不存储有效数据，主要用于标识链表的开始位置以及方便链表的操作，如插入、删除等。
• 数据节点：用于存储实际的数据元素，每个数据节点都有一个指向前驱节点的指针和一个指向后继节点的指针，从而实现双向链接。

特点

• 双向访问：与双向链表一样，能够从任意一个节点出发，方便地向前或向后遍历链表，访问前后节点的数据。
• 循环特性：从链表中的任何一个节点出发，都可以通过指针遍历到链表中的其他所有节点，没有明显的起点和终点，在进行一些循环操作或需要反复遍历链表时非常方便。
• 操作统一：由于有头节点的存在，在进行插入、删除等操作时，无需对头部和其他位置进行特殊处理，使操作更加统一和简单，减少了代码的复杂性和出错的可能性。

应用场景

• 操作系统中的进程调度：可以将各个进程控制块用双向带头循环链表连接起来，方便按照一定的调度算法在各个进程之间进行切换，循环遍历查找合适的进程运行。
• 循环缓冲区：在数据通信或数据处理中，用于实现循环缓冲区，数据可以在缓冲区中循环存储和读取，提高数据处理的效率和灵活性。
• 实现一些复杂的数据结构：如哈希表中的链地址法解决冲突时，若采用双向带头循环链表作为链的结构，可以更方便地进行节点的插入、删除和查找操作。

以下为结构图:

二.双向链表的存储结构

由上文我们可以知道,双向链表的节点是在包含数据的同时,存在着prev指针和next指针,让我们来看看具体的逻辑代码结构:

typedef int LTDataType;//方便修改变量类型;typedef struct ListNode
{LTDataType data;//数据存储struct ListNode* next;//指向下一个节点;struct ListNode* prev;//指向前一个节点;
}LTNode;

为了图片的美观,我就采取了横向的节点构成,这样在后面更方便能体现循环的特点,下面是节点的图结构:

现在我们已经了解了其节点的构成,该开始学习增删查改函数啦!

三.准备工作

创建对应的三个文件夹:
1.List.h:用于存储创建链表的节点结构体和增删查改函数的函数声明,以及对应的库函数,方便生成程序时的链接;
2.List.c:用于函数的实现;
3.test.c:用于测试和修改;
ps:2和3,均要包含头文件1,即 #include"List.h".

四.双向链表的增删查改的实现

1.List.h

以下是必要的函数声明:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;
//可复用的节点创建函数
LTNode* CreatListNode(LTDataType x);
//初始化
LTNode* LTInit();
//销毁
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//判断是否为空
bool LTEmpty(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//中间插入`
void LTInsert(LTNode* pos, LTDataType x);
//中间删除
void LTErase(LTNode* pos);

在了解了这些不同函数的声明后,就来到我们的老环节啦—函数的实现!

2.List.c

2.1双向链表的可复用的节点创建函数

//因为需要返回一个新节点的地址,所以使用我们的结构体指针
LTNode* CreatListNode(LTDataType x)
{//使用动态内存开辟,开辟出结构体空间LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL)//是否开辟空间失败{perror("malloc fail");//返回错误行return NULL;//结束}newNode->data = x;//存储数据newNode->next = NULL;//初始化置空newNode->prev = NULL;//初始化置空return newNode;//返回新节点地址;
}

我个人是比较建议每次都将创建新节点的函数单开出来,方便后续复用;

2.2双向链表的初始化

LTNode* LTInit()
{//利用-1创建新节点,即创建一个不带数据的头节点;LTNode* phead = CreatListNode(-1);phead->next = phead;//next指向自己phead->prev = phead;//prev指向自己
//体现循环的特点return phead;//返回一个头节点;
}

逻辑简图如下:

2.3双向链表的销毁

//思考:为什么这里又是传的一级指针?
void LTDestroy(LTNode* phead)
{assert(phead);//断言,防止传空LTNode* cur = phead->next;//给cur赋值第一个节点的地址while (phead->next != phead)//找尾{//因为是循环,所以当节点的下一个节点为头节点,此时节点为尾节点//说明已经走完,就结束;LTNode* next = cur->next;//记住当前节点的下一个节点free(cur);//释放cur = next;//更新循环条件}free(phead);//释放头节点;//注意头节点是头节点,第一个节点是第一个节点哦,不要混淆了哦;//可参考开头的结构图哦
}

思考题:为什么这里又是传的一级指针?
**后面传的都是一级指针,因为以下原因:

访问链表节点

• 函数接收指向链表头节点的一级指针，就可通过该指针访问链表的各个节点，进而操作节点的数据和指针域。例如要遍历链表打印所有节点数据，只需通过传入的头指针依次访问每个节点。

修改节点内容

• 通过一级指针可直接修改节点的数据内容。如要将链表中某个节点的数据值从10改为20，可利用一级指针找到该节点并修改其数据域。

保持操作的简洁性

• 对于一些不改变链表结构，仅对节点数据或指针进行简单操作的函数，传一级指针能使代码简洁清晰。如获取链表节点个数的函数，仅需顺着一级指针遍历链表计数即可。

与其他数据结构操作统一

• 在很多数据结构操作中，常使用一级指针来表示数据结构的起始位置或当前操作位置。使用一级指针操作双向带头循环链表，能与其他数据结构的操作方式保持一致，便于开发者理解和使用。

不过，在某些需要修改链表头指针本身，如创建新链表或进行链表合并等操作时，可能需要传递二级指针或使用指针的引用，以确保能正确修改头指针的指向。那都是特殊情况啦,我们目前可以就考虑传一级指针啦!

2.4双向链表的打印

void LTPrint(LTNode* phead)
{assert(phead);printf("<=head<=>");//加入头的表示LTNode* cur = phead->next;while (cur != phead)//挨个遍历,直到回到头节点{printf("%d<=>", cur->data);cur = cur->next;//往下走}printf("\n");//防止多次调用,数据连在一起
}

2.5双向链表的是否为空判断

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;//如果头节点指向自己,说明为空
}

判空逻辑如图:

2.6双向链表的节点查找

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

前面的几篇已经多次讲述了查找啦,这里就不过多赘述啦!

2.7双向链表的尾插

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//逻辑代码LTNode* newNode = CreatListNode(x);LTNode* tail = phead->prev;//找尾//双向链表的好处,非常简单的找尾tail->next = newNode;newNode->prev = tail;newNode->next = phead;//双向链接phead->prev = newNode;//使用代码复用;//LTInsert(phead, x);//后面我们会讲
}

结合图进行理解

2.8双向链表的尾删

void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//逻辑代码LTNode* tail = phead->prev;//找尾LTNode* tailPrev = tail->prev;//找尾的前一个tailPrev->next = phead;//将头和尾的前一个链接phead->prev = tailPrev;free(tail);//释放尾tail = NULL;//置空,完成尾删//使用代码复用;//LTErase(phead->prev);
}

2.9双向链表的头插

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//逻辑代码LTNode* newNode = CreatListNode(x);//双向链接方法一//newNode->next = phead->next;//思考一下这个是如何实现头插的//phead->next->prev = newNode;//phead->next = newNode;//newNode->prev = phead;//双向链接方法二LTNode* first = phead->next;//先记第一个节点phead->next = newNode;//将第一个节点更新为新节点newNode->prev = phead;//双向链接newNode->next = first;//新第一个节点与旧第一个节点双向链接;first->prev = newNode;//使用代码复用;//LTInsert(phead->next, x);
}

图示如下:

2.10双向链表的头删

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//逻辑代码LTNode* first = phead->next;//记下第一个节点LTNode* firstNext = first->next;//记下第二个节点phead->next = firstNext;//头节点与第二个节点双向链接firstNext->prev = phead;free(first);//释放first = NULL;//置空,完成头删//使用代码复用;//LTErase(phead->next);
}

可以结合头插的图示分析一下,理顺逻辑;

2.11双向链表的中间插入

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = CreatListNode(x);//先将newNode的prev指针连接上pos的前一个,//此时有两个指针指向pos的前一个节点newNode->prev = pos->prev;pos->prev->next = newNode;//此时再断掉其与pos的链接,转而链接上newNodenewNode->next = pos;//再将newNode与pos双向链接;pos->prev = newNode;//LTNode* prev = pos->prev;//newNode->next = pos;//pos->prev = newNode;//newNode->prev = prev;//prev->next = newNode;
}

为什么说可以复用呢?
只要我传的位置是第一个节点的位置,是不是就是在第一个节点前插入,也就是头插,
只要我传的位置是头节点的位置,是不是就是在头节点前插入,也就是尾插,(因为是循环,所以头节点的前一个就是尾节点)

2.12双向链表的中间删除

//复用理由同上
void LTErase(LTNode* pos)
{assert(pos);LTNode* Prev = pos->prev;//找到pos前一个LTNode* Next = pos->next;//找到pos后一个Prev->next = Next;Next->prev = Prev;//两个双向链接free(pos);释放//pos = NULL;形参无法改变实参,pos置不置空都可以;//但是需要在test.c,即在使用中进行置空; 
}

2.13完整代码(使用了中间插入与中间删除的复用)

#define _CRT_SECURE_NO_WARNINGS 1#include"List.h"//双向链表的创建;
LTNode* CreatListNode(LTDataType x)
{LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL){perror("malloc fail");return NULL;}newNode->data = x;newNode->next = NULL;newNode->prev = NULL;return newNode;
}//双向链表的初始化;
LTNode* LTInit()
{LTNode* phead = CreatListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}//双向链表的销毁;
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (phead->next != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}//双向链表的打印
void LTPrint(LTNode* phead)
{assert(phead);printf("<=head<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}//双向链表的是否为空判断;
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//双向链表的节点查找;
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 LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//逻辑代码//LTNode* newNode = CreatListNode(x);//LTNode* tail = phead->prev;//tail->next = newNode;//newNode->prev = tail;//newNode->next = phead;//phead->prev = newNode;//使用代码复用;LTInsert(phead, x);
}//双向链表的尾删;
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//逻辑代码//LTNode* tail = phead->prev;//LTNode* tailPrev = tail->prev;//tailPrev->next = phead;//phead->prev = tailPrev;//free(tail);//tail = NULL;//使用代码复用;LTErase(phead->prev);
}//双向链表的头插;
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//逻辑代码//LTNode* newNode = CreatListNode(x);//newNode->next = phead->next;//phead->next->prev = newNode;//phead->next = newNode;//newNode->prev = phead;//LTNode* first = phead->next;//phead->next = newNode;//newNode->prev = phead;//newNode->next = first;//first->prev = newNode;//使用代码复用;LTInsert(phead->next, x);
}//双向链表的头删;
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//逻辑代码//LTNode* first = phead->next;//LTNode* firstNext = first->next;//phead->next = firstNext;//firstNext->prev = phead;//free(first);//first = NULL;//使用代码复用;LTErase(phead->next);
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = CreatListNode(x);newNode->prev = pos->prev;pos->prev->next = newNode;newNode->next = pos;pos->prev = newNode;//LTNode* prev = pos->prev;//newNode->next = pos;//pos->prev = newNode;//newNode->prev = prev;//prev->next = newNode;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* Prev = pos->prev;LTNode* Next = pos->next;Prev->next = Next;Next->prev = Prev;free(pos);//pos = NULL;形参无法改变实参,pos置不置空都可以;
}

那么接下来我们来看看测试吧

3.test.c

直接上完整代码:

#define _CRT_SECURE_NO_WARNINGS 1#include"List.h"void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopBack(plist);LTPopBack(plist);LTPrint(plist);LTPushFront(plist, 20);LTPushFront(plist, 40);LTPrint(plist);LTPopFront(plist);LTPopFront(plist);LTPrint(plist);LTPushFront(plist, 20);LTPushFront(plist, 40);LTNode* ret = LTFind(plist, 20);LTInsert(ret, 4000);LTPrint(plist);if (ret){LTErase(ret);ret = NULL;//自己来置空}LTPrint(plist);LTDestroy(plist);plist = NULL;//使用者来置空;}int main()
{TestList1();return 0;
}

---

五.双向链表的优缺点

优点

• 遍历灵活：既可以正向遍历，也可以反向遍历，能方便地访问当前节点的前驱和后继节点，在处理需要双向访问数据的问题时效率较高，比如实现双向链表的迭代器、文本编辑器中的撤销和重做功能等。
• 插入和删除高效：在已知节点位置的情况下，插入和删除操作的时间复杂度为O(1)。因为只需修改相关节点的指针，就能完成插入或删除，无需像顺序表那样移动大量元素，适用于频繁进行插入和删除操作的场景，如操作系统的进程调度、内存管理等。
• 内存利用率高：节点按需动态分配内存，可根据实际需求灵活调整链表长度，不会像数组那样预先分配大量连续内存空间而可能导致浪费，在处理数据量不确定的情况时优势明显，如网络数据包的存储和处理。
• 安全性好：有头节点作为链表的标识，且循环结构使链表形成一个闭环，在遍历或操作链表时，可有效避免出现空指针引用等错误，增强了程序的稳定性和可靠性。

缺点

• 结构复杂：每个节点需要额外存储前驱和后继指针，相比单链表，增加了实现和理解的难度，在编写代码时，对指针的操作和维护更复杂，容易出现指针操作错误，导致程序出现难以排查的bug。
• 空间开销大：除数据本身外，每个节点都要存储两个指针，对于大量数据存储，指针所占用的空间不容忽视，可能会降低内存的有效利用率，在内存资源紧张的环境中，可能会成为性能瓶颈。
• 随机访问效率低：要访问第n个节点，需从头部或尾部开始逐个节点遍历，时间复杂度为O(n)，远低于数组的随机访问效率O(1)，不适用于需要频繁随机访问元素的场景，如数组下标访问很方便的矩阵运算等。

六.顺序表与链表的比较

如图:

---

链表总结

• 链表作为基础且重要的数据结构，在程序设计中占据关键地位。本次博客对链表进行了深入剖析，从单链表出发，其通过节点间的指针连接实现数据存储，虽结构简单但在插入和删除操作上展现出O(1)的时间复杂度优势，无需像数组那样大量移动元素。

• 随着讨论深入，引入双向链表，它为每个节点增设前驱指针，赋予链表双向遍历能力，为特定场景提供了便利。而循环链表则通过让尾节点指向头节点，形成闭环，在循环处理数据等场景中有独特应用。

• 当然，链表也并非完美无缺，其随机访问效率低，需从头遍历查找元素，时间复杂度达O(n) ，且每个节点需额外存储指针，带来一定空间开销。理解链表的特性、操作方式及优缺点，能帮助我们在不同编程需求下做出明智的数据结构选择，为构建高效、稳定的程序奠定坚实基础。