【数据结构】双向奔赴的爱恋 --- 双向链表
关注小庄 顿顿解馋๑ᵒᯅᵒ๑
引言:上回我们讲解了单链表(单向不循环不带头链表),我们可以发现他是存在一定缺陷的,比如尾删的时候需要遍历一遍链表,这会大大降低我们的性能,再比如对于链表中的一个结点我们是无法直接访问它的上一个结点,那有什么解决方法呢?这里就得请出我们今天的主角----双链表。
文章目录
- 一. 🏠 什么是双链表
- 二. 🏠 双链表的实现
- 👿 双链表结点
- 👿 双链表哨兵位的创建
- 👿 双链表插入数据
- 👿 双链表删除数据
- 👿 双链表查找
- 👿 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++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...

学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...