当前位置: 首页 > news >正文

数据结构与算法(五)--链表概念以及向链表添加元素

一、前言

今天我们学习另一种非常重要的线性数据结构–链表,之前我们已经学习了三种线性数据结构,分别是动态数组,栈和队列。其中队列我们额外学习了队列的另一种实现方式–循环队列。其实我们自己实现过前三个数据结构就知道,它们底层均依托静态数组,靠resize解决固定容量问题。而链表和前三种均不同,它是真正的动态数据结构
学好链表,有利于:

  • 链表是最简单的动态数据结构,方便你学习后面的二分搜索树,Trie,AVL,红黑树等等
  • 更深入的理解引用(或者指针)
  • 更深入的理解递归
  • 辅助生成其他数据结构,例如我们之前学习的栈,队列可以通过链表实现,亦或是其他复杂的数据结构如图,哈希表等

二、链表

  • 数据存储在"节点"(Node)中
class Node<T>{T t;   //数据Node next; //指向当前节点的下一个节点
}

就像火车一样,每一个节点就像一个个车厢,车厢除了人(数据),还要和其他车厢进行连接,以使得数据是整合在一起的,用户可以方便的在所有的数据上进行查询等其他操作。而数据和数据之间的连接就是靠Node next决定的。
在这里插入图片描述
而我们的链表自然也不可能是无穷无尽的,我们链表存储的数据一定是有限的,那么最后一个节点它的next存储的就是一个NULL:我们也可以反过来得知,如果一个节点的NEXT是NULL,那么就说明这个节点一定是最后一个节点
在这里插入图片描述

  • 优点:真正的动态,不需要处理固定容量的问题,需要多少数据,就生成多少节点,并将它们连接起来。不需要像静态数组一样事先预定好一块儿固定空间。
  • 缺点:丧失了随机访问的能力,说白了就是不能像数组一样直接拿一个索引,找出索引对应的元素。这是因为从底层机制上,数组所开辟的空间在内存里是连续分布的,所以我们可以直接去寻找索引对应的偏移,直接计算机相应的数据所存储的地址,直接用O(1)的复杂度就把这个元素找出来。但是链表不同,链表是靠next一层一层连接的,所以在计算机的底层每一个节点在内存的位置是不同的,我们必须靠next一点一点的找到我们想要的元素,这就是链表最大的缺点

基于上述理论,我们可以有如下数组和链表的对比:

数组

  • 数组最好用于索引有语意的情况。如scores[2]
  • 最大的优点:支持快速查询

链表

  • 链表不适合用于索引有语意的情况
  • 最大的优点:动态

但是其实我们后续实现动态数组有说过,我们处理的都是索引没有语意的情况,对于这类不方便使用索引的数据,我们使用链表存储这些数据是更合适的。由于它最大的优点就是动态。
我们可以先初步搭建一下我们链表的类,首先创建一个链表类,然后创建一个内部私有类Node节点,就和我们之前提的是一样的:

public class LinkedList<T> {//只有在链表结构内才能访问Node,链表结构外用户无法访问,因为对于用户而言,他们不需要指定链表的底层实现private class Node {public T data;public Node next;public Node(T data, Node next) {this.data = data;this.next = next;}public Node(T data) {this(data, null);}public Node() {this(null, null);}@Overridepublic String toString() {return "Node{" +"data=" + data +", next=" + next +'}';}}
}

三、向链表添加元素

对于链表来说,我们要想访问链表中的所有节点,相应的必须把链表头存储起来,通常呢,链表的头结点叫作head,所以我们的LinkedList类中应该有一个Node类型的变量叫作head。它指向链表中的第一个节点。我们首先把我们linkedList的基础变量声明出来。

private Node head;private int size;public LinkedList() {this.head = null;this.size = 0;}public int getSize(){return size;}public boolean isEmpty(){return size == 0;}

①往链表头部增加元素
我们之前学习数组添加元素的时候,第一个说的方法是往数组末尾添加元素,这是因为对于数组而言,往数组末尾添加元素是比较方便的。
但链表则正好相反,对于链表而言往连边头部增加元素是非常方便的。
这其实很好理解,因为数组有size这个变量,它直接指向的是第一个未被添加元素的位置,所以直接往尾部添加很方便,因为有size这个变量在跟踪数组的尾巴。
而链表我们有头部的变量,但是我们没有相应的变量去跟踪链表的尾巴,所以我们往链表头添加元素很方便。
例如我现在要插入一个666的节点,图示如下:
在这里插入图片描述

往链表头添加元素后,我们要把这个元素和链表连接起来,所以我们需要让新添加的Node指向我们的head,然后由于连起来后,这个链表已经成了新的头节点,所以我们要把新添加的Node赋值给我们的头结点。

node.next = head;
head = node;

那么我们往头部插入元素实现就很简单:

public void addFirst(T t){//声明一个新的节点,将这个新节点指向我们的头结点,然后再让新的节点成为头结点Node node = new Node(t);node.next = head;head = node;size ++;}

其实上面的方法我们还有更优雅的写法:

	public void addFirst(T t){//声明一个新的节点,将这个新节点指向我们的头结点,然后再让新的节点成为头结点
//		Node node = new Node(t);
//		node.next = head;
//		head = node;//这一行代码干了上面三行代码的事head = new Node(t,head);size ++;}

往链表中间插入元素(注:这个操作不是常用操作,练习用)
例如,往“索引”为2的位置插入元素:
注意,这里索引打了引号,因为链表其实不存在索引这个概念,如下图,其实就相当于在1这个元素后面插入一个666的元素:
在这里插入图片描述
那么我们的思路就是,想要插入这个666的元素,需要找到插入的位置的前一个节点的位置,让这个节点的next指向我要插入的新节点,然后新节点的next指向原来的前一个节点的next的节点。所以我们为了方便找到前一个节点的位置,我们定义一个prev变量,初始情况prev和head指向同一个位置,而后面通过将prev移动找到对应的插入的位置的前一个节点的位置:
在这里插入图片描述
所以我们的任务就是找到插入666之前的那个节点是谁。比如我们现在要插入的位置是“索引”为2,所以插入之前的“索引”为1,所以我们遍历一下,prev指向“索引”为1的位置,然后新的节点的next指向我们的原来“索引”为1的next,即“索引”为2的节点,然后将原来“索引”为1的next指向我们新的节点:
在这里插入图片描述

node.next = prev.next;
prev.next= node;

关键就是:找到要添加的节点的前一个节点
有些人可能会注意到,当我要把元素添加到索引为0的位置的时候,此时索引为0的位置是没有前一个元素的,我们需要特殊处理一下。
然后就是对于链表很重要的一点:顺序
如果我把上述操作倒过来:

prev.next= node;
node.next = prev.next;

那么就会出现Node的next指向Node自己的错误,所以顺序一定要注意。可以通过纸笔或者debug调试一下。那么我们的实现如下:

//在链表的Index(0-based)位置添加新的元素epublic void add(T t, int index) {if (index < 0 || index > size) {throw new IllegalArgumentException("add element error:index should >= 0 && index <= size");}//如果Index = 0,由于索引为0的位置没有前一个元素,所以我们直接特殊处理,其实就相当于往头部添加元素if(index == 0){addFirst(t);}else {Node prev = head;for(int i = 0;i < index - 1;i ++){prev = prev.next;}Node node = new Node(t);node.next = prev.next;prev.next = node;size ++;}}

那么add完成了后,我们就可以很简单的完成再添加一个add方法了,就是向链表末尾添加一个元素addLast(),其实就是add方法的index传size即可:

public  void addLast(T t){add(t,size);}

那么以上就是链表的添加元素方法,但其实我们的add()仍然不够优雅,关键在于我们需要对Index=0的处理方法特殊处理,其实有一种方法可以直接让我们拜托这种特殊处理,就是设立虚拟head结点,这个我们后面会讲到:

四、为链表设立虚拟头结点

我们之前说add方法的时候,有一个不太优雅的地方就是当Index=0的时候,我们需要特殊处理,原因就是头结点没有上一个节点,那么解决思路也很简单,我们就造一个虚拟的链表头结点,它其实不存储任何的元素,我们将这个NULL节点称之为我们链表的head,也叫做dummyHead,即虚拟头结点。它其实就是索引为0对应的元素的前一个位置。那么这样添加,当index = 0时,就不需要特殊处理了。
在这里插入图片描述
且我们现在prev是从dummyHead开始,即索引为0对应的元素的前一个位置开始,那么我们其实我们不再需要遍历Index-1次,而直接遍历Index次就可以找到插入位置的前一个位置了,说白了就是我的起点往前挪了一个位置,那么我遍历次数自然就需要少1次
在这里插入图片描述
代码如下:

//在链表的Index(0-based)位置添加新的元素epublic void add(T t, int index) {if (index < 0 || index > size) {throw new IllegalArgumentException("add element error:index should >= 0 && index <= size");}Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}Node node = new Node(t);node.next = prev.next;prev.next = node;size++;}

那么反过来,我们的addFirst也可以通过add简化了:

	public void addFirst(T t) {//声明一个新的节点,将这个新节点指向我们的头结点,然后再让新的节点成为头结点add(t, 0);}

相关文章:

数据结构与算法(五)--链表概念以及向链表添加元素

一、前言 今天我们学习另一种非常重要的线性数据结构–链表&#xff0c;之前我们已经学习了三种线性数据结构&#xff0c;分别是动态数组&#xff0c;栈和队列。其中队列我们额外学习了队列的另一种实现方式–循环队列。其实我们自己实现过前三个数据结构就知道&#xff0c;它…...

计算机视觉与深度学习-图像分割-视觉识别任务02-目标检测-【北邮鲁鹏】

目录标题 参考目标检测定义深度学习对目标检测的作用单目标检测多任务框架多任务损失预训练模型姿态估计 多目标检测问题滑动窗口&#xff08;Sliding Window&#xff09;滑动窗口缺点 AdaBoost&#xff08;Adaptive Boosting&#xff09;参考 区域建议 selective search 思想慢…...

Flink——Flink检查点(checkpoint)、保存点(savepoint)的区别与联系

Flink checkpoint Checkpoint是Flink实现容错机制最核心的功能&#xff0c;能够根据配置周期性地基于Stream中各个Operator的状态来生成Snapshot&#xff0c;从而将这些状态数据定期持久化存储下来&#xff0c;从而将这些状态数据定期持久化存储下来&#xff0c;当Flink程序一…...

[篇五章五]-如何禁用 Windows Defender-我的创作纪念日

################################################## 目录 禁用掉烦人的 Windows Defender 在本地组策略编辑器中禁用 Windows Defende 关闭 Microsoft Defender 防病毒 禁止 Defender 开机自动运行 重新激活 Windows Defender #######################################…...

什么情况下使用微服务?

单体架构图参考网络&#xff1a; 1. 什么是单体应用 单体应用就是将应用程序的所有功能都打包成一个独立的单元&#xff0c;最终以一个WAR包或JAR包存在&#xff0c;没有外部的任何依赖&#xff0c;里面包含DAO、Service、UI等所有的逻辑。 优点&#xff1a; &#xff11;&…...

【Linux】Ubuntu美化主题【教程】

【Linux】Ubuntu美化主题【教程】 文章目录 【Linux】Ubuntu美化主题【教程】1. 安装优化工具Tweak2.下载自己喜欢的主题3. 下载自己喜欢的iconReference 1. 安装优化工具Tweak 首先安装优化工具Tweak sudo apt-get install gnome-tweak-tool安装完毕后在菜单中打开Tweak 然后…...

spring-boot2.x,使用EnableWebMvc注解导致的自定义HttpMessageConverters不可用

在json对象转换方面&#xff0c;springboot默认使用的是MappingJackson2HttpMessageConverter。常规需求&#xff0c;在工程中使用阿里的FastJson作为json对象的转换器。 FastJson SerializerFeatures WriteNullListAsEmpty &#xff1a;List字段如果为null,输出为[],而非nu…...

2023-09-20 Android CheckBox 让文字显示在选择框的左边

一、CheckBox 让文字在选择框的左边 &#xff0c;在布局文件里面添加下面一行就可以。 android:layoutDirection"rtl" 即可实现 android:paddingStart"10dp" 设置框文间的间距 二、使用的是left to right <attr name"layoutDirection">&…...

目标检测YOLO实战应用案例100讲-基于改进YOLOv5的口罩人脸检测

目录 前言 国内外研究现状 目标检测研究发展 国内外口罩人脸检测研究现状...

CentOS7 yum安装报错:“Could not resolve host: mirrorlist.centos.org; Unknown error“

虚拟机通过yum安装东西的时候弹出这个错误&#xff1a; 1、查看安装在本机的网卡 网卡ens33处于disconnected的状态 nmcli d2、输入命令&#xff1a; nmtui3、选择网卡&#xff0c;然后点击edit 4、移动到Automatically connect按空格键选择&#xff0c;然后移动到OK键按空格…...

关于token续签

通常我们会对token设置一个有效期&#xff0c;于是&#xff0c;就有了token续签的问题。由于token并没有续时机制&#xff0c;如果不能及时的替换掉过期的token&#xff0c;可能会拦截用户正常的请求&#xff0c;用户只能重新登录&#xff0c;如果提交的信息量很大&#xff0c;…...

淘宝分布式文件存储系统( 二 ) -TFS

淘宝分布式文件存储系统( 二 ) ->>TFS 目录 : 大文件存储结构哈希链表的结构文件映射原理及对应的API文件映射头文件的定义 大文件存储结构 : 采用块(block)文件的形式对数据进行存储 , 分成索引块,主块 , 扩展块 。所有的小文件都是存放到主块中的 &#xff0c;扩展块…...

Java中synchronized:特性、使用、锁机制与策略简析

目录 synchronized的特性互斥性可见性可重入性 synchronized的使用方法synchronized的锁机制常见锁策略乐观锁与悲观锁重量级锁与轻量级锁公平锁与非公平锁可重入锁与不可重入锁自旋锁读写锁 synchronized的特性 互斥性 synchronized确保同一时间只有一个线程可以进入同步块或…...

记一次clickhouse手动更改分片数异常

背景&#xff1a;clickhouse中之前是1分片1副本&#xff0c;随着数据量增多&#xff0c;想将分片数增多&#xff0c;于是驻场人员手动添加了分片数的节点信息 <clickhouse><!-- 集群配置 --><clickhouse_remote_servers><feihuang_ck_cluster><sha…...

深度学习论文: ISTDU-Net:Infrared Small-Target Detection U-Net及其PyTorch实现

深度学习论文: ISTDU-Net&#xff1a;Infrared Small-Target Detection U-Net及其PyTorch实现 ISTDU-Net&#xff1a;Infrared Small-Target Detection U-Net PDF: https://doi.org/10.1109/LGRS.2022.3141584 PyTorch代码: https://github.com/shanglianlm0525/CvPytorch PyTo…...

图像识别-YOLO V8安装部署-window-CPU-Pycharm

前言 安装过程中发现&#xff0c;YOLO V8一直在更新&#xff0c;现在是2023-9-20的版本&#xff0c;已经和1月份刚发布的不一样了。 eg: 目录已经变了&#xff0c;旧版预测:在ultralytics/yolo/v8/下detect 新版&#xff1a;ultralytics/models/yolo/detect/predict.py 1.安…...

js禁用F1至F12、禁止缩放、取消选中并且取消右键操作、打印、拖拽、鼠标点击弹出自定义信息、禁用开发者工具js

禁用js //禁止缩放 //luwenjie hualun window.addEventListener(mousewheel, function (event) {if (event.ctrlKey true || event.metaKey) {event.preventDefault();} }, {passive: false});//firefox window.addEventListener(DOMMouseScroll, function (event) {if (even…...

Zabbix5.0_介绍_组成架构_以及和prometheus的对比_大数据环境下的监控_网络_软件_设备监控_Zabbix工作笔记

z 这里Zabbix可以实现采集 存储 展示 报警 但是 zabbix自带的,展示 和报警 没那么好看,我们可以用 grafana进行展示,然后我们用一个叫睿象云的来做告警展示, 会更丰富一点. 可以看到 看一下zabbix的介绍. 对zabbix的介绍,这个zabbix比较适合对服务器进行监控 这个是zabbix的…...

百度SEO优化TDK介绍(分析下降原因并总结百度优化SEO策略)

TDK是SEO优化中很重要的部分&#xff0c;包括标题&#xff08;Title&#xff09;、描述&#xff08;Description&#xff09;和关键词&#xff08;Keyword&#xff09;&#xff0c;为百度提供网页内容信息。其中标题是最重要的&#xff0c;应尽量突出关键词&#xff0c;同时描述…...

搭建自动化 Web 页面性能检测系统 —— 设计篇

页面性能对于用户体验、用户留存有着重要影响&#xff0c;当页面加载时间过长时&#xff0c;往往会伴随着一部分用户的流失&#xff0c;也会带来一些用户差评。性能的优劣往往是同类产品中胜出的影响因素&#xff0c;也是一个网站口碑的重要评判标准。 一、名称解释 前端监控…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

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…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...