链表总结 -- 《数据结构》-- c/c++

链表的概念

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。

链表的一个结点示意图 : 

在c/c++语言中,链表一般使用结构体来定义实现 ;

struct Node{
    int data;
    Node*next;
};

链表的类型

单链表 : 

链表的入口节点称为链表的头结点也就是head。

双链表

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

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

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

循环链表

循环链表,顾名思义,就是链表首尾相连。

链表的存储方式

数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。

如图所示 : 

这个链表起始节点为2, 终止节点为7, 各个节点分布在内存的不同地址空间上,通过指针串联在一起。

链表的定义

这里我给出C/C++的定义链表节点方式,如下所示:

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

链表的操作

删除结点

比如删除下图中的D结点  : 

要做的是将c的尾结点指向E结点,然后再将d结点手动释放一下就行了 ;

添加结点

如图所示:

链表-添加节点

可以看出链表的增添和删除都是O(1)操作,也不会影响到其他节点。

但是要注意,要是删除第五个节点,需要从头节点查找到第四个节点通过next指针进行删除操作,查找的时间复杂度是O(n)。

性能分析

数组在定义的时候,长度就是固定的,如果想改动数组的长度,就需要重新定义一个新的数组。

链表的长度可以是不固定的,并且可以动态增删, 适合数据量不固定,频繁增删,较少查询的场景。

参考 : 

  • https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E9%93%BE%E8%A1%A8%E7%9A%84%E6%93%8D%E4%BD%9C

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Windows 编译 yangfengzzz/fluid-engine-OpenVDB

我想将 OpenVDB 接入 doyubkim 的流体引擎 https://github.com/doyubkim/fluid-engine-dev 然后搜到已经有人做过这件事了 https://github.com/yangfengzzz/fluid-engine-OpenVDB Windows 编译 yangfengzzz/fluid-engine-OpenVDB 但是我是 windows,所以想要编译…

idea突然出现错误: “找不到或无法加载主类 @C:\Users\happ“解决方案

在公司敲代码时,编译器突然出现了以下报错,之前一直能正常运行 可以使用以下方法解决 找到启动类相关配置 找到Shorten command line,选择如下配置即可 进行到这里项目就能正常运行了,仅以此贴记录问题解决方案

高程 | 继承与派生(c++)

文章目录 📚继承的概念和语法📚派生类生成过程📚继承权限和继承方式🐇公有继承🐇私有继承🐇保护继承 📚类型转换规则📚派生类构造函数和析构函数📚继承中的静态成员特性&…

互联网加竞赛 基于设深度学习的人脸性别年龄识别系统

文章目录 0 前言1 课题描述2 实现效果3 算法实现原理3.1 数据集3.2 深度学习识别算法3.3 特征提取主干网络3.4 总体实现流程 4 具体实现4.1 预训练数据格式4.2 部分实现代码 5 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 基于深度学习机器视觉的…

SpringBoot实战:打造企业资产管理系统

✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 |…

php 数组函数

php 数组函数 1. 常用的php数组函数 1. 常用的php数组函数 array_pop() 删除数组中最后一个元素 array_push() 将一个或多个元素插入到数组的末尾 array_keys <?php $arr array("刘岩" > 30, "范冰冰" > 31, "娜扎" > 31);$…

制作一个入耳式耳机壳需要用到哪些材料和工艺流程呢?

制作一个入耳式耳机壳需要用到以下材料和工艺流程&#xff1a; 材料&#xff1a; 耳机壳材料&#xff1a;常用的有PC/ABS塑料、金属、陶瓷、木质等。不同材料具有不同的特性&#xff0c;如塑料轻便耐用、金属质感好、陶瓷高档、木质自然等。耳塞材料&#xff1a;常用的有硅胶、…

自学ESPIDF(一)点个灯

不废话&#xff0c;万物皆从点灯开始。 espidf的examples里有个blink&#xff0c;作为测试再好不过了。 /* Blink ExampleThis example code is in the Public Domain (or CC0 licensed, at your option.)Unless required by applicable law or agreed to in writing, thissof…

模仿 STM32 驱动开发格式实验

1.模仿 STM32 寄存器定义 为了开发方便&#xff0c; ST 官方为 STM32F103 编写了一个叫做 stm32f10x.h 的文件&#xff0c;在这个文件 里面定义了 STM32F103 所有外设寄存器&#xff0c;我们可以使用其定义的寄存器来进行开发&#xff0c;比如我 们可以用如下代码来初始…

【regex】正则表达式

集合 [0-9.] [0-9.\-] 例子 正则表达式&#xff0c;按照规则写&#xff0c;写的时候应该不算困难&#xff0c;但是可读性差 不同语言中regex会有微小的差异 vim 需要转义&#xff0c; perl/python中不需要转义 锚位 \b am\b i am 命名 [0-9.\-] (?<ta>[0-9.\-]) …

机器学习中为什么需要梯度下降

在机器学习中&#xff0c;梯度下降是一种常用的优化算法&#xff0c;用于寻找损失函数的最小值。我们可以用一个简单的爬山场景来类比梯度下降的过程。 假设你被困在山上&#xff0c;需要找到一条通往山下的路。由于你是第一次来到这座山&#xff0c;对地形不熟悉&#xff0c;你…

微服务学习Day4

文章目录 初始MQ同步通讯和异步通讯MQ常见技术介绍 RabbitMQ快速入门入门案例 SpringAMQP介绍例子WorkQueue模型exchange交换机消息转换器 初始MQ 同步通讯和异步通讯 MQ常见技术介绍 RabbitMQ快速入门 入门案例 SpringAMQP 介绍 例子 WorkQueue模型 exchange交换机 消息转换…

【解决(几乎)任何机器学习问题】:处理分类变量篇(上篇)

这篇文章相当长&#xff0c;您可以添加至收藏夹&#xff0c;以便在后续有空时候悠闲地阅读。 本章因太长所以分为上下篇来上传&#xff0c;请敬请期待 很多⼈在处理分类变量时都会遇到很多困难&#xff0c;因此这值得⽤整整⼀章的篇幅来讨论。在本章中&#xff0c;我将 讲述不同…

分享几种免费获取SSL证书方式

自2018年七月开始&#xff0c;Chrome将所有未安装使用SSL证书的网站皆标记为“不安全”。在访问未安装部署SSL证书网站时经常会出现风险提示&#xff0c;而拥有SSL证书的网站在权重排名上会有一定提升。 当然网站部署SSL证书最主要的意义还是在于网络安全防范和普及https&#…

【IDEA关闭项目一直转圈】

IDEA关闭项目一直转圈&#xff1a; IDEA启动时&#xff0c;会自动打开上次关闭时所有显示的窗口&#xff0c;如果本次工作不需要上次打开的所有窗口&#xff0c;可以基于选择窗口界面的右上角去关闭。 项目关闭失败 但是偶尔会出现窗口关闭时&#xff0c;一直显示“正在关闭项…

Ubuntu学习笔记-禅道从windows迁移到ubuntu中。

文章目录 一、备份Windows下的数据1.1 备份Windows下的mysql数据库数据1.1.1 找到禅道安装目录下的mysql文件路径。1.1.2 执行mysqldump指令备份数据库1.1.3 将数据库备份文件拷贝到ubuntu服务器中。二、ubuntu下配置禅道2.1 ubuntu安装禅道2.1.1 点击禅道下载,然后搜索12.5.3…

前端面试必备八股文——HTMLCSS

HTML src和href的区别 src和href都是用来加载外部资源&#xff0c;区别如下 src当浏览器解析到该元素时&#xff0c;会暂停其他资源的加载和处理&#xff0c;直到该资源加载完成。 它会将资源内容嵌入到当前标签所在的位置&#xff0c;将其指向的资源下载应用到文档内&#…

普中51单片机学习(六)

点亮第一个LED LED相关知识 LED,即发光二极管&#xff0c;是一种半导体固体发光器件。工作原理为&#xff1a;LED的工作是有方向性的&#xff0c;只有当正级接到LED阳极&#xff0c;负极接到LED的阴极的时候才能工作&#xff0c;如果反接LED是不能正常工作的。其原理图如下 …

[嵌入式系统-27]:RT-Thread -14- 操作系统配置:rtconfig.h文件与menuconfig命令

目录 一、rtconfig.h 1.1 概述 1.2 软硬件资源配置 1.3 功能模块选择 1.4 内核配置详解 1.5 调度器配置 1.6 硬件设备驱动配置 1.7 网络配置 1.8 调试配置 二、menuconfig 2.1 概述 2.2 主要功能 三、RT Thread配置 VS Linux配置 一、rtconfig.h 1.1 概述 rtco…

关于虚拟化的一切

茶还是咖啡&#xff1f; Xbox 还是 PlayStation&#xff1f; Chrome 还是 Firefox&#xff1f; 我们习惯于做出棘手的选择。在云计算中&#xff0c;选择 Linux 还是 Windows 也不例外&#xff0c;通常涉及成本、灵活性和项目特定要求。虽然 Linux 具有开源和经济高效的优势&…