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

【Java数据结构】LinkedList与链表

认识LinkedList

        LinkedList就是一个链表,它也是实现List接口的一个类。LinkedList就是通过next引用将所有的结点链接起来,所以不需要数组。LinkedList也是以泛型的方法实现的,所以使用这个类都需要实例化对象。

        链表分为很多种,比较常用的就两种:单链表(单向、不带头、非循环)和双链表(双向、不带头、非循环),后面会模拟实现。下面是顺序表和链表的区别:

模拟实现LinkedList

单链表

        首先需要创建结点,但是它比顺序表多了一个next引用,可以通过next引用来访问下一个结点,不再需要通过连续地址访问,首先先创建结点这个类, 然后再实现增删查改等这些方法:

链表长度、遍历链表、头插法、尾插法、任意位置插入、查找关键字key是否在链表中 、删除第一次出现关键字为key的节点、删除所有值为key的节点、清空。

public class MySingle {static class ListNode{private int val;private ListNode next;public ListNode(int val){this.val = val;}}private ListNode head;//头插法public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if (head == null){head = node;}else {ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}}//任意位置插入public void addIndex(int index,int data){if (index < 0 || index > size()){throw new IndexOutOfException("位置不合法!");}if (index == 0){addFirst(data);return;}ListNode node = new ListNode(data);ListNode cur = head;while (index - 1 != 0){cur = cur.next;index--;}//将index位置前后两个节点和新结点联系起来node.next = cur.next;cur.next = node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null){if (cur.val == key){return true;}}return false;}public ListNode keyPre(int key){ListNode cur = head;while (cur.next != null){if (cur.next.val == key){return cur;}cur = cur.next;}return null;}//删除第一次出现关键字为key的节点public void remove(int key){if (head == null){return;}if (head.val == key){head = head.next;return;}//找到key结点的前一个结点ListNode pre = keyPre(key);ListNode del = pre.next;pre.next = del.next;}//删除所有值为key的节点public void removeAllKey(int key){ListNode pre = head;ListNode cur = head.next;while (cur != null){if (cur.val == key){pre.next = cur.next;cur = cur.next;}else{pre = pre.next;cur = cur.next;}}if (head.val == key){head = head.next;}}//得到单链表的长度public int size(){int count = 0;ListNode cur = head;while (cur != null){count++;cur = cur.next;}return count;}public void display(){ListNode cur = head;while (cur != null){System.out.print(cur.val+"  ");cur = cur.next;}System.out.println();}
}

双链表(LinkedList)

        LinkedList其实就是一个双链表, 它既可以访问前驱又可以访问后继,所以可以快速插入和删除。下面是LinkedList模拟实现,比较难的就是插入和删除:

public class MyLinkedList {static class ListNode{private int val;private ListNode prev;private ListNode next;public ListNode(int val){this.val = val;}}public ListNode head;public ListNode tail;//头插法public void addFirst(int data){ListNode node = new ListNode(data);if (head == null){head = node;tail = node;}else {head.prev = node;node.next = head;head = node;}}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if (tail == null){head = node;tail = node;}else{tail.next = node;node.prev = tail;tail = node;//tail = tail.next;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if (index < 0 || index > size()){throw new IndexOutofBoundException(index+"位置不合理!");}ListNode node = new ListNode(data);ListNode cur = head;while (index > 0){cur = cur.next;index--;}node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null){if (cur.val == key){return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if (head == null){return ;}ListNode cur = head;while(cur != null ) {if (cur.val == key){if (cur.next == null && cur.prev == null){head = null;tail = null;return;}if (cur.prev == null) {head = cur.next;cur.next.prev = null;return;}if(cur.next == null){tail = cur.prev;cur.prev.next = null;return;}cur.prev.next = cur.next;cur.next.prev = cur.prev;return;}else{cur = cur.next;}}}//删除所有值为key的节点public void removeAllKey(int key){if (head == null){return ;}ListNode cur = head;while(cur != null ) {if (cur.val == key){if (cur.next == null && cur.prev == null){head = null;tail = null;}else if (cur.prev == null) {head = cur.next;cur.next.prev = null;}else if(cur.next == null){tail = cur.prev;cur.prev.next = null;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}cur = cur.next;}else{cur = cur.next;}}}//得到单链表的长度public int size(){ListNode cur = head;int size = 0;while (cur != null){size++;cur = cur.next;}return size;}//清空public void clear(){ListNode cur = head;while(cur != null){ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}head = null;tail = null;}//遍历public void display(){ListNode cur = head;while (cur != null){System.out.print(cur.val+"   ");cur = cur.next;}System.out.println();}
}

LinkedList的创建

构造一个对象,可以无参构造(较为常用,在其里初始化一个数组)。 

LinkedList的遍历

        遍历的方法和ArrayList里一样,三种:for循环、增强for循环、迭代器。这两个遍历方法都是一样的,就不重复叙述。https://blog.csdn.net/2402_84815218/article/details/144038207?spm=1001.2014.3001.5502

LinkedList常用方法

 这些方法和ArrayList中的方法差不多都一样,只是实现的过程不一样。这里我就举几个例子:

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(12);//尾插进入list.add(23);System.out.println(list);//【12,23】
//        list.add(3, 100);//插入到第index位置,但是该list中没有第三个位置
//        System.out.println(list);System.out.println(list.get(1));//得到1位置元素  23list.set(1,100);//更新1位置的元素System.out.println(list.get(1));// 100list.remove(1);//删除1位置元素list.clear();//清空链表System.out.println(list);//【】}

ArrayList与LinkedList的区别

        简而言之就是LinkedList的插入和删除的复杂度高,而ArrayList的可能需要移动n次数据,所以应用根据应用场景来判断使用哪一种。         

相关文章:

【Java数据结构】LinkedList与链表

认识LinkedList LinkedList就是一个链表&#xff0c;它也是实现List接口的一个类。LinkedList就是通过next引用将所有的结点链接起来&#xff0c;所以不需要数组。LinkedList也是以泛型的方法实现的&#xff0c;所以使用这个类都需要实例化对象。 链表分为很多种&#xff0c;比…...

uniapp——微信小程序,从客户端会话选择文件

微信小程序选择文件 文章目录 微信小程序选择文件效果图选择文件返回数据格式 API文档&#xff1a; chooseMessageFile 微信小程序读取文件&#xff0c;请查看 效果图 选择文件 /*** description 从客户端会话选择文件* returns {String} 文件路径*/ const chooseFile () &g…...

【CSS in Depth 2 精译_098】17.3:CSS 动画延迟技术与填充模式设置 + 17.4:通过 CSS 动画传递意图的秘诀

当前内容所在位置&#xff08;可进入专栏查看其他译好的章节内容&#xff09; 第五部分 添加动效 ✔️【第 17 章 动画】 ✔️ 17.1 关键帧17.2 3D 变换下的动画设置 17.2.1 添加动画前页面布局的构建17.2.2 为布局添加动画 17.3 动画延迟与填充模式 ✔️17.4 通过动画传递意图…...

Oracle考试多少分算通过?

OCP和OCM认证的考试及格分数并不是固定的&#xff0c;而是根据考试的难度和考生的整体表现来确定。对于OCP认证&#xff0c;考生需要全面掌握考试要求的知识和技能&#xff0c;并在考试中表现出色才有可能通过。而对于OCM认证&#xff0c;考生则需要在每个模块中都达到一定的水…...

在云服务器中编译IDF(ESP32库)

登录云服务器 使用gitee从github上导入仓库 地址GitHub - espressif/esp-idf: Espressif IoT Development Framework. Official development framework for Espressif SoCs. 然后在云服务器中创建目录~/esp 进入路径后使用git clone 下载项目 进入编程指南ESP-IDF 编程指南…...

Oracle 日常巡检

1. 检查服务器状态 1.1. CPU使用情况 1.1.1. top top 命令是 Linux 和 Unix 系统中用于显示实时系统状态的工具&#xff0c;特别是对于监控 CPU 和内存的使用非常有用。 在命令行中输入 top&#xff0c;top 会显示一个实时更新的界面&#xff0c;其中包含系统的关键指标&am…...

机器学习常用术语

目录 概要 机器学习常用术语 1、模型 2、数据集 3、样本与特征 4、向量 5、矩阵 6、假设函数与损失函数 7、拟合、过拟合与欠拟合 8、激活函数(Activation Function) 9、反向传播(Backpropagation) 10、基线(Baseline) 11、批量(Batch) 12、批量大小(Batch Size)…...

springboot507基于Springboot教学管理系统(论文+源码)_kaic

摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装教学管理系统软件来发挥其高效地信息处理的作用&#xff0c…...

工具变量笔记

补充知识 简单介绍工具变量 假设 Y i α β D i ϵ i Y_i\alpha\beta D_i\epsilon_i Yi​αβDi​ϵi​, where E ( ϵ i ∣ D i ) 0 E(\epsilon_i\mid D_i)0 E(ϵi​∣Di​)0. 但是通常这个条件不满足。于是假如有这样一个工具变量 Z i Z_i Zi​存在的话&#xff0c;满…...

ElasticSearch 统计分析全攻略

在大数据时代&#xff0c;数据的价值不仅在于存储&#xff0c;更在于能够从中挖掘出有意义的信息。ElasticSearch 作为一款强大的分布式搜索引擎&#xff0c;除了具备出色的搜索功能外&#xff0c;其内置的统计分析能力也不容小觑&#xff0c;能够助力我们快速洞察数据背后的规…...

DataCap MongoDB Driver: 全面解析MongoDB在DataCap中的使用指南

在大数据时代&#xff0c;MongoDB作为一款广受欢迎的NoSQL数据库&#xff0c;其灵活的文档存储模型和强大的查询能力使其成为许多现代应用的首选数据存储方案。今天&#xff0c;我们将深入探讨DataCap MongoDB Driver&#xff0c;这是一个强大的工具&#xff0c;它让在DataCap环…...

DDSort-简单实用的jQuery拖拽排序插件

DDSort.js是一款简单实用的jQuery拖拽排序插件。通过该插件你可以任意拖动页面中元素&#xff0c;并放置到指定的地方。DDSort.js插件实用简单&#xff0c;兼容IE8浏览器。 在线预览 下载 使用方法 实用该拖拽排序插件需要在页面中引入jquery文件和ddsort.js文件。 <scri…...

「下载」智慧园区及重点区域安全防范解决方案:框架统一规划,建设集成管理平台

智慧园区在基础设施建设和管理上仍存在诸多挑战。园区内场景碎片化、系统独立化、数据无交互、应用无联动等问题普遍存在&#xff0c;导致管理效率低下&#xff0c;安全隐患频发。 各安保系统如视频监控系统、报警管理系统、门禁管理系统等独立运行&#xff0c;数据不共享&…...

华为 IPD,究竟有什么特点?(一)

关注作者 &#xff08;一&#xff09;华为版 IPD 特点一&#xff1a;一定要让研发转身为作战 部队 冲到前台的研发&#xff0c;应主动拉通公司上下游&#xff0c;向前抓需求&#xff0c;向后支撑可制造性、可 服务性&#xff0c;并推动制造、服务的改进。 1&#xff09;研发从…...

Llama 3 后训练(三)

目录 4. 后训练 4.1 建模 图表解读 4.1.1 聊天对话格式 4.1.2 奖励建模 4.1.3 监督微调&#xff08;Supervised Finetuning&#xff09; 4.1.4 直接偏好优化&#xff08;Direct Preference Optimization&#xff09; 4.1.5 模型平均&#xff08;Model Averaging&#x…...

Docker 安装全攻略:从入门到上手

Docker 安装全攻略&#xff1a;从入门到上手 在当今的软件开发与部署领域&#xff0c;Docker 已经成为了一项不可或缺的关键技术。它能够将应用程序及其依赖项打包成轻量级、可移植的容器&#xff0c;极大地简化了开发、测试和部署的流程。本文将详细讲解在不同操作系统下 Doc…...

螺杆支撑座在运用中会出现哪些问题?

螺杆支撑座是一种用于支撑滚珠螺杆的零件&#xff0c;通常用于机床、数控机床、自动化生产线等高精度机械设备中。在运用中可能会出现多种问题&#xff0c;这些问题源于多个方面&#xff0c;以下是对可能出现的问题简单了解下&#xff1a; 1、安装不当&#xff1a;安装过程中没…...

Java与SQL Server数据库连接的实践与要点

本文还有配套的精品资源&#xff0c;点击获取 简介&#xff1a;Java和SQL Server数据库交互是企业级应用开发中的重要环节。本文详细探讨了使用Java通过JDBC连接到SQL Server数据库的过程&#xff0c;包括加载驱动、建立连接、执行SQL语句、处理异常、资源管理、事务处理和连…...

客户案例:基于慧集通的致远OA与海康威视智能会议设备集成方案

一、引言 本案例原型公司是我国生产纺织原料的大型上市企业&#xff0c;主导产品为再生纤维素长丝、氨纶等系列产品。公司产品不仅得到国内客户认可&#xff0c;还远销海外&#xff0c;合作伙伴遍布德国、意大利、日本、韩国、土耳其、印度等30多个国家和地区。 二、简介 &am…...

嵌入式驱动开发详解7(并发、竞争、中断)

文章目录 前言并发和竞争原子操作自旋锁信号量互斥体 中断中断简介中断API上半部和下半部设备树分析中断号获取源码 后续参考文献 前言 中断会引起线程的切换&#xff0c;并发和竞争也是对线程切换的一种灵活保护和处理&#xff0c;因此这里将中断和并发与竞争放在一块讲解说明…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...