【数据结构】链表(一)

链表(一)

文章目录

  • 链表(一)
    • 01 引入
    • 02 概念及结构
    • 03 单向不带头不循环链表实现
      • 3.1 创建节点类型
      • 3.2 简易创建一个链表
      • 3.3 遍历链表每个节点
      • 3.4 获取链表长度
      • 3.5 查找是否包含关键字key是否在单链表当中
      • 3.6 头插法
      • 3.7 尾插法
      • 3.8 任意位置插入
      • 3.9 删除第一次出现关键字为key的节点
      • 3.10 删除所有值为key的节点
      • 3.11 清空

01 引入

接上文顺序表,我们可以知道ArrayList的缺陷。当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java集合中又引入了LinkedList,即链表结构。

那么下面,让我们来了解了解链表。

02 概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。其实就是节点组成,一个节点类似于火车一个车厢那样:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nxFKWdPq-1691313293619)(C:\Users\86159\AppData\Roaming\Typora\typora-user-images\image-20230802182622237.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NmTz2djR-1691313293621)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230805165401086.png)]

下面是一个单向带头非循环链表:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cIeoB8dK-1691313293621)(C:\Users\86159\AppData\Roaming\Typora\typora-user-images\image-20230803142840530.png)]

下面是链表的种类:

单向双向
不带头带头
非循环循环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kxeLdsML-1691313293622)(https://gitee.com/liuhb-clanguage/picture/raw/master/png/image-20230803144159308.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yb7FYu2f-1691313293622)(https://gitee.com/liuhb-clanguage/picture/raw/master/png/image-20230803144412289.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PCab9kv4-1691313293623)(C:\Users\86159\AppData\Roaming\Typora\typora-user-images\image-20230803144625610.png)]

通过彼此间的排列组合,一共可以分为:8种,如下:

  1. 单向 不带头 非循环
  2. 单向 不带头 循环
  3. 单向 带头 非循环
  4. 单向 带头 循环
  5. 双向 不带头 非循环
  6. 双向 不带头 循环
  7. 双向 带头 非循环
  8. 双向 带头 循环

这里着重介绍单向 不带头 非循环 和 双向 不带头 非循环。

  • 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
  • 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

03 单向不带头不循环链表实现

3.1 创建节点类型

链表是由一个一个节点组成的,每一个节点对应每一个对象,如果我们去抽象他,他其实有两个域值,所以我们可以把节点定义成内部类。

创建一个ListNode类来作为节点类型,包含两个成员变量:val域用来储存数据(数据域),next用来存储下一个节点的地址(指针域)。
再创建一个带参的构造方法来实例化对象,同时给val赋值,next的默认值是null。接下来我们用代码来实现一下:

//静态内部类static class ListNode{public int val; //节点的值域public ListNode next; //下一个节点的地址//实例化节点对象public ListNode(int val){this.val = val;}}

3.2 简易创建一个链表

public ListNode head;//表示当前链表的头节点//以穷举的方式创建一个链表public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);}

此时创建的链表如图:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a22rDdR2-1691313293623)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230803161957003.png)]

目前各节点间不存在关系。

那么接下来的操作就是要让node1->node2->node3->node4->node5

//以穷举的方式创建一个链表public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KSoJaQPS-1691313293623)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230803163008316.png)]

这里我们不妨在编译器里debug来看看:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0gyacBuy-1691313293624)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230803221846684.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r9st8GkK-1691313293624)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230803221913786.png)]

3.3 遍历链表每个节点

public void display() {while (head != null){System.out.println(head.val+" ");head = head.next;}}

这里我们可以在测试类中debug一下看看:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mvZIpdf9-1691313293624)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230803225415004.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zQCGDYFR-1691313293625)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230803225425896.png)]

虽然这里的确是将链表遍历完全,但是,这里的头节点head = null
在这里插入图片描述

那么这样就会造成一个后果,鬼都不知道头节点head死哪里去了,那咋办?

这个后果虽然很严重,但是解决办法其实也很容易,既然head它不能乱来,那它可以叫个分身cur代替它去呀。

public void display() {ListNode cur = head;while (cur != null){//如果cur == null,说明把链表遍历完成System.out.println(cur.val+" ");cur = cur.next;//cur每次向后走一步}System.out.println();}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4tyC9HTA-1691313293625)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230803232650482.png)]

3.4 获取链表长度

这个其实也就是基于3.3 遍历链表得来的。

//得到单链表的长度public int size(){int count = 0;ListNode cur = head;if (cur!=null){while(cur != null){cur = cur.next;count++;}return count;}else{return -1;}}

3.5 查找是否包含关键字key是否在单链表当中

这个其实也一样是基于3.3 遍历链表得来的。

//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while(cur != null){if (key == cur.val){return true;}cur = cur.next;}return false;}

3.6 头插法

头插法指的是在链表的头节点位置插入一个新的节点,定义一个node表示插入的新节点,然后将node.next = head,head = node,即可。

形象一点来看,如图:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wq1UPcRp-1691313293625)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230804140014328.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uiECf3X7-1691313293626)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230804140805784.png)]

//头插法public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}

3.7 尾插法

尾插法指的是:在链表的尾巴节点位置插入一个新节点,定义一个node表示新节点,如同头插法那样,对原尾巴节点的next进行赋值。下面是尾插链表出现的情况:

  • 当链表不为空的时候,定义一个cur来代替head(这里其实和遍历节点的道理一致),直到cur.next == null 的时候就跳出遍历,cur.next == node,这样即可完成尾插。

  • 当链表为空的时候,不论我们定义什么去代替head,都是竹篮打水一场空,都无法进入遍历,同时也会报空指针异常,解决方法其实也很简单,直接让head = node即可。

具体分析见以下:

如图:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cQZ0sLBB-1691313293626)(https://gitee.com/liuhb-clanguage/picture/raw/master/png/image-20230804142311057.png)]

其实这其中也有遍历链表那味了,其思想就是遍历到链表最后一个节点,然后再进行尾插就行了。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UcGHqGsq-1691313293626)(https://gitee.com/liuhb-clanguage/picture/raw/master/png/image-20230804143200359.png)]

//尾插法public void addLast(int data){ListNode node = new ListNode(data);ListNode cur = head;while (cur.next != null){cur = cur.next;}cur.next = node;}

但是这个代码是具有一定的问题的,情景如下图:

在这里插入图片描述

这个问题其实就是,此时head是空的,同时我们定义一个cur= head,那么cur也是空,那么就无法进入到while循环中。修正如下:

//尾插法public void addLast(int data){ListNode node = new ListNode(data);ListNode cur = head;if (cur == null){head = node;return;}//找到链表的尾巴,注意是cur.next 不是curwhile (cur.next != null){cur = cur.next;}cur.next = node;}

3.8 任意位置插入

思路:

  1. 定义curindex-1步,找到要插入位置的前一个节点
  2. 进行插入

给一个情景,定义cur = index - 1,在1号、2号间插入node.

关键就在于我们要将0x66 -> 0x777,null -> 0x32,即node.next = cur.next,cur.next = node.

需要将head先移至2号位置(注意:用cur代替head,防止head丢失),然后

node.next = cur.next使该节点的next域改为下一节点的地址,再cur.next = node.next使前一节点的next域改为该节点的地址。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ugPmgfIm-1691313293627)(https://gitee.com/liuhb-clanguage/picture/raw/master/png/image-20230804161544727.png)]

//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if (index < 0 || index > size()){System.out.println("index不合法");return;}if (index == 0){addFirst(data);return;}if (index == size()){addLast(data);return;}/*ListNode node = new ListNode(data);ListNode cur = head;int tmp = index - 1;while (tmp != 0){cur = cur.next;tmp--;}node.next = cur.next;cur.next = node;*///将上面这一坨封装ListNode cur = findIndexSubOne(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}/*** 找到要删除节点位置的前一个节点* @param index* @return*/private ListNode findIndexSubOne(int index){ListNode cur = head;int tmp = index - 1;while (tmp != 0){cur = cur.next;tmp--;}return cur;}

3.9 删除第一次出现关键字为key的节点

效果图如下:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XNjLHKsz-1691313293628)(E:\Typora_note\数据结构笔记\Java\链表.assets\image-20230804163610766.png)]

  • 对于删除第一次出现的key值的节点,若不是头节点,我们只需将key值对应的节点的前一节点的next的域改为key值对应的节点的next域即可。

  • 对于头节点,直接head = head.next即可。

  1. 找到要删除节点的前一个节点
  2. 此时要删除的节点del = cur.next;
  3. 进行删除cur.next = del.next

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3Z4twZk9-1691313293628)(https://gitee.com/liuhb-clanguage/picture/raw/master/png/image-20230804165759876.png)]

//删除第一次出现关键字为key的节点public void remove(int key){if (head == null){return;}//单独删除头节点if (head.val == key){head = head.next;return;}ListNode cur = searchPrev(key);if (cur == null){System.out.println("没有你要删除的数字!");return;}ListNode del = cur.next;cur.next = del.next;}/*** 找到关键字key的前驱* @param key* @return*/private ListNode searchPrev(int key){ListNode cur = head;while (cur.next != null){if (cur.next.val == key){return cur;}cur = cur.next;}return null;}

3.10 删除所有值为key的节点

情景如下:

将值为23的删除

有种暴力的方法,我们只需要多次调用3.9种的remove函数即可,但是这并不是我们真正想要的,要求:遍历一遍就要删除完。

如图分析:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XnRqeEfk-1691313293628)(https://gitee.com/liuhb-clanguage/picture/raw/master/png/image-20230806160715303.png)]

//删除所有值为key的节点public void removeAllKey(int key){ListNode prev = head;ListNode cur = head.next;if (head == null){return;}while (cur != null){if(cur.val == key){prev = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if (head.val == key){head = head.next;}}

3.11 清空

简单粗暴:

public void clear() {this.head = null;}

温柔:

    public void clear(){while(this.head != null){ListNode curNext = this.head.next;this.head.next = null;this.head = cur.next;}}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL 重置root 密码

5.7 版本 首先要把服务mysql57 关闭 net stop MySQL57 在安装的mysql57的程序的bin中 运行cmd&#xff08;管理员运行&#xff09; mysqld --defaults-file‘mysql存放数据的位置\my.ini’ --skip-grant-tables 上图 错误 注意&#xff1a;如果遇到mysqld: Can’t change dir…

【从零学习python 】02. 开发工具介绍

文章目录 编写Python代码一、常见的代码编辑工具二、运行Python程序三、Pycharm的下载和安装PyCharm的主要功能区域进阶案例 编写Python代码 根据我们之前介绍的知识&#xff0c;我们知道&#xff0c;所谓代码其实就是将一段普通文本按照一定的规范编写&#xff0c;然后交给电…

Cesium 加载ArcGIS Server切片服务错级问题

1.首先上官方api说明 ArcGisMapServerImageryProvider - Cesium Documentation 里面没有 zoomoffset参数!!! 2.如果按照互联网栅格切片规则 3857、4326、4490常用切片层级参数,则直接加载显示地图 viewer.imageryLayers.addImageryProvider(new Cesium.ArcGisMapServerI…

【Spring Boot】(三)深入理解 Spring Boot 日志

文章目录 前言一、日志文件的作用二、Spring Boot 中的日志2.1 查看输出的日志信息2.2 日志格式二、Spring Boot 中的日志2.1 查看输出的日志信息2.2 日志格式 三、自定义日志输出3.1 日志框架3.2 日志对象的获取3.3 使用日志对象打印日志 四、日志级别4.1 日志级别的作用4.2 日…

Oracle-expdp报错ORA-39077、06502(Bug-16928674)

问题: 用户在使用expdp进程导出时&#xff0c;出现队列报错ORA-39077、ORA-06502 ORA-31626: job does not exist ORA-31638: cannot attach to job SYS_EXPORT_SCHEMA_01 for user SYS ORA-06512: at "SYS.DBMS_SYS_ERROR", line 95 ORA-06512: at "SYS.KUPV$…

【修正-高斯拉普拉斯滤波器-用于平滑和去噪】基于修正高斯滤波拉普拉斯地震到达时间自动检测研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

解密HTTP代理爬虫中的IP代理选择与管理策略

在当今数据驱动的世界中&#xff0c;HTTP代理爬虫作为一项重要的数据采集工具&#xff0c;其成功与否往往取决于IP代理的选择与管理策略。作为一家专业的HTTP代理产品供应商&#xff0c;我们深知IP代理在数据采集中的重要性。在本文中&#xff0c;我们将分享一些关于HTTP代理爬…

图像膨胀+滤波达到边缘外扩模糊效果

有一个扯淡需求, 根据某些格网值渲染对应的颜色, 我们做的实现方案是按照色代码渐变做颜色映射, 但是某些厂家不顾结果正确性与否, 应是为了好看做的好看, 将边界膨胀模糊, 一个非风场,力场类似场数据做了一个类似场的渲染效果, 也不知道说啥好, 例如原始图渲染如下 经过一系列…

Spring Boot配置文件与日志文件

1. Spring Boot 配置文件 我们知道, 当我们创建一个Spring Boot项目之后, 就已经有了配置文件存在于目录结构中. 1. 配置文件作用 整个项目中所有重要的数据都是在配置文件中配置的&#xff0c;比如: 数据库的连接信息 (包含用户名和密码的设置) ;项目的启动端口;第三方系统的调…

资深测试总结,Web自动化测试POM设计模式封装框架,看这篇就够了...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 线性脚本 import…

ParallelCollectionRDD [0] isEmpty at KyuubiSparkUtil.scala:48问题解决

ParallelCollectionRDD [0] isEmpty at KyuubiSparkUtil.scala:48问题解决 这个问题出现在使用Kyubi Spark Util处理ParallelCollectionRDD的过程中&#xff0c;具体是在KyubiSparkUtil.scala文件的第48行调用isEmpty方法时出现的。该问题可能是由以下几个原因引起的&#xff1…

FFmpeg将编码后数据保存成mp4

以下测试代码实现的功能是&#xff1a;持续从内存块中获取原始数据&#xff0c;然后依次进行解码、编码、最后保存成mp4视频文件。 可保存成单个视频文件&#xff0c;也可指定每个视频文件的总帧数&#xff0c;保存多个视频文件。 为了便于查看和修改&#xff0c;这里将可独立的…

[CKA]考试之检查可用节点数量

由于最新的CKA考试改版&#xff0c;不允许存储书签&#xff0c;本博客致力怎么一步步从官网把答案找到&#xff0c;如何修改把题做对&#xff0c;下面开始我们的 CKA之旅 题目为&#xff1a; Task 检查集群中有多少节点为Ready状态&#xff08;不包括被打上 Taint&#xff1…

FPGA学习——Altera IP核调用之PLL篇

文章目录 一、IP核1.1 IP核简介1.2 FPGA中IP核的分类1.3 IP核的缺陷 二、PLL简介2.1 什么是PLL2.2 PLL结构图2.3 C4开发板上PLL的位置 三、IP核调用步骤四、编写测试代码五、总结 一、IP核 1.1 IP核简介 IP核&#xff08;知识产权核&#xff09;&#xff0c;是在集成电路的可…

视频监控汇聚平台EasyCVR视频分享页面WebRTC流地址播放不了是什么原因?

开源EasyDarwin视频监控TSINGSEE青犀视频平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;TSINGSEE青犀视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多…

机器学习笔记之优化算法(八)简单认识Wolfe Condition的收敛性证明

机器学习笔记之优化算法——简单认识Wolfe Condition收敛性证明 引言回顾&#xff1a; Wolfe \text{Wolfe} Wolfe准则准备工作推导条件介绍推导结论介绍 关于 Wolfe \text{Wolfe} Wolfe准则收敛性证明的推导过程 引言 上一节介绍了非精确搜索方法—— Wolfe \text{Wolfe} Wolf…

【Python】从同步到异步多核:测试桩性能优化,加速应用的开发和验证

目录 测试工作中常用到的测试桩mock能力 应用场景 简单测试桩 http.server扩展&#xff1a;一行命令实现一个静态文件服务器 性能优化&#xff1a;使用异步响应 异步响应 能优化&#xff1a;利用多核 gunicorn 安装 gunicorn 使用 gunicorn 启动服务 性能优化&#…

linuxARM裸机学习笔记(2)----汇编LED灯实验

MX6ULL 的 IO IO的复用功能 这里的只使用了低五位&#xff0c;用来配置io口&#xff0c;其中bit0~bit3(MUX_MODE)就是设置 GPIO1_IO00 的复用功能的&#xff0c;GPIO1_IO00 一共可以复用为 9种功能 IO&#xff0c;分别对应 ALT0~ALT8。每种对应了不同的功能 io的属性配置 HY…

MATLAB(R2023a)添加工具箱TooLbox的方法-以GPOPS为例

一、找到工具箱存放位置 首先我们需要找到工具箱的存放位置&#xff0c;点击这个设置路径可以看到 我们的matlab工具箱的存放位置 C:\Program Files\MATLAB\R2023a\toolbox\matlab 从资源管理器中打开这个位置&#xff0c;可以看到里面各种工具箱 二、放入工具箱 解压我们…

【docker】docker私有仓库

目录 一、说明二、私有仓库搭建三、上传镜像到私有仓库四、从私有仓库拉取镜像 一、说明 1.docker官方的docker hub(https://hub.docker.com)是一个用于管理公共镜像的仓库&#xff0c;可以从上面拉取镜像到本地&#xff0c;也可以把自己的镜像推送上去 2.若服务器无法访问互联…