【数据结构】模拟实现无头单向非循环链表
链表的概念
学过ArrayList后我们知道它的底层是用数组来存储元素的,是连续的存储空间,当我们要从ArrayList任意位置删除或插入元素时,我们要把后续整体向前或后移动,时间复杂度为O(n),效率比较低,因此ArrayList不适合做需要过多任意位置插入或删除的场景,这种场景我们使用LinkedList(链表)比较合适。
链表的一个节点分为值域(存储的是节点的值)和指针域(存储的是下一个节点的地址),链表的逻辑顺序是连续的,但物理地址不一定是连续的因为节点是从堆中申请出来的,从堆中申请的空间是按照一定的策略分配的,两次申请的空间可能是连续的,也有可能不连续。
模拟实现无头单向非循环链表
//无头单向非循环链表实现
public class SingleLinkedList {static class ListNode{public int val;//节点值域public ListNode next;//节点指针域 下一个节点的地址public ListNode(int val) {this.val = val;}}ListNode head;//当前链表的头节点//初始化一个简单的链表public void createList(){ListNode node1 = new ListNode(11);ListNode node2 = new ListNode(22);ListNode node3 = new ListNode(33);ListNode node4 = new ListNode(44);ListNode node5 = new ListNode(55);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}
}
链表常用的方法
//头插法
public void addFirst(int data)//尾插法
public void addLast(int data)//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data)//查找是否包含关键字key是否在单链表当中
public boolean contains(int key)//删除第一次出现关键字为key的节点
public void remove(int key)//删除所有值为key的节点
public void removeAllKey(int key)//得到单链表的长度
public int size()//清除链表
public void clear()
实现addFirst方法(头插法)
public void addFirst(int data) {ListNode node = new ListNode(data);//让要插入的节点的指针域指向头节点node.next = head;//让插入的节点成为头节点head = node;
}
实现addList方法(尾插法)
要实现尾插法,我们就必须要找到最后一个节点,所以我们要遍历链表,遍历链表的时候我们可以定义一个节点指向头节点然后让定义的节点向后去遍历链表
public void addLast(int data) {ListNode node = new ListNode(data);//定义一个节点cur指向头节点ListNode cur = head;//判断链表是否为空 如果为空就直接插入if (cur==null){head = node;return;}//遍历链表找到最后一个节点while (cur.next!=null){cur = cur.next;}//插入节点cur.next = node;
}
实现size方法(获取链表的长度)
public int size() {//定义一个变量来记录链表长度int count = 0;ListNode cur = head;//遍历链表while (cur!=null){count++;cur = cur.next;}return count;
}
实现addIndex方法(在任意位置插入元素)
public void addIndex(int index, int data) {//判断要插入的位置是否合法if (index<0||index>size()){System.out.println("index 不合法"+index);return;}//index为0 我们使用头插if (index==0){addFirst(data);return;}//index等于链表的长度我们可以使用尾插if (index==size()){addLast(data);return;}ListNode node = new ListNode(data);ListNode cur = head;for (int i = 0; i < index-1; i++) {cur = cur.next;}node.next = cur.next;cur.next = node;
}
实现contains方法(查找是否包含关键字key是否在单链表当中)
public boolean contains(int key) {ListNode cur = head;//如果链表为空直接返回falsewhile (cur!=null){//判断是否是key 是返回true 不是则遍历下一个节点if (cur.val==key){return true;}cur = cur.next;}return false;
}
实现remove方法(删除第一次出现关键字为key的节点)
我们可以先定义一个方法查看key是否在链表中
private ListNode searchKey(int key){ListNode cur = head;while (cur.next!=null){//判断cur是否是要删除节点的前一个节点if (cur.next.val==key){return cur;}cur = cur.next;}return null;
}
public void remove(int key) {//判断链表是否为空if (head==null){return;}//判断头节点是否为要删除的节点if (head.val==key){head = head.next;return;}//查找key是否在链表中 不在则返回nullListNode cur = searchKey(key);if (cur==null){System.out.println("没有key的节点"+key);return;}//因为cur是要删除节点的前一个节点 所以cur.next才是要删除的节点ListNode del = cur.next;cur.next = del.next;
}
实现removeAllKey方法(删除所有值为key的节点)
public void removeAllKey(int key) {//判断链表是否为空if (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;}
}
实现clear方法(清除链表)
//只需将头节点置为空即可
public void clear() {head = null;
}
相关文章:
【数据结构】模拟实现无头单向非循环链表
链表的概念 学过ArrayList后我们知道它的底层是用数组来存储元素的,是连续的存储空间,当我们要从ArrayList任意位置删除或插入元素时,我们要把后续整体向前或后移动,时间复杂度为O(n),效率比较低,因此Arra…...
linux驱动开发学习001:概述
linux的内核源码编译后,会生成一个总的镜像。镜像加载到内存中运行他,就会启动内核。驱动属于内核代码的一部分,对驱动修改要重编整个内核,麻烦但驱动可以独立于内核镜像外,并能动态加载和卸载字符设备驱动,…...
安全响应中心 — 垃圾邮件事件报告(10.13)
2023年10月 第二周 一. 样本概况 ✅ 案例1:DocuSign钓鱼 本周收到一封看似来自 DocuSign(DocuSign 是一种在企业环境中广泛使用的电子协议管理平台)的网络钓鱼电子邮件反馈。 如下图所示: 以上样本内容大体是说XX发送了一份文…...
扩散模型Diffusers Pipeline API使用介绍
1 关于Diffusers Pipeline 1.1 简介 大部分扩散模型包含多个独立训练的子模型和组件模块组合而成,例如StableDiffusion 有: 3个独立训练的子模型:Autoencoder、 Conditional Unet、CLIP text encoder调度器组件scheduler,CLIPImageProcesso…...
el-date-picker 组件 监听输入的内容 并按照时间格式 格式化
这个时间选择组件在输入的时候是监听不到输入的值的,所以我们在外层再套个div,然后用获取焦点事件去操作dom 页面中 <div id"inParkingData"><el-date-pickerv-model"indateRange"size"small"value-format"…...
组件通信$refs | $parent |$root
父组件传值子组件用Props 子组件传值父组件用$emit 父组件直接还可以直接取子组件的值用$refs 父组件直接从子子组件中获取值$refs 不建议使用会增加组件之间的耦合度,一般用于第三方插件的封装 ref如果绑定在dom节点上,拿到的就是原生dom节点。 ref如…...
springboot中@Async的使用
1.AsyncAnnotationBeanPostProcessor是主要逻辑类 (1)AsyncAnnotationBeanPostProcessor实现BeanFactoryAware接口 在setBeanFactory(BeanFactory beanFactory)中初始化advisorAsyncAnnotationAdvisor() (2)AsyncAnnotationBeanPostProcessor实现BeanPostProcessor接口 在p…...
学C++从CMake学起
Cmake在此引入c17编译器,就可以使用c17的新特性了。 c17定义了一些算法,都定义在了下面这个头文件里。 #include <numeric> 通过redurce函数求和 将9行的std::plus{}换成std::times{}就是相乘。...
lv8 嵌入式开发-网络编程开发 20 域名解析与http服务实现原理
目录 1 域名解析 2 如何实现万维网服务器? 2.1 HTTP 的操作过程 2.2 万维网服务器实现 1 域名解析 域名解析gethostbyname函数 主机结构在 <netdb.h> 中定义如下: struct hostent {char *h_name; /* 官方域名 */char **h_alias…...
只要路由器有WPS按钮,佳能打印机连接到Wi-Fi网络的方法就很简单
佳能打印机是很好的设备,可以让你从智能手机、电脑或平板电脑打印照片。它们还提供其他功能,如扫描文档和复制图像。 最新的型号还允许你连接到Wi-Fi,因此你不需要使用电线将设备连接到打印机。 Wi-Fi是通过本地网络传输数据的标准方式。它…...
Cmake输出git内容方式
实现背景 在定位问题时,固件无法获取当前设备中版本的详细信息,无法准确获取版本具体内容 输出效果 实现方式 以下是基于Cmake的语法实现 在CMake中获取git信息,可以通过execute_process命令运行git命令并将结果保存在一个变量中。然后可…...
实现多余内容变成省略号
实现效果 代码 <p class"item-content">{{ item.content }}</p>样式 .item-content {white-space: nowrap;/* 禁止换行 */overflow: hidden;/* 隐藏溢出部分 */text-overflow: ellipsis;/* 使用省略号表示溢出部分 */ }...
WAL 模式(PostgreSQL 14 Internals翻译版)
性能 当服务器正常运行时,WAL文件不断被写入磁盘。但是,这些写操作是顺序的:几乎没有随机访问,因此即使是HDD也可以处理这个任务。由于这种类型的加载与典型的数据文件访问非常不同,因此有必要为WAL文件设置一个单独的物理存储&a…...
2023年信息科学与工程学院学生科协第二次软件培训
2023年信息科学与工程学院学生科协第二次软件培训 文章目录 2023年信息科学与工程学院学生科协第二次软件培训一维数组数组的概念定义格式一维数组的访问例题:练习题: 数组元素数量一维数组的初始化 二维数组定义格式二维数组的访问二维数组的存储结构二…...
渗透测试tomcat错误信息泄露解决办法
解决方法: 1、使用tomcat8.5.16,会重定向非法url到登录url 2、配置server.xml,加上 <Valve className"org.apache.catalina.valves.ErrorReportValve" showReport"false" showServerInfo"false" />配置…...
notes_NLP
RNN > LSTM, GRU model特点RNNLSTMinputforgetputput;GRUresetupdate;参数比LSTM少,计算效率更高; 循环神经网络(RNN/LSTM/GRU) 人人都能看懂的GRU transformer > self-attention 根据Query和Key计…...
内存分段、分页
大家好,我叫徐锦桐,个人博客地址为www.xujintong.com。平时记录一下学习计算机过程中获取的知识,还有日常折腾的经验,欢迎大家访问。 前言 每个进程都有一套自己的虚拟地址,尽管进程可能有相同的虚拟地址,…...
Python-pptx教程之一从零开始生成PPT文件
简介 python-pptx是一个用于创建、读取和更新PowerPoint(.pptx)文件的python库。 典型的用途是根据动态内容(如数据库查询、分析数据等),将这些内容自动化生成PowerPoint演示文稿,将数据可视化,…...
k8s 使用ingress-nginx访问集群内部应用
k8s搭建和部署应用完成后,可以通过NodePort,Loadbalancer,Ingress方式将应用端口暴露到集群外部,提供外部访问。 缺点: NodePort占用端口,大量暴露端口非常不安全,并且有端口数量限制【不推荐】…...
企业数据泄露怎么办?
随着数字化时代的到来,威胁企业数据安全的因素越来越多。一旦机密数据泄露,不仅会对企业造成巨大的经济损失,还会对企业的声誉和客户信任度造成严重影响。发生数据泄露情况时,企业该怎样应对? 1.确认数据泄露 确认是…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
实战设计模式之模板方法模式
概述 模板方法模式定义了一个操作中的算法骨架,并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下,重新定义算法中的某些步骤。简单来说,就是在一个方法中定义了要执行的步骤顺序或算法框架,但允许子类…...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一:yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因,后面把yaml.safe_dump直接替换成yaml.dump,确实能保存,但出现乱码: 放弃yaml.dump,又切…...
