-
【数据结构与算法】链表
😺概念
在上一篇文章本喵详细介绍了顺序表，在实现各个接口功能的时候，相信各位小伙伴也感受到了它存在很多不方便的地方，比如这些问题：
- 头插和在中间插入数据时，时间复杂度是O(N)
- 增容时按照每次增加2倍的方式来增加，会有不小的浪费。
而链表对顺序表的这些问题加以改善。
链表：是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
类似于上图的结构，data1到data5表示数据，每个data下面的数字是它们所占内存空间中的地址。- 每个数据的地址之间没有任何关系，不连续，也没有任何数量关系，这就是我概念中所说，在物理存储结构上非连续。
plist是指向data1的指针变量，我们称为头指针，每个数据下面地址都是下一个数据的地址- 我们用指针变量将每个数据连起来，前一个节点的指针指向下一个节点，这样它在逻辑上就是连续的了。
这样一个既有数据，又有指针变量的数据结构只能通过结构体来自定义
typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SLTNode;- 1
- 2
- 3
- 4
- 5
- 6
- 7
这样的一个结构体类型的变量称为一个节点。
- SLTDate x是该节点的数据
- struct SListNode* next是指向下一个节点的指针变量
我们在使用单链表的时候，只需要找到链表的头指针即可
SLTNode* plist = 头指针;- 1
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
-
单向、双向
-
带头、不带头
-
循环、非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
-
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
-
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
以上便是8种链表类型。
接下来本喵便重点介绍俩种链表结构。
😺无头单向非循环链表（单链表）
首先我们需要将节定义好，创建一个结构体类型
typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SLTNode;- 1
- 2
- 3
- 4
- 5
- 6
- 7
接着便开始实现各种接口函数
😼接口的实现
- 动态申请一个节点
//动态申请一个节点 SLTNode* BuySListNode(SLTDateType x) { SLTNode* str = (SLTNode*)malloc(sizeof(SLTNode));//开辟动态空间 //开辟失败返回空指针 if (str == NULL) { perror("malloc fail"); return NULL; } //开辟成功 str->data = x;//将数据存放在节点 str->next = NULL;//下一个节点为空 return str; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 链表的节点同样是存放在堆区上的，所以要使用malloc开辟动态内存空间
- 将要存放的数据放在节点处
- 由于不知道后面是否有节点，所以将指向下一个节点的指针设为空指针
- 打印链表
//打印链表 void SListPrint(const SLTNode* phead) { SLTNode* cur = phead;//一般不会动传进来的指针，以防混乱 while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 防止改变头指针，需要定义一个新的指针cur，此时cur中的值就是第一个节点的地址
- 将数据打印出来。为了更加形象，我们将数据用箭头连接起来
- cur指向下一个数据是通过取得本身结构体中下一个指针中的值实现的。
- 当打印到最后一个节点后，cur指针就会便成空，循环停下来
- 摧毁链表
//摧毁链表 void SListDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead;//用新指针指向第一个节点 //释放每个动态空间 while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } //将头指针置空 *pphead = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
在释放一个节点的时候需要用一个新的指针来存放下一个节点的地址，否则在当前节点被free释放以后，下一个节点就找不到了。- 释放以后，需要使头指针失忆，如果形参用一级指针接收，那么在函数中对头指针的改变并不影响本来头指针的值，就会造成野指针的问题。
- 所以形参使用二级指针来接收头指针的地址，通过解一次引用将头指针置空。
- 尾插（在链表的末尾处插入新节点）
//尾插 void SListPushBack(SLTNode** pphead, SLTDateType x) { assert(pphead); //原来没有节点 if (*pphead == NULL) { SLTNode* newnode = BuySListNode(x); *pphead = newnode;//头指针指向插入的节点 } else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = BuySListNode(x); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 如果链表为空的话，尾插一个节点时就需要将头指针指向这个节点，同样需要传二级指针
- 如果链表不是空，尾插一个节点时，需要通过头指针找到最后一个节点，将最后一个节点中的指针指向尾插的这个新节点。
- 头插（从链表开始处插入新节点）
//头插 void SListPushFront(SLTNode** pphead, SLTDateType x) { assert(pphead); //创建新节点 SLTNode* newnode = BuySListNode(x); //新节点中的指针指向原本第一个节点 newnode->next = *pphead; //头指针指向新节点 *pphead = newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- plist原本指向data1的节点
- 插入新节点后，需要让新节点中的指针指向原来的第一个节点，就像图中编号为1的绿色箭头
- 头指针需要指向新的节点，就像图中编号为2的绿色箭头
- 必须严格按照这个顺序，否则就会找不到原本的第一个节点
- 尾删（从链表末尾处删除节点）
//尾删 void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead != NULL);//链表为空，无法尾删，直接报错 SLTNode* tail = *pphead; //链表仅有一个节点 if (tail->next == NULL) { free(tail);//释放空间 *pphead = NULL;//头指针值向空 } else { //找到要删除的节点 while (tail->next->next) { tail = tail->next; } //释放掉，并且置为空指针 free(tail->next); tail->next = NULL; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
三种情况：
- 链表为空，此时无法删除，直接报错
- 链表中只有一个节点，将节点删除以后，头指针置为空
- 链表中有多个节点，需要找到链表中的最后一个节点
找到要删除的节点时，tail指向的是倒数第二个节点，将此节点钟的指针置为空
- 头删（从链表的其实位置删除节点）
//头删 void SListPopFront(SLTNode** pphead) { assert(pphead); //链表为空，直接报错 assert(*pphead != NULL); SLTNode* cur = *pphead; //只有一个节点 if (cur->next == NULL) { //释放空间 free(cur); //头指针置空 *pphead = NULL; } //有多个节点 else { //头指针指向删除后的新节点 *pphead = cur->next; free(cur); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
三种情况：
- 链表为空，直接报错
- 链表中只有一个节点，删除后，让头指针为空
- 链表中有多个节点，删除头指针指向的第一个节点，并且让头指针指向原本的第二个节点
- 查找（查找指定节点的位置）
//查找 SLTNode* SListFind(const SLTNode* phead, SLTDateType x) { SLTNode* cur = phead; //挨个寻找 while (cur) { if (cur->data == x) return cur;//找到返回当前节点的地址 cur = cur->next; } //链表中没有，返回空指针 return NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
俩种情况：
- 空链表，不可能找到，直接返回空指针
- 不是空链表，挨个循环比较，找到则返回节点地址，找不到返回空指针
- 指定位置插入节点
在pos前插入 ：
//指定位置前插入 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pphead); assert(pos); //相当于头插 if (*pphead == pos) SListPushFront(pphead, x); //中间插入 else { SLTNode* cur = *pphead; SLTNode* newnode = BuySListNode(x);//插入新节点 //找到指定位置 while (cur->next != pos) { cur = cur->next; } //找到此节点 if (cur->next != NULL) { cur->next = newnode;//新节点前面的节点的指针指向新节点 newnode->next = pos;//新节点的指针指向新节点后面的指针 } //没有找到此节点 else return; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 俩种情况
- 当指定位置是第一个节点时，此时相当于头插，直接调用头插函数就可以
- 当指定位置是链表中的某个节点时
新节点中的指针要指向指定位置的节点，原指定位置的前一个节点要指向新的节点。
在pos后插入 ：
//指定位置后插入 void SListInsert_After(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pphead); assert(pos); SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 同样在赋值指针的时候是不可以将顺序打乱的，否则会找不到新节点后面的地址
- 在指定位置后插入比在指定位置前插入便捷很多
- 指定位置删除节点
删除pos处节点 ：
//指定位置删除节点 void SListErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); //删除第一个节点 if (*pphead == pos) { SListPopFront(pphead); } //删除其他节点 else { if (pos->next == NULL) SListPopBack(pphead); //不是最后一个节点 else { SLTNode* cur = *pphead; //找到指定位置的前一个节点 while (cur->next != pos) { cur = cur->next; } //指定位置前一个节点指针指向指定位置下一个节点 cur->next = pos->next; free(pos); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
三种情况
- 指定位置是第一个节点时，相当于头删
- 指定位置是最后一个节点时，相当于尾删
- 指定位置是中间节点时，需要找到指定位置的前一个节点，让其指针指向删除位置的下一个节点
删除pos处之后的节点：
//指定位置删除节点 void SListErase_After(SLTNode* pos) { //指定位置不能是空，并且不能是最后一个节点 assert(pos&&(pos->next)); //指定位置指向下一个的下一个节点 pos->next = pos->next->next; free(pos->next); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 指定位置不能是最后一个节点，否则无法删除
删除后指定位置直接指向后面第二个节点。
各种接口已经全部介绍完，下面是SList.h中的代码
#pragma once #include#include #include typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SLTNode; //动态申请一个节点 SLTNode* BuySListNode(SLTDateType x); //打印链表 void SListPrint(const SLTNode* phead); //摧毁链表 void SListDestory(SLTNode** pphead); //尾插 void SListPushBack(SLTNode** pphead, SLTDateType x); //头插 void SListPushFront(SLTNode** pphead, SLTDateType x); //尾删 void SListPopBack(SLTNode** pphead); //头删 void SListPopFront(SLTNode** pphead); //查找 SLTNode* SListFind(const SLTNode* phead, SLTDateType x); //指定位置前插入 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x); //指定位置后插入 void SListInsert_After(SLTNode** pphead, SLTNode* pos, SLTDateType x); //指定位置删除节点 void SListErase(SLTNode** pphead, SLTNode* pos); //指定位置删除节点 void SListErase_After(SLTNode* pos); - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
优略分析:
上面的接口中，有的功能很方便，有的功能很繁琐，下面本喵来分析一下
- 繁琐的接口都有一个特征，就是需要利用循环来找节点，比如尾插，尾删，以及在指定位置之前插入节点，都需要找节点，而此时算法的时间复杂度是O(N)
- 也有一些功能是不用找节点的，比如头插头删，以及删除指定位置后面的一个节点，此时的时间复杂度就是O(1)
- 所以说，单链表适合头插头删，此时才优化了顺序表存在的问题，而其他功能用单链表并不合适。
😺带头双向循环链表
我们已经知道，单链表并不能完全的弥补顺序表的不足，那么接下来介绍的带头双向循环链表就可以完美弥补顺序表的不足。
我们再看它的结构
首先来说什么是带头:在单链表中也有头指针，但是和这里的头指针不一样，单链表的头指针只是一个结构体指针变量，只能存放一个地址，
而双向循环链表中的头也是一个结构体，为了加以区分，我们称这个头为哨兵头
typedef int LTDateType; typedef struct DListNode { struct DListNode* next; struct DListNode* prev; LTDateType x; }LTNode;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
这是头的结构体声明，可以看到，它有俩个结构体类型的指针变量，一个指向下一个节点，一个指向前一个节点，还有一个变量，但是这个变量是不存放值的，在很多地方都在这个值中方链表中节点个数，但是本喵认为这样是不妥的，原因如下：
- 我们这里的变量类型恰好是整型，所以可以放节点个数，那如果变量类型是char* 或者int* 类型的变量呢？
- 此时就无法在这个变量中存放节点个数了，除非将哨兵头重新定义为和节点不一样的结构体，专门有一个变量存放节点个数，但是为了统一，我们一般不这么干。
哨兵头的好处：
- 有哨兵头可以避免使用二级指针，当头节点发生变化时，单链表中的头指针就需要改变，而此时就需要利用解引用一次二级指针才能改变头指针。而哨兵头则只需要改变next指针变量的值就可以，传参传的也是一级结构体指针。
- 哨兵头中有俩个指针变量，可以指向俩个节点，这样才能够很方便的实现双循环，而单链表中的头指针只能指向一个节点，实现双循环很复杂。
接下来看接每个节点有什么不同：
带头双向循环链表中的每个节点都是和哨兵头一样的结构体类型的变量，只是节点结构体中的变量存放我们要在链表中储存的值。
指针prev指向前一个节点，我们不再需要像单链表那样使用时间复杂度是O(N)的方法找前一个节点了。
指针next指向下一个节点，和单链表一样。其中，
- 末尾节点处的指针变量next指向哨兵头
- 哨兵头处的指针变量prev指向末尾处的节点
😼接口的实现
带头双向循环链表看着结构非常复杂，但是在实现了以后，使用起来极其的方便。
- 初始化（创建哨兵头）
//初始化 LTNode* ListInit() { //创建头节点 LTNode* gurd = (LTNode*)malloc(sizeof(LTNode)); if (gurd == NULL) { perror("malloc fail"); return NULL; } //赋初值 gurd->next = gurd; gurd->prev = gurd; gurd->x = 0; return gurd; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
在只有哨兵头的时候，为了仍然达到双向循环的目的
- 哨兵头的next指针指向它自己
- 头兵头的prev指针指向它自己
这样一个最小的双向循环便构成了，接下来就是往这个结构来插入节点。
- 增加新节点
//增加新节点 LTNode* BuyListNode(LTDateType x) { //创建新节点 LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("Buy malloc fail"); return NULL; } //将俩个指针初始为空 node->next = NULL; node->prev = NULL; //将数据存储进链表 node->data = x; return node; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
在创建好新的节点后，我们并不知道该节点的前一个和后一个分别是什么，为了避免野指针，我们将指针next和prev都置为空指针，将要存储的值放入节点。
- 打印链表
//打印链表 void ListPrint(LTNode* phead) { assert(phead); //指向第一个节点（不包括哨兵头） LTNode* cur = phead->next; printf("phead <=> "); while (cur != phead) { printf("%d <=> ", cur->data); cur = cur->next; } printf("phead\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
链表中的节点不包括哨兵头
所以我们从第一个节点开始循环打印，由于是双向循环，所以在打印完最后一个节点后还会回到哨兵头，所以我们就限制它在循环回哨兵头的位置停止打印。
- 摧毁链表
//摧毁链表 void ListDestroy(LTNode* phead) { assert(phead); //指向第一个节点 LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next;//记录下一个节点，防止释放后找不到 free(cur);//释放当前节点 cur = next;//指向下一个节点 } free(phead); phead = NULL;//处于好习惯的角度，实际没有意义 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
同样这里需要提前记录下一个节点
上图，我们删除的是cur指向的节点- 我们释放的是cur指向的节点，如果直接释放掉，这个节点中的内容就都没有了，包括指针next，所以当我们要找下一个节点的时候就找不到了
- 我们要先找到下一个节点，并记录下来，然后再释放当前节点，将指向下一个节点，如此往复循环
- 因为是双向循环链表，所以要控制在循环到哨兵头的时候停下来，在单独释放哨兵头
前期的铺垫接口已经做好，接下就是插入删除数据了。
- 尾插（从链表尾部插入数据）
//尾插 void ListPushBack(LTNode* phead, LTDateType x) { assert(phead); //创建新节点 LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev;//找到原本的尾节点 newnode->next = phead; phead->prev = newnode; newnode->prev = tail; tail->next = newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
每插入一个新节点需要改变四个指针
可以看到，蓝色的线有四根，代表着改变了四个指针的指向关系- 步骤3必须在步骤4的前面，否则就会找不到原本的尾节点
在这里我们创建一个tail尾指针记录原本的尾节点，这样就不用考虑改变指针指向关系的顺序了。
- 新尾节点的next指向哨兵头
- 原尾节点的next指向新尾节点
- 新尾节点的prev指向原本尾节点
- 哨兵头的prev指向新的尾节点
在插入时，不用考虑原链表是否是空，因为至少都有哨兵头，如果是空链表的话，哨兵头自成循环，插入时往循环里插就可以，逻辑是相同的。
- 尾删（从链表的末尾处删除数据）
//尾删 void ListPopBack(LTNode* phead) { assert(phead); //找到原本的尾节点 assert(phead->next != phead);//判断链表是否为空，空直接报错 LTNode* tail = phead->prev; phead->prev = tail->prev;//哨兵头的prev指向尾节点的前一个节点 tail->prev->next = phead;//尾节点的前一个节点的next指向哨兵头 free(tail); tail = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
删除尾节点的时候，需要改变俩个指针的指向关系
这里我们为了不发生混乱，使用方便，同样用一个tail指针记录原本的尾节点- 新尾节点的next指向哨兵头
- 哨兵头的prev指向新尾节点
注意：
尾删时要注意是否是空链表，如果是空链表则不能删除，使用*哨兵头的next指向的是否是自己判断是否是空链表
- 头插（在哨兵头后面插入新节点）
//头插 void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); //创建新节点 LTNode* newnode = BuyListNode(x); //记录原本第一个节点 LTNode* cur = phead->next; newnode->next = cur;//新节点的next指向原本的第一个节点 cur->prev = newnode;//原本第一个节点的prev指向新节点 phead->next = newnode;//哨兵头的next指向新节点 newnode->prev = phead;//新节点的prev指向哨兵头 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
同样需要修改四个指针的指向关系
为了不发生混乱，我们将原本的第一个节点用cur记录下来- 新节点的next指向原本的第一个节点
- 原本第一个节点的prev指向新节点
- 哨兵头的next指向新节点
- 新节点的prev指向哨兵头
同样在插入时，不用考虑原链表是否是空，因为至少都有哨兵头，如果是空链表的话，哨兵头自成循环，插入时往循环里插就可以，逻辑是相同的。
- 头删（删除哨兵头后的第一个节点）
//头删 void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead);//判断链表是否为空，空直接报错 LTNode* cur = phead->next;//记录当前头节点 LTNode* next = cur->next;//记录头节点的下一个节点 phead->next = next;//头指针的next指向头节点的下一个节点 next->prev = phead;//头节点的下一个节点的prev指向哨兵头 free(cur);//释放 cur = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
同样需要修改俩个指针的指向关系
为了不混乱，将头节点的下一个节点记录在next中- 头指针的next指向头节点的下一个节点
- 头节点的下一个节点的prev指向哨兵头
注意：
头删时要注意是否是空链表，如果是空链表则不能删除，使用*哨兵头的next指向的是否是自己判断是否是空链表
- 查找某一数据
//查找某一数据 LTNode* ListFind(LTNode* phead, LTDateType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
从头节点开始挨个变量寻找与x相等的数，找到则返回当前节点的地址，找不到则返回空指针。
- 通过控制当前指针是否指向哨兵头来控制循环结束
- 指定位置插入
//指定位置插入 void ListInsert(LTNode* pos, LTDateType x) { assert(pos);//防止指定位置为空 //记录指定位置前一个节点 LTNode* prev = pos->prev; //创建新节点 LTNode* newnode = BuyListNode(x); newnode->next = pos;//新节点的next指向指定位置 pos->prev = newnode;//指定位置的prev指向新节点 prev->next = newnode;//指定位置前一个节点的next指向新节点 newnode->prev = prev;//新节点的前一个位置指向指定位置的前一个节点 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
这里同样需要修改四个指针的指向关系
为了不混乱，我们用prev记录指定位置的前一个节点- 新节点的next指向指定位置
- 指定位置的prev指向新节点
- 指定位置前一个节点的next指向新节点
- 新节点的前一个位置指向指定位置的前一个节点
这里我们看一下当指定位置是第一个节点的情况
此时记录前一个节点的指针prev指向的是哨兵头，逻辑和其他位置的插入是一样。并且- 指定位置是第一个节点时，和头插的效果是一样的，所以我们可以用插入指定位置来代替头插。
//头插 void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); 创建新节点 //LTNode* newnode = BuyListNode(x); 记录原本第一个节点 //LTNode* cur = phead->next; //newnode->next = cur;//新节点的next指向原本的第一个节点 //cur->prev = newnode;///原本的prev指向新节点 //phead->next = newnode;//哨兵头的next指向新节点 //newnode->prev = phead;//新节点的prev指向哨兵头 ListInsert(phead->next, x); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
我们之前实现的头插接口中调用指定位置插入的函数，此时指定位置就是第一个节点，就可以实现头插的功能。同样的，尾插也可以利用该函数实现。
- 指定位置删除
//指定位置删除 void ListErase(LTNode* pos) { assert(pos); LTNode* next = pos->next;//记录指定位置的下一个节点 LTNode* prev = pos->prev;//记录指定位置的前一个节点 prev->next = next;//指定位置前一个节点的next指向指定位置的下一个节点 next->prev = prev;//指定位置下一个节点的prev指向指定位置的前一个节点 free(pos);//释放 pos = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
同样需要修改俩个指针的指向关系
为了避免混乱，我们用next记录指定位置的下一个节点，用prev记录指定位置的上一个节点- 指定位置前一个节点的next指向指定位置的下一个节点
- 指定位置下一个节点的prev指向指定位置的前一个节点
同样，我们可以利用指定位置删除实现头删以及尾删
void ListPopFront(LTNode* phead) { //assert(phead); //assert(phead->next != phead);//判断链表是否为空，空直接报错 //LTNode* cur = phead->next;//记录当前头节点 //LTNode* next = cur->next;//记录头节点的下一个节点 //phead->next = next;//头指针的next指向头节点的下一个节点 //next->prev = phead;//头节点的下一个节点的prev指向哨兵头 //free(cur);//释放 //cur = NULL; ListErase(phead->next); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
指向将指定位置传参为第一个节点的位置，尾删本喵就不给大家演示了。
- 统计节点个数（不包括哨兵头)
//统计个数 int ListSize(LTNode* phead) { assert(phead); int count = 0; LTNode* cur = phead->next;//指向第一个节点 while (cur != phead) { count++; cur = cur->next; } return count; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
个数的统计就相当简单了，本喵就不阐述了。
最后本喵展示一下List.h中的代码：
#pragma once #include#include #include typedef int LTDateType; typedef struct DListNode { struct DListNode* next; struct DListNode* prev; LTDateType data; }LTNode; //初始化 LTNode* ListInit(); //增加新节点 LTNode* BuyListNode(LTDateType x); //打印链表 void ListPrint(LTNode* phead); //摧毁链表 void ListDestroy(LTNode* phead); //尾插 void ListPushBack(LTNode* phead, LTDateType x); //尾删 void ListPopBack(LTNode* phead); //头插 void ListPushFront(LTNode* phead, LTDateType x); //头删 void ListPopFront(LTNode* phead); //查找某一数据 LTNode* ListFind(LTNode* phead, LTDateType x); //指定位置插入 void ListInsert(LTNode* pos, LTDateType x); //指定位置删除 void ListErase(LTNode* pos); //统计个数 int ListSize(LTNode* phead); - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
小结:
- 插入：不管是什么类型的插入，都需要修改四个指针的指向关系
- 删除：不管是什么类型的删除，都需要修改俩个指针的指向关系
- 在修改指针的指向关系时，有时必须按照一定的顺序来修改，否则会发生找不到其他节点的困境，为了更加方便，我们可以提前记录一些节点，比如尾节点tail，前一个节点prev，下一个节点next
我们在实现上诉各个接口的时候，除了在找指定元素以及在个数统计的时候算法的时间复杂度是O(N)，其他各种插入以及删除的时间负责度都是O(1)，包括空间复杂度也是O(1)，这就是带头双向循环链表的强大之处，它完美的弥补了顺序表以及单链表的不足。
😺顺序表和链表的区别
不同点 顺序表 链表(带头双向循环链表) 存储空间上 物理上和逻辑上都连续 逻辑上连续，物理上不连续 访问指定位置 可以直接访问，时间复杂度是O(1) 不可以直接访问，需要寻找，时间复杂度是O(N) 任意位置插入或者删除元素 可能需要搬移多个数据，效率低，时间复杂度O(N) 只需修改指针指向，时间复杂度O(1) 插入多个数据 容量不够需要扩容，可能造成空间浪费 用多少申请多少，不存在浪费，也不存在容量不够 应用场景 数据高效储存 + 高频访问 任意位置插入和删除 缓存利用率 高 低 可以看到，顺序表的缺点正好被链表弥补，而链表的缺点也正好被顺序表弥补，它们俩相辅相成。
😼缓存利用率
在上面表格的最后一行有一个缓存利用率，这是一个什么呢？本喵在这里介绍一下。
这是储存器层次结构，越往上，访问速度越快，但是造价也就越高，所以也就越小。- 有三个高速缓存，从L1到L3的存储空间依次增大，但相比于内存的大小还是很小
- 主存就是我们平时所说的内存，包括栈区，堆区，静态区，常量区等等。
- 二级缓冲就是硬盘。
CPU是通过它周围的寄存器来访问内存中的数据的，假设我们要访问内存中的整型数据a，它会经历如下流程：
- CPU让寄存器去高速缓冲L1中取数据a，如果有（也叫做命中）则读取到了，如果没有，L1就会去高速缓冲L2中取，重复上面的过程直到L3。
- 如果整个高速缓存都没有数据a，就会去主存也就是内存中取，此时CPU处于一个等待状态，当内存中的整型数据a被高速缓存拿走后，CPU再将其拿走。
形象点就像下面这张图一样
非常形象的表达出来它们几个储存空间的关系。那么，为什么顺序表的缓存利用率高呢？
我们知道，当高速缓存中没有CPU想要的数据的时候，CPU会等待高速缓存区内存中取数据，如果每次CPU想要的数据高速缓存都没有，都需要CPU等着它取来，这样CPU工作的效率岂不是非常低？大多数处于等待状态？
其实不然，当高速缓存去内存中取数据时并不是只取一个数据，而是将它周围的数据全部取到高速缓存中(具体取多数由硬件决定)，以备CPU使用。
我们知道，顺序表在内存中的物理地址是连续的
- 高速缓存在内存中取顺序表中的某个数时，会将这个数周围的其他数据也取走，这些数就会包括顺序表中的其他数据。
- 当CPU访问顺序表中的下一个数据的时候，可以直接从高速缓存中拿走，这样就不用等待高速缓存去内存中拿了，效率就会很高。
而链表在内存中的物理地址不是连续的，是通过指针才在逻辑上连续在一起的
- 高速缓存在内存中取链表中的某个数据时，同样会将周围的其他数据也取走，但是这些数据很大概率不会包括链表中的其他数据，因为每个节点直接并不一定挨着。
- 当CPU访问链表中的下一个数据时，很可能在高速缓存中是没有的，此时就需要高速缓存再去内存中取数，CPU继续等待，如此一来，效率就低了。
这就是顺序表高速缓存利用率比链表高的原因。
😺总结
我们在使用链表时虽然大部分时候都是使用带头双向循环链表，但是单链表是任何一种类型链表的基础，它也经常作为其他数据结构的子结构在使用，所以也要重视。
链表虽然可以完美弥补顺序表存的问题，但是它也不是十全十美的，它们各有各的优势所在，我们在使用的时候要扬长避短，这样我们的代码才会有更高的质量。
最后，希望可以对各位有所帮助。 -
相关阅读:
Python面向对象三大特征
基于javaScript+html+sql的假期留校宿舍管理系统设计与实现
数学建模论文六大获奖技巧总结（想得奖的进来看）
2023秋招—大数据开发面经—杰创智能科技
实现两栏布局的五种方式
IO流高级流
2022年国内云管平台厂商哪家好？为什么？
Spring Boot Actuator 模块，spring-boot-starter-actuator
【Blender】Blender入门学习
自然语言处理 | 语言模型(LM) 浅析
- 原文地址：https://blog.csdn.net/weixin_63726869/article/details/126095880
