数据结构:链表(1)

顺序表的优缺点

缺点:

1.插入数据必须移动其他数据,最坏情况下,就是插入到0位置。时间复杂度O(N)

2.删除数据必须移动其他数据,最坏情况下,就是删除0位置。时间复杂度O(N)

3.扩容之后,有可能会浪费空间。

优点:

在给定下标进行查找的时候

总结:顺序表比较适合进行给定下路查找的场景

🆗链表可以完美解决顺序表的缺点


链表是什么?

一个链表其实就是一辆火车

火车的每个车厢相当于一个节点,链表节点长这样

其中,数据域存储数据 

而火车之间要有挂钩链接,这就需要next域出马了,next读取下一个节点的地址并把它记录在next域里面,下面这个图也是单向链表,一条路走到黑

分类

有六种分类

常见的是红色圈起来的两个

带头的长啥样?头部存的数据是无效的,跟这个链表没有关系,这个头节点的值永远不会改变

循环的?

双向的?两边都能走

链表结构特点:物理上不一定是连续的,但逻辑上是连续的


单向链表

手搓一个

初始化

实现方法有下面这些

//IList.java 接口
public interface IList {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}

再新建一个模块重写这些方法

public class MySingleList implements IList{@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}
}

ok!接下来我们要设置一个节点的内部类把要用到的属性加上

    static class ListNode{public int val;public ListNode next; //定义next域//节点类构造方法public ListNode(int val){this.val = val;}}

为什么是static呢?因为每个节点都一样,都由数据域和next域组成的,直接static定义共同特点。

那第三行的ListNode next 怎么理解呢?因为next指向的是下一个节点的地址,而下一个节点的类型也是ListNode,所以这里的next一定是ListNode类型


好接下来定义一个链表的头

public ListNode head;

注意不要放到内部类里面,因为head是链表的成员而不是节点的成员

给几个节点赋上值

1.如何让node1的下一个节点是node2

node1.next = node2 //表示node2地址0x46给到node1

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

node1是局部变量,整个过程走完之后node1会被回收怎么办?

两种方法:

第一种,把刚刚那个函数类型改成ListNode,函数返回node1

第二种,我们不是定义了head了吗,直接在函数末尾写上

this.head = node1;    这样就行了

检验结果


遍历列表

1.怎么从一个节点走到下一个节点

2.怎么判断所有节点都遍历完了

一个循环,循环终止条件是head为空,我们按照这个思想把display代码完成

这个代码有一个问题,遍历完列表之后head为空,整个头节点地址和值全都无了

解决办法是创一个中间变量cur把head锁死,遍历完之后cur为空了,但是head本质上不会变

    @Overridepublic void display() {ListNode cur = this.head;while(cur != null){System.out.println(cur.val + " ");cur = cur.next;}}

有这个代码的基础,链表长度和包含函数也不在话下

    @Overridepublic int size() {int count = 0;ListNode cur = this.head;while(cur != null){cur = cur.next;count++;}return count;}@Overridepublic boolean contains(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}

头插法

链表里面有节点

三步走

1. 实例化一个节点

2.改变插入节点的next

3.改变head

无节点

直接把head定义成这个节点

    @Overridepublic void addFirst(int data) {//实例化节点对象ListNode node = new ListNode(data);//无节点if(this.head == null){this.head = node;//有节点}else{node.next = this.head;this.head = node;}}

注意这个插入是倒叙插入 


尾插法

指的是将待插入的节点存放到链表的最后一个位置

步骤:

1.实例化一个节点

2.把cur走到最后一个节点

3.cur.next = node; //插入下一个节点

    @Overridepublic void addLast(int data) {ListNode node = new ListNode(data);ListNode cur = this.head;if (this.head == null){this.head = node;}else {//找到尾巴while (cur.next != null) {cur = cur.next;}//cur现在指向最后一个节点cur.next = node;}}

如果想要让cur停在最后一个节点的位置 cur.next != null;

如果想把整个链表都遍历完,就是cur != null;

注意:尾插法时间复杂度是O(N),因为要遍历完整个链表n个节点后才插入元素


在任意位置插入节点

1.让cur走index-1步

2.node.next = cur.next;

cur.next = node;

在插入一个节点的时候,一定要先绑定后面这个节点

    @Overridepublic void addIndex(int index, int data) {if(index < 0 || index > size()){return;}if(index == size()){addLast(data);return;}ListNode cur = searchPrev(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}private ListNode searchPrev(int index){ListNode cur = this.head;int count = 0;while(count!=index-1){cur = cur.next;count++;}return cur;}

删除元素

现在我们想删除第三个节点,把第三个节点设成del

在一个循环里面让cur遍历整个链表

判断 cur.next.val == key,找到cur的位置

后面cur = cur.next

    @Overridepublic void remove(int key) {if(this.head == null){//一个节点都没有,删除不了return;}//删除头节点if(this.head.val == key){this.head = this.head.next;return;}//1、找到前驱ListNode cur = findPrev(key);//2、判断返回值是否为空?if(cur == null){System.out.println("没有你要删除的数字");return;}//3、删除ListNode del = cur.next;cur.next = del.next;}//找到关键字key的前一个节点的地址private ListNode findPrev(int key){ListNode cur = this.head;while(cur.next!=null){if(cur.next.val == key){return cur;}}return null;}

删除所有值为key的节点 

比如下面删除所有值为23的节点

定义cur为当前要删除的节点

prev为当前要删除的节点的前驱

cur找到了就直接把prev的next地址改成cur下一个节点的地址,cur继续往下遍历

while(cur!=null){

        if(cur.val == key){

                prev.next = cur.next; //删除操作

                cur = cur.next;

        }else{

                prev = cur;

                cur = cur.next

        }

}

    @Overridepublic void removeAllKey(int key) {if(this.head == null){return;}ListNode prev = head;ListNode cur = head.next;while(cur!=null){if(cur.val == key){prev.next = cur.next;cur = cur.next;//不等于就往下走}else{prev = cur;cur = cur.next;}}if(head.val == key){head = head.next;}}

清空链表

把一个节点的val = null, next = null

再把链表的head = null

注意:这里的val = null不是直接让你 cur.val = null,拿第一个节点来说,如果你把值置为空,那么0x46被替换成null,cur找不到下一个节点的地址0x46了

我们可以拿一个变量curNext来记录cur下一个节点的位置,把cur.next 置为空之后,cur往后挪到curNext的位置,继续置空下一个节点

注意别忘了头节点,整个遍历完之后还要把头节点也置为空

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

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

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

相关文章

游戏服务端性能测试实战总结

导语&#xff1a;近期经历了一系列的性能测试&#xff0c;涵盖了Web服务器和游戏服务器的领域。在这篇文章中&#xff0c;我将会对游戏服务端所做的测试进行详细整理和记录。需要注意的是&#xff0c;本文着重于记录&#xff0c;而并非深入的编程讨论。在这里&#xff0c;我将与…

mysql面试题35:MySQL有关权限的表有哪些?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:MySQL有关权限的表有哪些? MySQL中与权限相关的表主要包括以下几个: user表:存储MySQL用户的基本信息,包括用户名、密码等。可以使用以下命令…

sqlalchemy 连接池

报错 sqlalchemy.exc.TimeoutError: QueuePool limit of size 100 overflow 10 reached, connection timed out, timeout 30 (Background on this error at: http://sqlalche.me/e/3o7r) 查看数据库未活动超时时间 show variables like "interactive_timeout";一般…

CAN和CANFD通信介绍

CAN&#xff08;Controller Area Network&#xff0c;控制器局域网&#xff09;是一种串行通信技术&#xff0c;专门用于在汽车电子控制单元&#xff08;ECU&#xff09;之间实现可靠的数据交换。 CAN协议介绍 电子化 汽车近年来的发展呈现出以电子化为主的特点。电子化的主…

虚幻引擎:如何才能对音波(声音资产)进行逻辑设置和操作

案列&#xff1a;调整背景音乐大小 1.创建一个SoundCue 2.进入创建的SoundCue文件 3. 创建音效类和音效类混合 4.进入SoundCue选择需要的音效类 5.然后音效类混合选择相同的音效类 6.然后蓝图中通过节点进行控制音量大小

C#实现五子棋小游戏:简单、有趣的编程项目

目录 引言什么是五子棋游戏规则开发环境准备安装C#开发环境选择合适的集成开发环境(IDE)游戏设计与功能分析游戏界面设计实现棋盘的绘制与操作实现落子功能实现输赢判断说明引言 什么是五子棋 五子棋是一种源于中国的传统棋类游戏,常见于中国、日本、韩国等亚洲国家,是亚洲…

Maven创建父子工程详解

引言 在微服务盛行的当下&#xff0c;我们创建的工程基本都是父子工程&#xff0c;我们通过父工程来引入jar&#xff0c;定义统一的版本号等&#xff0c;这样我们在子工程中就可以直接引用后使用了&#xff0c;而不需要去重复的声明版本号等&#xff0c;这样会更方便对整个项目…

测试老鸟整理,Pytest自动化测试框架的一些关键点,一文贯通...

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

机器学习、深度学习相关的项目集合【自行选择即可】

【基于YOLOv5的瓷砖瑕疵检测系统】 YOLOv5是一种目标检测算法&#xff0c;它是YOLO&#xff08;You Only Look Once&#xff09;系列模型的进化版本。YOLOv5是由Ultralytics开发的&#xff0c;基于一阶段目标检测的概念。其目标是在保持高准确率的同时提高目标检测的速度和效率…

Flink开发环境搭建与提交运行Flink应用程序

Flink开发环境搭建与提交运行Flink应用程序 Flink概述环境 Flink程序开发项目构建添加依赖安装Netcat实现经典的词频统计批处理示例流处理示例 Flink Web UI 命令行提交作业编写Flink程序打包上传Jar提交作业查看任务测试 Web UI提交作业提交作业测试 Flink 概述 Apache Flink…

MinIO的安装与使用

文章目录 1.MINIO是什么&#xff1f;2.MINIO安装3.启动脚本4.打开MINIO页面5.MC命令6.MINIO备份脚本 1.MINIO是什么&#xff1f; MinIO 是一款高性能、分布式的对象存储系统. 它是一款软件产品, 可以100%的运行在标准硬件。即X86等低成本机器也能够很好的运行MinIO。 MinIO与…

alsa音频pcm设备之i2c调试

i2cdetect 列举 I2C bus i2cdetect -l ls /dev/i2c* 列出I2C bus i2c-7 上面连接的所有设备,并得到i2c设备地址 i2cdetect -y 7 发现i2c设备的位置显示为UU或表示设备地址的数值,UU表示设备在driver中被使用. I2cdump i2c设备大量register的值 i2cdump -y 7 0x40 I2cset设置…

ICPC 2019-2020 North-Western Russia Regional Contest

A (codeforces.com) 这题在移动不被挡板挡住以及不超过边界的情况下&#xff0c;每次走的越多那么次数就越少 只要两个每次都走b-a步&#xff08;已经是不被挡板挡住走的最多了&#xff09;&#xff0c;就不用考虑被挡板挡住的情况&#xff0c;只用单独考虑了&#xff0c;如果…

微服务09-Sentinel的入门

文章目录 微服务中的雪崩现象解决办法&#xff1a;1. 超时处理2. 舱壁模式3. 熔断降级4.流量控制 Sentinel1.介绍2.使用操作3.限流规则4.实战&#xff1a;流量监控5.高级选项功能的使用1.关联模式2.链路模式3.总结 流控效果1.预热模式2.排队等待模式3.总结4.热点参数限流5.实战…

【业务功能篇 131】23种设计模式介绍

第一章 设计模式概述 1.1 代码质量好坏如何评价? 要想学习设计模式呢 我们就必须搞清楚设计模式到底在我们的编程过程中起到了怎样的作用,在编程世界中它处在一个什么样的位置,它到底是一种抽象的设计思想,还是一套具体的落地方案. 在学习设计模式之前呢 我们需要了解一下 代…

【数据结构C/C++】顺序与链式二叉树创建与前中后、层序遍历

文章目录 顺序存储结构二叉树链式存储结构二叉树刷题推荐408考研各数据结构C/C代码&#xff08;Continually updating&#xff09; 顺序存储结构二叉树 顺序存储结构的二叉树的特点在于&#xff0c;其使用数组存放二叉树中的每一个节点。 我们设定根节点的数组索引下标为n&…

MYSQL的日志管理

MySQL中有几种类型的日志记录&#xff0c;分别用于记录不同的操作和事件。以下是MySQL中常见的日志类型 错误日志 错误日志是 MySQL 中最重要的日志之一&#xff0c;它记录了当 mysqld 启动和停止时&#xff0c;以及服务器在运行过程中发生任何严重错误时的相关信息。当数据…

linux后台运行java项目/ jar包:nohup 命令

1.提出问题 我们把一个 SpringBoot 工程导出为 jar 包&#xff0c;jar 包上传到阿里云 ECS 服务器上&#xff0c;使用 java -jar xxx-xxx.jar 命令启动这个 SpringBoot 程序。此时我们本地的 xshell 客户端必须一直开着&#xff0c;一旦 xshell 客户端关闭&#xff0c;java -j…

Jenkins对应java版本

官网地址&#xff1a;Java Support Policy 运行jenkins时,需要使用下列Java版本:

Jenkins安装多个jdk版本,并在项目中选择对应jdk版本

下载jdk版本&#xff1a;进入oracle官网下载官方jdk Java Downloads | Oracle 例&#xff1a;比如项目需要使用java8.341的版本&#xff0c;而jenkins用的是java11的版本&#xff0c;这里就需要下载多个jdk版本。进入下载网址&#xff0c;Java Archive Downloads - Java SE 8u…