【数据结构】双向奔赴的爱恋 --- 双向链表
关注小庄 顿顿解馋๑ᵒᯅᵒ๑
引言:上回我们讲解了单链表(单向不循环不带头链表),我们可以发现他是存在一定缺陷的,比如尾删的时候需要遍历一遍链表,这会大大降低我们的性能,再比如对于链表中的一个结点我们是无法直接访问它的上一个结点,那有什么解决方法呢?这里就得请出我们今天的主角----双链表。
文章目录
- 一. 🏠 什么是双链表
- 二. 🏠 双链表的实现
- 👿 双链表结点
- 👿 双链表哨兵位的创建
- 👿 双链表插入数据
- 👿 双链表删除数据
- 👿 双链表查找
- 👿 pos结点前插入数据和删除pos结点数据
- 👿 双链表打印和销毁
- 三. 🏠 双链表的分析
一. 🏠 什么是双链表
在这里我们讲的双链表有三个特点 :双向 , 循环 , 带头 。我们分别理解这三个特点~
-
双向 循环
优势
:1.每一个结点都能很方便访问它的后一个结点和前一个结点 2.方便找到尾节点,提高了效率。 -
带头
图中的head就是哨兵位
- 这里的
带头
跟我们之前所说的头节点
有所不同,这里的带头,不存储有效数据
起到一个哨兵的作用。- 哨兵位的作用:
遍历循环链表避免死循环,其次涉及到头节点的删除和插入时,无需考虑NULL的问题。
双链表的这三个特点将会使得实现它比实现单链表更简单~
二. 🏠 双链表的实现
👿 双链表结点
为了能循环和双向,我们双链表的一个结点需要两个指针。
typedef int Datatype;
typedef struct ListNode
{struct ListNode* next;struct ListNode* pre;Datatype x;
}ListNode;
👿 双链表哨兵位的创建
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (NULL == newnode){perror("malloc failed");return;}newnode->x = x;newnode->next = newnode;newnode->pre = newnode;
1.注意next指针和pre指针都要指向自己。
2.由于插入数据也要创建新结点,所以我们可以直接创建一个申请结点的接口方便复用。
//申请新结点的接口
ListNode* BuyNode(Datatype x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (NULL == newnode){perror("malloc failed");return;}newnode->x = x;newnode->next = newnode;newnode->pre = newnode;return newnode;
}
// 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* phead = BuyNode(-1); //哨兵位return phead;
}
👿 双链表插入数据
- 尾插
双链表的尾插指的是将新节点插入到哨兵位之前
1.黄色箭头和蓝色箭头是我们要修改的指针指向
2.注意:要先改变蓝色箭头的对应关系
,如果先让head的pre变成newnode话,后边newnode->pre = plist就会指向自己
3.小技巧:不管三七二十一,插入直接先改newnode的next和pre
// 双向链表尾插 尾插是插到plist的前面
void ListPushBack(ListNode* plist, Datatype x)
{assert(plist);ListNode* newnode = BuyNode(x);newnode->next = plist;newnode->pre = plist->pre;plist->pre->next = newnode;plist->pre = newnode;
}
- 头插
// 双向链表头插 头插是插到哨兵位的后面
void ListPushFront(ListNode* plist, Datatype x)
{ListNode* newnode = BuyNode(x);ListNode* del = plist->next;newnode->next = del;newnode->pre = plist;del->pre = newnode;plist->next = newnode;
}
*是不是很easy,跟单链表比起来 ~ *
👿 双链表删除数据
- 尾删
对于尾删 只需要改它前面一个结点next和哨兵位的pre就好了,存好pre结点的位置
void ListPopBack(ListNode* plist)
{assert(plist);assert(plist->next != plist);ListNode* ptail = plist->pre;ListNode* pre = ptail->pre;pre->next = plist;plist->pre = pre;free(ptail);ptail = NULL;
}
- 头删
// 双向链表头删
void ListPopFront(ListNode* plist)
{assert(plist);assert(plist->next != plist);ListNode* pNext = plist->next->next;ListNode* pcur = plist->next;plist->next = pNext;pNext->pre = plist;free(pcur);pcur = NULL;
}
👿 双链表查找
遍历链表找到就停下,如果没找到循环到head停止,返回NULL。大大提现了哨兵位的好处
// 双向链表查找
ListNode* ListFind(ListNode* plist, Datatype x)
{assert(plist);ListNode* pcur = plist->next;while (pcur != plist){if (pcur->x == x){return pcur;}pcur = pcur->next;}return NULL;
}
👿 pos结点前插入数据和删除pos结点数据
类似尾插尾删,头插头删,改变指针指向即可
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, Datatype x)
{assert(pos);ListNode* newnode = BuyNode(x);ListNode* pre = pos->pre;newnode->next = pos;newnode->pre = pre;pre->next = newnode;pos->pre = newnode;
}
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos)
{assert(pos);ListNode* pre = pos->pre;ListNode* pNext = pos->next;pre->next = pNext;pNext->pre = pre;free(pos);pos = NULL;
}
👿 双链表打印和销毁
循环遍历到phead停止~
// 双向链表打印
void ListPrint(ListNode* plist)
{assert(plist);ListNode* pcur = plist->next;while (pcur != plist){printf("%d->", pcur->x);pcur = pcur->next;}printf("\n");
}
// 双向链表销毁
void ListDestory(ListNode* plist)
{ListNode* pcur = plist->next;while (pcur != plist){ListNode* del = pcur->next;free(pcur);pcur = del;}free(pcur);pcur = NULL; //无效
}
注意:由于函数形参是实参的一份临时拷贝,所以要在函数外手动置空!
三. 🏠 双链表的分析
经过如上我们实现的双链表结构,我们不禁发现它比单链表功能的强大,那它是否是完美的呢?答案是否的,没有完美的人,也没有完美的数据结构。
优点:
1.双链表单次任意位置插入和删除效率较高,比单链表还要效率高
2.双链表不存在空间浪费,按需申请和释放空间
3.双链表的一个结点可以访问前后结点(相比于单链表)
缺点:
1.和单链表一样,虽然双链表访问尾结点快,但是任然不支持随机访问
2.cpu高速缓存命中率低,因为结点地址可能是分散的。
本次双链表的讲解就到此结束啦,各位看官能否与我双向奔赴来个三连呢! ! !
相关文章:

【数据结构】双向奔赴的爱恋 --- 双向链表
关注小庄 顿顿解馋๑ᵒᯅᵒ๑ 引言:上回我们讲解了单链表(单向不循环不带头链表),我们可以发现他是存在一定缺陷的,比如尾删的时候需要遍历一遍链表,这会大大降低我们的性能,再比如对于链表中的一个结点我们是无法直接…...
【Redis】高频面试题
提供五种常见的数据类型:String(字符串),Hash(哈希),List(列表),Set(集合)、Zset(有序集合) 文章目录 1、为什…...
数据分析基础
数据分析基础 1. 数据加载 使用 Pandas 库可以轻松地加载各种格式的数据,如 CSV、Excel、JSON 等。 import pandas as pd# 从 CSV 文件加载数据 data pd.read_csv(‘data.csv’). 2. 数据探索 一旦数据加载完成,我们可以开始对数据进行探索性分析&a…...
ffmpeg把一个平面视频,做成左右平面视频
要使用FFmpeg将单个平面视频转换为左右(或称为并排)3D格式的视频,你可以使用FFmpeg的filter_complex功能来实现。这种类型的视频通常用于3D视觉效果,其中同一画面的两个版本并排放置,每个版本略有不同的视角࿰…...

Docker搭建LNMP环境实战(02):Win10下安装VMware
实战开始,先安装 VMware 虚拟机。话不多说,上手就干! 1、基本环境检查 1.1、本机Bios是否支持虚拟化 进入:任务管理器- 性能,查看“虚拟化”是否启用,如果已启用,则满足要求,如果未…...

苍穹外卖笔记
苍穹外卖 DAY01nginx反向代理MD5加密yapi进行接口导入Swagger介绍 DAY02新增员工需求分析和设计写相关代码测试(1. 后端文档测试 2. 前后端联调代码完善 员工分页查询DAY01 02涉及到的知识 DAY03阿里云OSS事务注解 Transactional DAY01 nginx反向代理 MD5加密 拓展࿱…...

[医学分割大模型系列] (3) SAM-Med3D 分割大模型详解
[医学分割大模型系列] -3- SAM-Med3D 分割大模型解析 1. 特点2. 背景3. 训练数据集3.1 数据集收集3.2 数据清洗3.3 模型微调数据集 4. 模型结构4.1 3D Image Encoder4.2 3D Prompt Encoder4.3 3D mask Decoder4.4 模型权重 5. 评估5.1 评估数据集5.2 Quantitative Evaluation5.…...
【React】React中将 Props 传递给组件
当使用 React 时,props 是组件之间传递数据的主要方式。以下是针对您提到的五个问题的详细解答: 1. 如何向组件传递 props 在父组件中,你可以通过组件标签的属性(attributes)将 props 传递给子组件。这些属性在子组件…...
JOL工具查看java对象布局
JOL(Java Object Layout)是一个用于分析Java对象在Java虚拟机(JVM)中内存布局的小工具包。以下是如何使用JOL查看Java对象布局的步骤示例: Maven项目中添加依赖: 首先,在Maven项目中引入JOL工…...
Rust 实战练习 - 3. 文件系统,权限,读写,路径组合,time
目标: 文件系统,遍历目录路径的使用权限和文件属性时间time use std::{env, fmt::Debug, os::unix::fs::{MetadataExt, PermissionsExt}, path::{Path, PathBuf}, time::SystemTime};fn main() {// 时间处理// 除Duration和SystemTime外,标准库没有时间…...

既有理论深度又有技术细节——深度学习计算机视觉
推荐序 我曾经试图找到一本既有理论深度、知识广度,又有技术细节、数学原理的关于深度学习的书籍,供自己学习,也推荐给我的学生学习。虽浏览文献无数,但一直没有心仪的目标。两周前,刘升容女士将她的译作《深度学习计…...
Flink Temporal Join 系列 (2):用 Temporal Table DDL 实现基于处理时间的关联
本文要演示的是:使用 Temporal Table DDL 定义被关联表(维表),然后基于主动关联表(事实表)的“处理时间”去进行Temporal Join(关联时间维度上对应版本的维表数据)。该演示涉及三个要点: 被关联的表(维表)是用 Temporal Table DDL 形式定义,必须是一张时态表(版本…...

eclipse中使用PlantUML plugin查看对象关系
一.背景 公司安排的带徒弟任务,给徒弟讲了如何设计对象。他们的思维里面都是单表增删改查,我的脑海都是一个个对象,他们相互关系、各有特色本事。稳定的结构既能满足外部功能需求,又能在需求变更时以最小代价响应。最大程度的记录…...

HCIP的学习(4)
GRE和MGRE VPN---虚拟专用网络。指依靠ISP(运营商)或其他公有网络基础设施上构建的专用的安全数据通信网络。该网络是属于逻辑上的。 核心机制—隧道机制(封装技术) GRE—通用路由封装 三层隧道技术,并且是属于…...
MySQL写shell的问题
写shell用什么函数? select <?php phpinfo()> into outfile D:/shelltest.phpdumpfilefile_put_contentsoutfile不能用了怎么办? select unhex(udf.dll hex code) into dumpfile c:/mysql/mysql server 5.1/lib/plugin/xxoo.dll;可以UDF提权https…...
每天学习一会java(第一天)----条件运算符
今天学习的是条件运算符 1.描述: 条件运算符由“?”与 “:” 两个符号组成,必须一起使用,是 JAVA 中唯一的三目(三元)运算符,需要三个操作数才能进行运算。 条件表达式的一般使用形式为: 表达…...

hyperf 二十八 修改器 一
教程:Hyperf 一 修改器和访问器 根据教程,可设置相关函数,如set属性名Attribute()、get属性名Attribute(),设置和获取属性。这在thinkphp中也常见。 修改器:set属性名Attribute();访问器:get属性名Attri…...

ubuntu20.04安裝輸入法
文章目录 前言一、操作過程1、安装fcitx-googlepinyin2、配置language support 前言 參考文獻 一、操作過程 1、安装fcitx-googlepinyin sudo apt-get install fcitx-googlepinyin2、配置language support 第一次點擊進去,會讓你安裝 點擊ctrl和空格切換中英文…...

2024年【熔化焊接与热切割】考试报名及熔化焊接与热切割找解析
题库来源:安全生产模拟考试一点通公众号小程序 熔化焊接与热切割考试报名考前必练!安全生产模拟考试一点通每个月更新熔化焊接与热切割找解析题目及答案!多做几遍,其实通过熔化焊接与热切割实操考试视频很简单。 1、【单选题】 下…...

聚类分析|基于层次的聚类方法及其Python实现
聚类分析|基于层次的聚类方法及其Python实现 0. 基于层次的聚类方法1. 簇间距离度量方法1.1 最小距离1.2 最大距离1.3 平均距离1.4 中心法1.5 离差平方和 2. 基于层次的聚类算法2.1 凝聚(Agglomerative)2.3 分裂(Divisive) 3. 基于…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...

【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...