目录
一、前言
二、链表的分类
🥝单链表
🥝双链表
🥝循环链表
🥝带头双向循环链表
🍍头节点（哨兵位）的作用
✨定义：
✨作用：
🍇总结
三、带头双向循环链表 和 单链表 的区别
四、带头双向循环链表的实现
🍑概念详解
🍋带头双向循环链表的各个接口实现
✨初始化链表
✨打印链表
✨插入节点
⚡ 头插
⚡ 尾插
⚡ 指定位置插入
⚡ 插入升级
✨删除结点
⚡头删
⚡尾删
⚡指定位置删除
⚡删除升级
✨查找元素
✨链表判空
✨获取链表中的元素个数
✨销毁链表
五、带头双向循环链表的完整代码
✨ 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：内存占用
带头双向循环链表：相对于单向链表，每个节点额外存储一个前驱指针和一个后继指针，使得双向链表在存储上需要更多的内存空间。这是一个需要考虑的因素，尤其是在链表节点数量较大或内存有限的情况下。
⭐总结
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
四、带头双向循环链表的实现
🍑概念详解
带头双向循环链表：带头双向循环链表也是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱
节点：
- 我们把存储数据元素信息的域称为数据域。
- 存储数据元素之间的链接信息即下一个存储数据元素地址的部分称为指针域。
- 由数据域和指针域组成的数据元素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 的理解，请持续关注我哦！！！
