当前位置: 首页 > 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;因此这里将中断和并发与竞争放在一块讲解说明…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...