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

Java_LinkedList链表详解

目录

前言

ArrayList的缺陷

链表 

链表的概念及结构

链表的种类

1.单向或双向

2.带头或不带头

3.循环或不循环

LinkedList的使用 

什么是LinkedList

LinkedList的使用

LinkedList的构造

LinkedList的其他常用方法介绍

LinkedList的遍历

ArrayList和LinkedList的区别

链表的缺陷 


 

前言

图文详解java链表,顺序表和链表的比较,多种链表的形式,链表的使用,链表的方法

ArrayList的缺陷

ArrayList顺序表

由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后 搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java 集合中又引入了LinkedList,即链表结构。

链表 

链表的概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

由上图可见链表不同于数组,删除和添加元素只需要把next的值改变即可

这样时间复杂度只为O(1)

例如: 

 

注意:

        1.从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续

        2.现实中的结点一般都是从堆上申请出来的

        3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

链表的种类

1.单向或双向

 

2.带头或不带头

3.循环或不循环

 

虽然有这么多的链表的结构,但是我们重点掌握两种:

无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如 哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

LinkedList的使用 

什么是LinkedList

LinkedList的底层是双向链表结构(链表后面介绍),由于链表没有将元素存储在连续的空间中,元素存储在单独的节 点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。

LinkedList的使用

LinkedList的构造

 

public static void main(String[] args) {// 构造一个空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>();list2.add("JavaSE");list2.add("JavaWeb");list2.add("JavaEE");// 使用ArrayList构造LinkedListList<String> list3 = new LinkedList<>(list2);
}

LinkedList的其他常用方法介绍

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素,内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在,如果存在返回true,否则返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem = list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list.subList(0, 3); System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());
}

LinkedList的遍历

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());// foreach遍历for (int e:list) {System.out.print(e + " ");}System.out.println();// 使用迭代器遍历---正向遍历ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();// 使用反向迭代器---反向遍历ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();
}

ArrayList和LinkedList的区别

链表的缺陷 

我们知道链表的删除和添加效率比顺序表高得多,但是没有取代顺序表,这是因为链表也有缺陷

如上图,链表对于访问来说非常的乏力,顺序表底层是数组,可以直接用下标来访问,时间复杂度为O(1),而链表则需要从头开始访问,一个个计数然后访问到需要的元素,时间复杂度为O(n) 

所以顺序表和链表都有其存在的意义,我们要视情况而选择合适的来使用 

相关文章:

Java_LinkedList链表详解

目录 前言 ArrayList的缺陷 链表 链表的概念及结构 链表的种类 1.单向或双向 2.带头或不带头 3.循环或不循环 LinkedList的使用 什么是LinkedList LinkedList的使用 LinkedList的构造 LinkedList的其他常用方法介绍 LinkedList的遍历 ArrayList和LinkedList的…...

MacOS 12 开放指定端口 指定ip访问

MacOS 12 开放指定端口 指定ip访问 在 macOS 上开放一个端口&#xff0c;并指定只能特定的 IP 访问&#xff0c;你可以使用 macOS 内置的 pfctl&#xff08;Packet Filter&#xff09;工具来实现。 以下是一些基本的步骤&#xff1a; 1、 编辑 pf 配置文件&#xff1a; 打开 /…...

LeedCode刷题---滑动窗口问题

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、长度最小的子数组 题目链接&#xff1a;长度最小的子数组 题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。…...

leetcode24. 两两交换链表中的节点

题目描述 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09;。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4] 输出&#…...

TCP传输层详解(计算机网络复习)

介绍&#xff1a;TCP/IP包含了一系列的协议&#xff0c;也叫TCP/IP协议族&#xff0c;简称TCP/IP。该协议族提供了点对点的连接机制&#xff0c;并将传输数据帧的封装、寻址、传输、路由以及接收方式都予以标准化 TCP/IP的分层模型 在讲TCP/IP协议之前&#xff0c;首先介绍一…...

【LuatOS】简单案例网页点灯

材料 硬件&#xff1a;合宙ESP32C3简约版&#xff0c;BH1750光照度模块&#xff0c;0.96寸OLED(4P_IIC)&#xff0c;杜邦线若干 接线&#xff1a; ESP32C3.GND — OLED.GND — BH1750.GND ESP32C3.3.3V — OLED.VCC — BH1750.VCC ESP32C3.GPIO5 — OLED.SCL — BH1750.SCL E…...

百度APP iOS端包体积50M优化实践(七)编译器优化

一. 前言 百度APP iOS端包体积优化系列文章的前六篇重点介绍了包体积优化整体方案、图片优化、资源优化、代码优化、无用类优化、HEIC图片优化实践和无用方法清理&#xff0c;图片优化是从无用图片、Asset Catalog和HEIC格式三个角度做深度优化&#xff1b;资源优化包括大资源…...

STM32-新建工程(标准库)

目录 STM32F10x新建工程&#xff08;标准库&#xff09; 移植文件夹 新建工程 添加启动文件和必需文件 在工程中加载新添加的文件 在工程中添加文件路径 在工程中添加main函数 添加lib库 添加必需文件 添加宏定义 点亮LED&#xff08;标准库&#xff09; STM32F10x新…...

Android集成科大讯飞语音识别与语音唤醒简易封装

目录 一、语音唤醒部分 1、首先在科大讯飞官网注册开发者账号 2、配置唤醒词然后下载sdk 3、选择对应功能下载 4、语音唤醒lib包全部复制到工程目录下 5、把语音唤醒词文件复制到工程的assets目录 6、复制对应权限到AndroidManifest.xml中 7、唤醒工具类封装 二、语音识…...

【Linux】telnet命令使用

telnet命令 telnet命令用于使用telnet协议与另一台主机进行通信。如果在没有主机参数的情况下调用telnet&#xff0c;它将进入命令模式&#xff0c;由其提示&#xff08;telnet>&#xff09;指示。在这种模式下&#xff0c;它接受并执行下面列出的命令。如果使用参数调用它…...

VCG 标记使用(BitFlags)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 对于网格的每个单形,我们都有一个称为BitFlags的组件,该组件存储固定大小的32位向量,用于各种需求。管理这些标志的相关类:vcg::tri::UpdateFlags与vcg::tri::UpdateSelection。主要的标记有:删除标记、边界标记…...

Pandas中的Series(第1讲)

Pandas中的Series(第1讲)         🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔…...

从手工测试进阶中高级测试?如何突破职业瓶颈...

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

【链表Linked List】力扣-114 二叉树展开为链表

目录 题目描述 解题过程 官方题解 题目描述 给你二叉树的根结点 root &#xff0c;请你将它展开为一个单链表&#xff1a; 展开后的单链表应该同样使用 TreeNode &#xff0c;其中 right 子指针指向链表中下一个结点&#xff0c;而左子指针始终为 null 。展开后的单链表应…...

Go (一) 基础部分4 -- 文件处理

一、文件基本介绍 1.1、打开一个文件 基本介绍&#xff1a;打开一个文件用于读取&#xff0c;如果操作成功&#xff0c;返回的文件对象的方法可用于读取文件数据。如果出错&#xff0c;错误底层类型是"*.PathError" func Open(name string) (*File, error) name stri…...

集合03 Collection (List) - Java

List ArrayListArrayList注意事项ArrayList底层操作机制-源码分析&#xff08;重点&#xff09; VectorVector基本介绍 ——Vector和ArrayList比较Vector底层结构和源码分析 LinkedList基本介绍LinkedList的底层结构和操作机制LinkedList的增删改查 ——LinkedList和ArrayList比…...

国产化软件突围!怿星科技eStation产品荣获2023铃轩奖“前瞻优秀奖”

11月11日&#xff0c;2023中国汽车供应链峰会暨第八届铃轩奖颁奖典礼在江苏省昆山市举行。怿星科技凭借eStation产品&#xff0c;荣获2023铃轩奖“前瞻智能座舱类优秀奖”&#xff0c;怿星CEO潘凯受邀出席铃轩奖晚会并代表领奖。 2023铃轩奖“前瞻智能座舱类优秀奖” 铃轩奖&a…...

如何解决Redis热Key问题?

Redis热点key是指访问频率较高的key&#xff0c;当大量的请求集中在一个或少数几个热点key上时&#xff0c;会导致这些key所在的Redis节点的CPU、内存和网络带宽等资源被大量消耗&#xff0c;影响Redis集群的整体性能和稳定性。 热点Key带来的问题 Redis节点负载过高&#xff1…...

react Hooks之useId

当我们在编写React组件时&#xff0c;有时需要为元素生成唯一的ID。这种情况经常出现在表单元素、标签和用于无障碍性的目的上。React提供了一个名为useId的自定义Hook&#xff0c;它可以帮助我们生成唯一的ID。 1、作用&#xff1a; 用于生成一个唯一的 ID。这个 ID 可以用于…...

2023年全球软件开发大会(QCon广州站2023)-核心PPT资料下载

一、峰会简介 本次峰会包含&#xff1a;泛娱乐时代的边缘计算与通讯、稳定性即生命线、下一代软件架构、出海的思考、现代数据架构、AGI 与 AIGC 落地、大前端技术探索、编程语言实战、DevOps vs 平台工程、新型数据库、AIGC 浪潮下的企业出海、AIGC 浪潮下的效能智能化、数据…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...