当前位置: 首页 > 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;也是一个网站口碑的重要评判标准。 一、名称解释 前端监控…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...