【数据结构】C/C++ 带头双向循环链表保姆级教程（图例详解！！）

目录

一、前言

 二、链表的分类

 🥝单链表

 🥝双链表

 🥝循环链表

 🥝带头双向循环链表

 🍍头节点（哨兵位）的作用

 ✨定义：

 ✨作用：

 🍇总结

三、带头双向循环链表 和 单链表 的区别

 四、带头双向循环链表的实现

🍑概念详解

🍋带头双向循环链表的各个接口实现

✨初始化链表 

✨打印链表

✨插入节点

⚡ 头插 

⚡ 尾插 

⚡ 指定位置插入

⚡ 插入升级

 ✨删除结点

⚡头删

⚡尾删 

⚡指定位置删除

⚡删除升级

✨查找元素

 ✨链表判空

 ✨获取链表中的元素个数

 ✨销毁链表

 五、带头双向循环链表的完整代码

✨ List.h 

✨ List.c

✨ test.c

 六、顺序表与链表的区别

七、共勉

一、前言

在前两篇文章中，我们学习了 顺序表（数组） 和 单向不带头非循环 链表。
链接如下：
1️⃣：C/C++ 顺序表
2️⃣：C/C++ 单链表
那么今天，将要学习链表的第三种 双向带头循环链表。

 二、链表的分类

        在前面的文章也介绍过链表的基本情况，但是还是会有朋友分不清链表到底有哪几种，所以今天再来笼统的介绍一下。 
        其实 链表 一共分为 8 种类型，分别如下：

🥝单链表

        通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是 数据域，一个是 指针域（存放指向下一个节点的指针），最后一个节点的指针域指向 NULL（空指针的意思）。
       链接的入口节点称为链表的头结点也就是 head。

 如图所示：

 🥝双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

⭐：双链表 既可以向前查询也可以向后查询。

如图所示： 

 🥝循环链表

循环链表，顾名思义，就是链表 首尾相连。 一般用于解决 ---  约瑟夫环问题

 🥝带头双向循环链表

既然单链表也可以有循环链表，那么双向链表也不例外。

双向链表的 循环带头结点 的链表如下图所示👇

  • 由于这是带头双向循环链表，那么对于链表中的某一个节点 p，它的后继的前驱是谁？当然还是它自己。
  • 比如，在上图的带头双向循环链表中，节点 B 的前驱的后继，还是节点 B。
  • 即：p->next->prev == p == p->prev->next。（prev 表示 前驱指针，next 表示 后继指针）。
  • 这就好比：坐动车时，北京的下一站是天津，那么北京的下一站的前一站是哪里？哈哈哈，当然还是北京。

 这是就会有老铁产生疑问，那么这里的带头（哨兵位）是什么意思呢？它有什么所用呢？

 🍍头节点（哨兵位）的作用

 ✨定义：

头结点 也被称为 哨兵结点，可以用来简化边界条件。


它是一个附加的链表结点，该 结点 作为第一个节点，它的数据域不存储任何东西，只是为了操作的方便而引入的。


也就是说，如果一个链表有哨兵节点的话，那么链表表的第一个元素应该是链表的第二个节点。 

 ✨作用：

说了这么多，那它到底有什么用呢？ 

在很多时候，我们处理某个节点需要用到它的前驱节点。
 
比如删除链表的某个节点，对于没有哨兵的单链表，当待删除的节点为链表的第一个节点，由于没有前驱，需要进行特殊处理，从而代码的复杂性增加。
 
而如果有哨兵节点，则第一个节点的处理方式与其他节点相同，可以统一进行处理。

 🍇总结

        通过上面的 多种链表的结构 估计已经勾起了大家对链表的痛苦的回忆，肯定有老铁会问：这么多种结构，难道每一种链表结构都会经常用吗，我都需要掌握吗❓
       ⭐：我想告诉大家的是，在这8种结构中，虽然很多，但是大家只需要掌握 单链表 和 带头双向循环链表 这种两种结构 就可以应对链表的所有问题啦。

        那又会有老铁问，这两种结构有什么本质上的区别吗❓下面给大家继续解答。

三、带头双向循环链表 和 单链表 的区别

  区别1： 指针个数

带头双向循环链表：每个节点有两个指针，分别指向前一个节点和后一个节点；
单向链表：每个节点只有一个指针，指向下一个节点。

 区别2： 遍历方式

带头双向循环链表：可以从任意节点开始向前或向后遍历整个链表
单向链表：只能从头节点开始顺序遍历

 区别3：插入和删除操作

带头双向循环链表：插入和删除操作相对方便，因为可以直接调整前驱和后继节点的指针；

单向链表：在进行插入和删除时，需要更多的操作来调整节点之间的链接关系

 区别4：空间占用

带头双向循环链表：相较于单向链表需要额外的空间来存储每个节点的前驱指针。这在一些特定场景下可能会带来一定的开销。

  区别6：双向性

 带头双向循环链表：可以在节点内部通过前驱指针和后继指针来实现双向的遍历和操作。这使得在某些场景下，双向链表更加方便和高效，例如需要反向遍历链表或者需要在给定节点处进行插入和删除操作

   区别7：内存占用

带头双向循环链表：相对于单向链表，每个节点额外存储一个前驱指针和一个后继指针，使得双向链表在存储上需要更多的内存空间。这是一个需要考虑的因素，尤其是在链表节点数量较大或内存有限的情况下。 

 ⭐总结

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  • 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

 四、带头双向循环链表的实现

🍑概念详解

带头双向循环链表：带头双向循环链表也是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱

节点： 

  1. 我们把存储数据元素信息的域称为数据域。
  2. 存储数据元素之间的链接信息即下一个存储数据元素地址的部分称为指针域。
  3. 由数据域和指针域组成的数据元素A的存储映像称为节点。

 🍋带头双向循环链表的各个接口实现

✨初始化链表 

带头双向循环链表是单链表中扩展出来的结构，所以它的很多操作是和 单链表 相同的，甚至理解起来比单链表更简单。

首先，还是先定义一个结点类型，与单向链表相比，带头双向循环链表的结点类型中需要多出一个 前驱指针，用于指向前面一个结点，实现双向。

📝 代码示例 

typedef int Datetype;  // 存储的数据类型// 定义  -- 带头双向循环链表 的节点 ----
typedef struct ListNode
{Datetype data;           // 数据域struct ListNode* next;   // 后驱指针struct ListNode* prev;   // 前驱指针
}LN;
  •  在初始化之前，先申请一个 带哨兵位 的头结点，头结点的前驱和后继指针都指向自己，使得链表一开始便满足循环。然后再用一个 初始化函数 对链表进行初始化。

 📝 代码示例

// 新增一个节点
LN* BuyListNode(Datetype x)
{// 创建一个新的节点LN* newnode = (LN*)malloc(sizeof(LN));// 判断这个节点是否创建成功if (newnode == NULL){printf("malloc fail\n");exit(-1);  // 终止程序}// 节点创建成功，开始给节点赋值newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}// 带头双向循环链表的---初始化
LN* ListInit()
{// 创建一个头节点  这个头节点充当 --- 哨兵位---不存储有效数据LN* phead = BuyListNode(0);// 起始时只有头节点，让它的前驱和后继都指向自己// 使得链表一开始就满足循环phead->next = phead;phead->prev = phead;return phead;
}

注意：第一个是 头结点，也被称为 带哨兵位 的结点，它的数据域一般是不存放数据的

 ✨打印链表

 打印 带头双向循环链表 ，是从头结点的后一个结点处开始，向后遍历并打印，直到遍历到头结点处时便停止。

// 打印链表
// 注意：打印是从 哨兵位 的下一个节点开始打印
void ListPrint(LN* phead)
{//  防止为空链表assert(phead);printf("当前链表为：\n");printf("\n");printf("哨兵位<==>");// 从头结点的后一个结点开始打印LN* cur = phead->next;// 因为是循环链表 所以当 cur指针指向头节点的时候，说明已经打印结束while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("NULL");printf("\n");printf("\n");
}

 注意：第一个是 头结点，也被称为 带哨兵位 的结点，它是用来 站岗 的，所以不需要打印。

✨插入节点

带头双向循环链表的插入操作分为 3 种情况： 

（1）头插
（2）尾插
（3）在指定 pos 位置之前插入 

⚡ 头插 

进行头插时，需要申请一个新的结点，将 新结点 插入到 头结点 与 头结点的后一个结点 之间即可。

📝 代码示例 

// 头插
void ListPush_front(LN* phead, Datetype x)
{//  防止为空链表assert(phead);LN* front = phead->next;  // 头节点就是哨兵位的后驱指针LN* newnode = BuyListNode(x); // 申请一个结点，数据域赋值为x/*建立新结点与头结点之间的双向关系*/phead->next = newnode;newnode->prev = phead;//建立新结点与beHind结点之间的双向关系newnode->next = front;front->prev = newnode;// 头插--升级版// ListInsert(phead->next, x);
}

注意：第一个是 哨兵结点，所以不能在它的前面插入。 

 ⚡ 尾插 

尾插也是一样，申请一个新结点，将新结点插入到头结点和头结点的前一个结点之间即可。

因为链表是循环的，头结点的前驱指针直接指向最后一个结点，所以我们不必遍历链表找尾。

 📝 代码示例

// 尾插
void ListPush_back(LN* phead, Datetype x)
{//  防止为空链表assert(phead);LN* tail = phead->prev;  // 尾节点就是哨兵位的前驱指针LN* newnode = BuyListNode(x); // 申请一个结点，数据域赋值为x/*建立新结点与头结点之间的双向关系*/newnode->next = phead;phead->prev = newnode;/*建立新结点与tail结点之间的双向关系*/tail->next = newnode;newnode->prev = tail;// 尾插--升级版// ListInsert(phead, x);
}
⚡ 指定位置插入

 这里的指定插入，是在指定的 pos 位置的 前面 插入结点。

这里 pos 是指定位置的 地址，那么如何得到这个地址呢？很简单，需要用到上面的 查找函数。

然后，我们只需申请一个新结点插入到 指定位置结点 和其 前一个结点 之间即可。

 动图演示👇

📝 代码示例 

// 在pos位置的前面插入
void ListInsert(LN* pos, Datetype x)
{//  防止当前没有pos位置assert(pos);LN* posPrev = pos->prev; // 记录 pos 指向结点的前一个结点LN* newnode = BuyListNode(x); // 申请一个结点，数据域赋值为x/*建立新结点与posPrev结点之间的双向关系*/posPrev->next = newnode;newnode->prev = posPrev;/*建立新结点与pos指向结点之间的双向关系*/newnode->next = pos;pos->prev = newnode;
}
 ⚡ 插入升级

 我们仔细回顾一下，刚刚写的 头插 和 尾插，有没有发现什么规律呢？

没错，头插 其实就是在 哨兵结点 的 下一个结点 插入数据，所以我们可以用上面写的 ListInsert 函数来实现。

📝 代码升级 

// 头插
void ListPush_front(LN* phead, Datetype x)
{//  防止为空链表assert(phead);// 头插--升级版ListInsert(phead->next, x);
}

那么 尾插 呢？其实就是在 哨兵结点 的 前面 插入结点。 

 📝 代码升级

// 尾插
void ListPush_back(LN* phead, Datetype x)
{//  防止为空链表assert(phead);// 尾插--升级版// ListInsert(phead, x);
}

 ✨删除结点

双向链表的删除操作分为 3 种情况： 

（1）头删
（2）尾删
（3）在指定 pos 位置删除

 ⚡头删

头删，即释 哨兵结点 的后一个结点，并建立 哨兵结点 与 被删除结点的后一个结点 之间的双向关系即可。

 📝 代码示例

// 头删
void ListPop_front(LN* phead)
{// 防止为空链表assert(phead);// 防止哨兵位的下一个节点为空assert(phead->next != phead);LN* front = phead->next;     // 记录头结点的后一个结点LN* newfront = front->next;  // 记录after结点的后一个结点/*建立头结点与newAfter结点之间的双向关系*/phead->next = newfront;newfront->prev = phead;free(front);  // 释放front节点// 头删--升级版// ListErase(phead->next);
}
⚡尾删 

尾删，即释放最后一个结点，并建立 哨兵结点 和 被删除结点的前一个结点 之间的双向关系即可。 

 📝 代码示例

// 尾删
void ListPop_back(LN* phead)
{// 防止为空链表assert(phead);// 防止哨兵位的下一个节点为空assert(phead->next != phead);LN* tail = phead->prev;     // 记录头结点的前一个结点--尾节点LN* newtail = tail->prev;   // 记录tail结点的前一个结点free(tail);  //释放tail节点tail = NULL;/*建立头结点与newtail结点之间的双向关系*/newtail->next = phead;phead->prev = newtail;// 尾删--升级版// ListErase(phead->prev);
}
 ⚡指定位置删除

删除指定 pos 位置的结点，这里不是删除 pos 前面的结点，也不是删除 pos 后面的结点，而是删除 pos 地址的结点。

同样，释放掉 pos 位置的结点后，建立该结点前一个结点和后一个结点之间的双向关系即可。

动图演示👇 

📝 代码示例 

// 删除pos位置上的节点
void ListErase(LN* pos)
{// 防止pos位置为空assert(pos);LN* posprev = pos->prev;   // 记录pos指向结点的前一个结点LN* posnext = pos->next;   // 记录pos指向结点的后一个结点free(pos);                 //free是把指针指向的节点还给操作系统pos = NULL;/*建立posprev结点与posnext结点之间的双向关系*/posprev->next = posnext;posnext->prev = posprev;
}
 ⚡删除升级

 同样，对于 头删 和 尾删 还是可以进行简化。

头删 实际上就是删除 哨兵结点 的 下一个结点。

📝 代码升级 

// 头删
void ListPop_front(LN* phead)
{// 防止为空链表assert(phead);// 防止哨兵位的下一个节点为空assert(phead->next != phead);// 头删--升级版// ListErase(phead->next);
}

尾删 实际上就是删除 哨兵结点 的 前一个结点。 

📝 代码升级 

// 尾删
void ListPop_back(LN* phead)
{// 防止为空链表assert(phead);// 防止哨兵位的下一个节点为空assert(phead->next != phead);// 尾删--升级版// ListErase(phead->prev);
}

✨查找元素

给定一个值，在链表中寻找与该值相同的结点，若找到了，则返回结点地址；

若没有找到，则返回空指针（NULL）。

📝 代码示例 

// 查找元素
LN* ListFind(LN* phead, Datetype x)
{// 防止为空链表assert(phead);LN* cur = phead->next;    // 从哨兵位的后一个结点开始查找while (cur != phead)      // 当cur指向头结点时，遍历完毕{if (cur->data == x){return cur;       // 返回目标结点的地址}cur = cur->next;}return NULL;              // 没有找到目标结点
}

 ✨链表判空

当链表的 头结点的前驱 或是 后驱 指向的是自己时，即 双向链表为空。

换句话说，当只有 哨兵结点 时，链表为空。

📝 代码示例 

// 链表判空  结果为1 是空   
bool ListEmpty(LN* phead)
{// 防止为空链表assert(phead);return phead->next == phead;    // 当链表中只有哨兵位时为空
}

 ✨获取链表中的元素个数

获取链表中的元素个数，即遍历一次链表，统计结点的个数（哨兵结点 不纳入总数）并返回即可。

 📝 代码示例

// 获取链表中元素的个数
int Listsize(LN* phead)
{// 防止为空链表assert(phead);int count = 0;  // 记录数据LN* cur = phead->next;  // 从头结点的后一个结点开始遍历while (cur != phead)    // 当cur指向头结点时，遍历完毕，头结点不计入总元素个数{count++;cur = cur->next;}return count;           //返回元素个数
}

 ✨销毁链表

 当链表使用完以后，要进行销毁。

销毁链表，从 哨兵结点 的 后一个结点 处开始向后遍历并释放结点，直到遍历到 哨兵结点 时，停止遍历并将 哨兵结点 也释放掉。

 📝 代码示例

// 销毁链表
void ListDestory(LN* phead)
{// 防止为空链表assert(phead);LN* cur = phead->next;   // 从哨兵位后一个结点开始释放空间while (cur != phead){LN* next = cur->next; // 释放之前先保存cur的后一个结点位置free(cur);cur = next;          // 把cur的下一个节点赋给cur}free(phead);           // 最后释放哨兵结点phead = NULL;
}

 五、带头双向循环链表的完整代码

✨ List.h 

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <stdbool.h>// 带头双向循环链表     ---- list 的原型typedef int Datetype;  // 存储的数据类型// 定义  -- 带头双向循环链表 的节点 ----
typedef struct ListNode
{Datetype data;           // 数据域struct ListNode* next;   // 后驱指针struct ListNode* prev;   // 前驱指针
}LN;// 初始化链表
LN* BuyListNode(Datetype x);  // 新增一个节点
LN* ListInit();               // 带头双向循环链表的---初始化
void ListPrint(LN* phead);    // 打印链表// 插入节点
void ListPush_back(LN* phead, Datetype x);         // 尾插
void ListPush_front(LN* phead, Datetype x);        // 头插
void ListInsert(LN* pos, Datetype x);              // 在pos位置的前面插入// 删除节点
void ListPop_front(LN* phead);                     // 头删
void ListPop_back(LN* phead);                      // 尾删
void ListErase(LN* pos);                           // 删除pos位置上的节点// 空间操作
bool ListEmpty(LN* phead);                         // 链表判空
int Listsize(LN* phead);                           // 获取链表中元素的个数
void ListDestory(LN* phead);                       // 销毁链表
LN* ListFind(LN* phead, Datetype x);               // 查找元素

 ✨ List.c

#include "list.h"// 新增一个节点
LN* BuyListNode(Datetype x)
{// 创建一个新的节点LN* newnode = (LN*)malloc(sizeof(LN));// 判断这个节点是否创建成功if (newnode == NULL){printf("malloc fail\n");exit(-1);  // 终止程序}// 节点创建成功，开始给节点赋值newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}// 带头双向循环链表的---初始化
LN* ListInit()
{// 创建一个头节点  这个头节点充当 --- 哨兵位---不存储有效数据LN* phead = BuyListNode(0);// 起始时只有头节点，让它的前驱和后继都指向自己// 使得链表一开始就满足循环phead->next = phead;phead->prev = phead;return phead;
}// 打印链表
// 注意：打印是从 哨兵位 的下一个节点开始打印
void ListPrint(LN* phead)
{//  防止为空链表assert(phead);printf("当前链表为：\n");printf("\n");printf("哨兵位<==>");// 从头结点的后一个结点开始打印LN* cur = phead->next;// 因为是循环链表 所以当 cur指针指向头节点的时候，说明已经打印结束while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("NULL");printf("\n");printf("\n");
}// 尾插
void ListPush_back(LN* phead, Datetype x)
{//  防止为空链表assert(phead);LN* tail = phead->prev;  // 尾节点就是哨兵位的前驱指针LN* newnode = BuyListNode(x); // 申请一个结点，数据域赋值为x/*建立新结点与头结点之间的双向关系*/newnode->next = phead;phead->prev = newnode;/*建立新结点与tail结点之间的双向关系*/tail->next = newnode;newnode->prev = tail;// 尾插--升级版// ListInsert(phead, x);
}// 头插
void ListPush_front(LN* phead, Datetype x)
{//  防止为空链表assert(phead);LN* front = phead->next;  // 头节点就是哨兵位的后驱指针LN* newnode = BuyListNode(x); // 申请一个结点，数据域赋值为x/*建立新结点与头结点之间的双向关系*/phead->next = newnode;newnode->prev = phead;//建立新结点与beHind结点之间的双向关系newnode->next = front;front->prev = newnode;// 头插--升级版// ListInsert(phead->next, x);
}// 在pos位置的前面插入
void ListInsert(LN* pos, Datetype x)
{//  防止当前没有pos位置assert(pos);LN* posPrev = pos->prev; // 记录 pos 指向结点的前一个结点LN* newnode = BuyListNode(x); // 申请一个结点，数据域赋值为x/*建立新结点与posPrev结点之间的双向关系*/posPrev->next = newnode;newnode->prev = posPrev;/*建立新结点与pos指向结点之间的双向关系*/newnode->next = pos;pos->prev = newnode;
}// 头删
void ListPop_front(LN* phead)
{// 防止为空链表assert(phead);// 防止哨兵位的下一个节点为空assert(phead->next != phead);LN* front = phead->next;     // 记录头结点的后一个结点LN* newfront = front->next;  // 记录after结点的后一个结点/*建立头结点与newAfter结点之间的双向关系*/phead->next = newfront;newfront->prev = phead;free(front);  // 释放front节点// 头删--升级版// ListErase(phead->next);
} // 尾删
void ListPop_back(LN* phead)
{// 防止为空链表assert(phead);// 防止哨兵位的下一个节点为空assert(phead->next != phead);LN* tail = phead->prev;     // 记录头结点的前一个结点--尾节点LN* newtail = tail->prev;   // 记录tail结点的前一个结点free(tail);  //释放tail节点tail = NULL;/*建立头结点与newtail结点之间的双向关系*/newtail->next = phead;phead->prev = newtail;// 尾删--升级版// ListErase(phead->prev);
}// 删除pos位置上的节点
void ListErase(LN* pos)
{// 防止pos位置为空assert(pos);LN* posprev = pos->prev;   // 记录pos指向结点的前一个结点LN* posnext = pos->next;   // 记录pos指向结点的后一个结点free(pos);                 //free是把指针指向的节点还给操作系统pos = NULL;/*建立posprev结点与posnext结点之间的双向关系*/posprev->next = posnext;posnext->prev = posprev;
}// 链表判空  结果为1 是空   
bool ListEmpty(LN* phead)
{// 防止为空链表assert(phead);return phead->next == phead;    // 当链表中只有哨兵位时为空
}// 获取链表中元素的个数
int Listsize(LN* phead)
{// 防止为空链表assert(phead);int count = 0;  // 记录数据LN* cur = phead->next;  // 从头结点的后一个结点开始遍历while (cur != phead)    // 当cur指向头结点时，遍历完毕，头结点不计入总元素个数{count++;cur = cur->next;}return count;           //返回元素个数
}// 销毁链表
void ListDestory(LN* phead)
{// 防止为空链表assert(phead);LN* cur = phead->next;   // 从哨兵位后一个结点开始释放空间while (cur != phead){LN* next = cur->next; // 释放之前先保存cur的后一个结点位置free(cur);cur = next;          // 把cur的下一个节点赋给cur}free(phead);           // 最后释放哨兵结点phead = NULL;
}// 查找元素
LN* ListFind(LN* phead, Datetype x)
{// 防止为空链表assert(phead);LN* cur = phead->next;    // 从哨兵位的后一个结点开始查找while (cur != phead)      // 当cur指向头结点时，遍历完毕{if (cur->data == x){return cur;       // 返回目标结点的地址}cur = cur->next;}return NULL;              // 没有找到目标结点
}

✨ test.c

void menu()
{printf("*******************欢迎使用双向带头循环链表******************\n");printf("*************            1.   尾插            *************\n");printf("*************            2.   头插            *************\n");printf("*************            3.   尾删            *************\n");printf("*************            4.   头删            *************\n");printf("*************            5.查询pos位置        *************\n");printf("*************            6.在pos位前插入元素x  *************\n");printf("*************            7.删除pos位置的元素   *************\n");printf("*************            8.打印链表           ************* \n");printf("*************           -1.退出链表           ************* \n");printf("***********************************************************\n");LN* pList = ListInit();int option = -1;do{printf("请输入选项:> ");scanf("%d", &option);if (option == 1){int x = 0;printf("请输入你要尾插的元素:>");scanf("%d", &x);ListPush_back(pList, x);}else if (option == 2){int x = 0;printf("请输入你要头插的数字:>");scanf("%d", &x);ListPush_front(pList, x);}else if (option == 3){//尾删ListPop_back(pList);}else if (option == 4){//头删ListPop_front(pList);}else if (option == 5){int x = 0;printf("请输入你要查找的值x:>");scanf("%d", &x);LN* pos = ListFind(pList, x);if (pos != NULL){printf("存在数字%d\n", x);}else{printf("未找到数字%d\n", x);}}else if (option == 6){int x = 0;int y = 0;printf("请分别输入pos值x和pos前所插入的值y:>");scanf("%d %d", &x, &y);LN* pos = ListFind(pList, x);if (pos != NULL){ListInsert(pos, y);}else{printf("该链表不存在%d\n", x);}}else if (option == 7){int x = 0;printf("请输入要删除pos位置的值:>");scanf("%d", &x);LN* pos = ListFind(pList, x);ListErase(pos);}else if (option == 8){printf("\n");ListPrint(pList);}} while (option != -1);ListDestory(pList);}int main()
{menu();return 0;
}

 六、顺序表与链表的区别

 顺序表 与 链表 的优缺点：

优点缺点
顺序表1. 物理空间是连续的，方便用下标随机访问。
2. CPU高速缓存命中率会更高。		1. 由于需要物理空间连续，空间不够需要扩容。其次扩容机制还存在一定的空间浪费。
2. 头部或者中部插入、删除、挪动数据效率低 O(N)。
链表1、按需申请和释放空间。
2. 任意位置插入、删除数据效率高 O(1)。		1. 不支持下标的随机访问。有些算法不适合在它上面进行。如：二分、排序等

七、共勉

        以下就是我对 带头双向循环链表 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 C++ list 的理解，请持续关注我哦！！！     

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/3016546.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

一键解密，网络安全神器现已问世！

一键解密，网络安全神器现已问世！

一、简介 当前版本V1.1这款工具是一款功能强大的网络安全综合工具&#xff0c;旨在为安全从业者、红蓝对抗人员和网络安全爱好者提供全面的网络安全解决方案。它集成了多种实用功能&#xff0c;包括解密、分析、扫描、溯源等&#xff0c;为用户提供了便捷的操作界面和丰富的功…
阅读更多...
Python Dash库：一个Web应用只需几行代码

Python Dash库：一个Web应用只需几行代码

大家好&#xff0c;在数据科学领域&#xff0c;数据可视化是将数据以图形化形式展示出来&#xff0c;帮助我们更直观地理解数据。Python中有一个非常流行的数据可视化库叫做Dash&#xff0c;Dash以其简洁、高效和强大的功能而闻名&#xff0c;它允许开发者快速构建交互式Web应用…
阅读更多...
Offline：IQL

Offline：IQL

ICLR 2022 Poster Intro 部分离线强化学习的对价值函数采用的是最小化均方bellman误差。而其中误差源自单步的TD误差。TD误差中对target Q的计算需要选取一个max的动作&#xff0c;这就容易导致采取了OOD的数据。因此&#xff0c;IQL取消max,&#xff0c;通过一个期望回归算子…
阅读更多...
STM32接入CH340芯片的初始化进入升级模式（死机）问题处理

STM32接入CH340芯片的初始化进入升级模式（死机）问题处理

目录 1. 问题描述2. 问题分析2.1 CH340G/K 的初始化波形2.2 第1种USB升级电路2.3 第2种USB升级电路2.4 第3种USB升级电路2.5 第4种USB升级电路 3. 总结 1. 问题描述 我所用的CH340G&#xff08;CH340K也用过&#xff09;接在MCU的电路中&#xff0c;在插入CH340G/K 的接插件&a…
阅读更多...
【一刷《剑指Offer》】面试题 16：反转链表

【一刷《剑指Offer》】面试题 16：反转链表

力扣对应题目链接&#xff1a;206. 反转链表 - 力扣&#xff08;LeetCode&#xff09; 牛客对应题目链接&#xff1a;反转链表_牛客题霸_牛客网 (nowcoder.com) 核心考点 &#xff1a;链表操作&#xff0c;思维缜密程度。 一、《剑指 Offer》内容 二、分析题目 解题思路&#…
阅读更多...
程序员的实用神器：助力软件开发的利器 ️

程序员的实用神器：助力软件开发的利器 ️

程序员的实用神器&#xff1a;助力软件开发的利器 &#x1f6e0;️ 程序员的实用神器&#xff1a;助力软件开发的利器 &#x1f6e0;️引言摘要自动化测试工具&#xff1a;保障代码质量的利剑 &#x1f5e1;️编写高效测试用例 持续集成/持续部署工具&#xff1a;加速交付的利器…
阅读更多...
Richard 林旅强：说说社区的故事和对 RTE 社区的畅想

Richard 林旅强：说说社区的故事和对 RTE 社区的畅想

各位 RTE 开发者社区的小伙伴们&#xff0c;大家好&#xff1a; 我是 Richard 林旅强&#xff0c;今年起开始担任我们 RTE 社区联合主理人&#xff0c;很荣幸能在这里跟杜金房老师和陈靖老师一起做点事情&#xff0c;为社区的大家服务 &#x1f603; 今天想跟各位分享&#x…
阅读更多...
重学SpringBoot3-SPI机制

重学SpringBoot3-SPI机制

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-SPI机制 什么是 SPI&#xff1f;Spring Boot 中的 SPI 机制spring.factories 文件自动配置的实现启动流程中的作用 SPI实际应用步骤 1: 新建模块步骤 2:…
阅读更多...
[Java EE] 多线程(九):ReentrantLock,Semaphore,CountDownLatch与线程安全的集合类(多线程完结)

[Java EE] 多线程(九):ReentrantLock,Semaphore,CountDownLatch与线程安全的集合类(多线程完结)

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏:&#x1f355; Collection与数据结构 (91平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm1001.2014.3001.5482 &#x1f9c0;Java …
阅读更多...
一文读懂Python的`__init__`，`__init__`方法的终极指南

一文读懂Python的`__init__`，`__init__`方法的终极指南

大家好&#xff0c;今天给大家介绍一个Python中一个特殊的函数__init__。 在Python中&#xff0c;__init__方法是一个特殊的函数&#xff0c;它在创建类的新实例时自动调用。它的作用类似于其他编程语言中的构造函数&#xff0c;用于初始化对象的状态。这篇文章将带你深入了解…
阅读更多...
python实现的信号合成分析系统(DSP)

python实现的信号合成分析系统(DSP)

python实现的信号合成分析系统(DSP) 流程 1、在QT界面上设置好信号频率，采样频率，采样点数 2、使用np构建sin函数 3、使用matplotlib画出 4、分别分析合成信号的FFT频域信息1、效果图 2、示例代码 def btn_com_clicked(self):# 信号合成分析Fs = self.com_fs_edit_value #…
阅读更多...
【网络编程】http协议

【网络编程】http协议

预备知识 什么是http协议 HTTP&#xff08;Hypertext Transfer Protocol&#xff0c;超文本传输协议&#xff09;是一个应用层的协议&#xff0c;用于在网络中传输超文本&#xff08;如HTML文档&#xff09;。HTTP协议建立在TCP/IP协议之上&#xff0c;是Web浏览器和Web服务器…
阅读更多...
Map集合的实现类~HashMap

Map集合的实现类~HashMap

存储结构&#xff1a;哈希表 键重复依据是hashCode和equals方法&#xff08;键不能重复&#xff09; 添加&#xff1a; 先创建Student类&#xff0c;那么往HashSet添加的就是Student对象作为键值&#xff0c;后面的作为值 删除&#xff1a; 判断&#xff1a; 遍历&#xff1a…
阅读更多...
为什么要梯度累积

为什么要梯度累积

文章目录 梯度累积什么是梯度累积如何理解理解梯度累积梯度累积的工作原理 梯度累积的数学原理梯度累积过程如何实现梯度累积 梯度累积的可视化 梯度累积 什么是梯度累积 随着深度学习模型变得越来越复杂&#xff0c;模型的训练通常需要更多的计算资源&#xff0c;特别是在训…
阅读更多...
self-attention 的 CUDA 实现及优化 (上)

self-attention 的 CUDA 实现及优化 (上)

self-attention 的 CUDA 实现及优化 (上) 导 读 self-attention 是 Transformer 中最关键、最复杂的部分&#xff0c;也是 Transformer 优化的核心环节。理解 self-attention &#xff0c;对于深入理解 Transformer 具有关键作用&#xff0c;本篇主要就围绕 self-attention 展…
阅读更多...
java+jsp+Oracle+Tomcat 记账管理系统论文（完整版）

java+jsp+Oracle+Tomcat 记账管理系统论文（完整版）

⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️ ➡️点击免费下载全套资料:源码、数据库、部署教程、论文、答辩ppt一条龙服务 ➡️有部署问题可私信联系 ⬆️⬆️⬆️​​​​​​​⬆️…
阅读更多...
ThingsBoard版本控制配合Gitee实现版本控制

ThingsBoard版本控制配合Gitee实现版本控制

1、概述 2、架构 3、导出设置 4、仓库 5、同步策略 6、扩展 7、案例 7.1、首先需要在Giitee上创建对应同步到仓库地址 ​7.2、giit仓库只能在租户层面进行配置 7.3、 配置完成后&#xff1a;检查访问权限。显示已成功验证仓库访问&#xff01;表示配置成功 7.4、添加设…
阅读更多...
鸿蒙OpenHarmony南向：【Hi3516标准系统入门（命令行方式）】

鸿蒙OpenHarmony南向：【Hi3516标准系统入门（命令行方式）】

Hi3516标准系统入门&#xff08;命令行方式&#xff09; 注意&#xff1a; 从3.2版本起&#xff0c;标准系统不再针对Hi3516DV300进行适配验证&#xff0c;建议您使用RK3568进行标准系统的设备开发。 如您仍然需要使用Hi3516DV300进行标准系统相关开发操作&#xff0c;则可能会…
阅读更多...
【Linux】文件内容相关的命令，补充：管道符

【Linux】文件内容相关的命令，补充：管道符

1、查看文件内容 &#xff08;1-1&#xff09;查看文件内容&#xff1a;cat&#xff0c;tac&#xff0c;head&#xff0c;tail 查看文件内容cat 文件名查看文件内容并显示行号cat -n 文件名倒着查看文件内容&#xff08;从最后一行开始&#xff09;tac 文件名查看文件前10行…
阅读更多...
力扣hot100：543. 二叉树的直径/108. 将有序数组转换为二叉搜索树

力扣hot100：543. 二叉树的直径/108. 将有序数组转换为二叉搜索树

一、543. 二叉树的直径 LeetCode&#xff1a;543. 二叉树的直径 二叉树的直径 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。 遇到二叉树的问题很容易去直接用求解的目标去定义递归函数。但是仔细考虑&#xff0c;返回树的直径并不能向上传播。因此我们可以拆…
阅读更多...
最新文章

Copyright @ 2022~2023