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 上开放一个端口,并指定只能特定的 IP 访问,你可以使用 macOS 内置的 pfctl(Packet Filter)工具来实现。 以下是一些基本的步骤: 1、 编辑 pf 配置文件: 打开 /…...
LeedCode刷题---滑动窗口问题
顾得泉:个人主页 个人专栏:《Linux操作系统》 《C/C》 《LeedCode刷题》 键盘敲烂,年薪百万! 一、长度最小的子数组 题目链接:长度最小的子数组 题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。…...
leetcode24. 两两交换链表中的节点
题目描述 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 示例 1: 输入:head [1,2,3,4] 输出&#…...
TCP传输层详解(计算机网络复习)
介绍:TCP/IP包含了一系列的协议,也叫TCP/IP协议族,简称TCP/IP。该协议族提供了点对点的连接机制,并将传输数据帧的封装、寻址、传输、路由以及接收方式都予以标准化 TCP/IP的分层模型 在讲TCP/IP协议之前,首先介绍一…...
【LuatOS】简单案例网页点灯
材料 硬件:合宙ESP32C3简约版,BH1750光照度模块,0.96寸OLED(4P_IIC),杜邦线若干 接线: 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图片优化实践和无用方法清理,图片优化是从无用图片、Asset Catalog和HEIC格式三个角度做深度优化;资源优化包括大资源…...
STM32-新建工程(标准库)
目录 STM32F10x新建工程(标准库) 移植文件夹 新建工程 添加启动文件和必需文件 在工程中加载新添加的文件 在工程中添加文件路径 在工程中添加main函数 添加lib库 添加必需文件 添加宏定义 点亮LED(标准库) STM32F10x新…...
Android集成科大讯飞语音识别与语音唤醒简易封装
目录 一、语音唤醒部分 1、首先在科大讯飞官网注册开发者账号 2、配置唤醒词然后下载sdk 3、选择对应功能下载 4、语音唤醒lib包全部复制到工程目录下 5、把语音唤醒词文件复制到工程的assets目录 6、复制对应权限到AndroidManifest.xml中 7、唤醒工具类封装 二、语音识…...
【Linux】telnet命令使用
telnet命令 telnet命令用于使用telnet协议与另一台主机进行通信。如果在没有主机参数的情况下调用telnet,它将进入命令模式,由其提示(telnet>)指示。在这种模式下,它接受并执行下面列出的命令。如果使用参数调用它…...
VCG 标记使用(BitFlags)
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 对于网格的每个单形,我们都有一个称为BitFlags的组件,该组件存储固定大小的32位向量,用于各种需求。管理这些标志的相关类:vcg::tri::UpdateFlags与vcg::tri::UpdateSelection。主要的标记有:删除标记、边界标记…...
Pandas中的Series(第1讲)
Pandas中的Series(第1讲) 🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔…...
从手工测试进阶中高级测试?如何突破职业瓶颈...
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 1、手工测试如何进…...
【链表Linked List】力扣-114 二叉树展开为链表
目录 题目描述 解题过程 官方题解 题目描述 给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。展开后的单链表应…...
Go (一) 基础部分4 -- 文件处理
一、文件基本介绍 1.1、打开一个文件 基本介绍:打开一个文件用于读取,如果操作成功,返回的文件对象的方法可用于读取文件数据。如果出错,错误底层类型是"*.PathError" func Open(name string) (*File, error) name stri…...
集合03 Collection (List) - Java
List ArrayListArrayList注意事项ArrayList底层操作机制-源码分析(重点) VectorVector基本介绍 ——Vector和ArrayList比较Vector底层结构和源码分析 LinkedList基本介绍LinkedList的底层结构和操作机制LinkedList的增删改查 ——LinkedList和ArrayList比…...
国产化软件突围!怿星科技eStation产品荣获2023铃轩奖“前瞻优秀奖”
11月11日,2023中国汽车供应链峰会暨第八届铃轩奖颁奖典礼在江苏省昆山市举行。怿星科技凭借eStation产品,荣获2023铃轩奖“前瞻智能座舱类优秀奖”,怿星CEO潘凯受邀出席铃轩奖晚会并代表领奖。 2023铃轩奖“前瞻智能座舱类优秀奖” 铃轩奖&a…...
如何解决Redis热Key问题?
Redis热点key是指访问频率较高的key,当大量的请求集中在一个或少数几个热点key上时,会导致这些key所在的Redis节点的CPU、内存和网络带宽等资源被大量消耗,影响Redis集群的整体性能和稳定性。 热点Key带来的问题 Redis节点负载过高࿱…...
react Hooks之useId
当我们在编写React组件时,有时需要为元素生成唯一的ID。这种情况经常出现在表单元素、标签和用于无障碍性的目的上。React提供了一个名为useId的自定义Hook,它可以帮助我们生成唯一的ID。 1、作用: 用于生成一个唯一的 ID。这个 ID 可以用于…...
2023年全球软件开发大会(QCon广州站2023)-核心PPT资料下载
一、峰会简介 本次峰会包含:泛娱乐时代的边缘计算与通讯、稳定性即生命线、下一代软件架构、出海的思考、现代数据架构、AGI 与 AIGC 落地、大前端技术探索、编程语言实战、DevOps vs 平台工程、新型数据库、AIGC 浪潮下的企业出海、AIGC 浪潮下的效能智能化、数据…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
