一文讲解Java中的ArrayList和LinkedList
ArrayList和LinkedList有什么区别?
-
ArrayList 是基于数组实现的,LinkedList 是基于链表实现的。
二者用途有什么不同? -
多数情况下,ArrayList更利于查找,LinkedList更利于增删
-
由于 ArrayList 是基于数组实现的,所以
get(int index)
可以直接通过数组下标获取,时间复杂度是 O(1);LinkedList 是基于链表实现的,get(int index)
需要遍历链表,时间复杂度是 O(n)。
当然,get(E element)
这种查找,两种集合都需要遍历通过 equals 比较获取元素,所以时间复杂度都是 O(n)。 -
ArrayList 如果增删的是数组的尾部,直接插入或者删除就可以了,时间复杂度是 O(1);如果 add 的时候涉及到扩容,时间复杂度会提升到 O(n)。
但如果插入的是中间的位置,就需要把插入位置后的元素向前或者向后移动,甚至还有可能触发扩容,效率就会低很多,O(n)。
LinkedList 因为是链表结构,插入和删除只需要改变前置节点、后置节点和插入节点的引用就行了,不需要移动元素。
如果是在链表的头部插入或者删除,时间复杂度是 O(1);如果是在链表的中间插入或者删除,时间复杂度是 O(n),因为需要遍历链表找到插入位置;如果是在链表的尾部插入或者删除,时间复杂度是 O(1)。
-
- 注意,这里有个陷阱,LinkedList 更利于增删不是体现在时间复杂度上,因为二者增删的时间复杂度都是 O(n),都需要遍历列表;而是体现在增删的效率上,因为 LinkedList 的增删只需要改变引用,而 ArrayList 的增删可能需要移动元素。
二者是否支持随机访问呢?
- ①、ArrayList 是基于数组的,也实现了 RandomAccess 接口,所以它支持随机访问,可以通过下标直接获取元素。
- ②、LinkedList 是基于链表的,所以它没法根据下标直接获取元素,不支持随机访问,所以它也没有实现 RandomAccess 接口。
二者的内存占用有何不同?
- ArrayList 是基于数组的,是一块连续的内存空间,所以它的内存占用是比较紧凑的;但如果涉及到扩容,就会重新分配内存,空间是原来的 1.5 倍,存在一定的空间浪费。
- LinkedList 是基于链表的,每个节点都有一个指向下一个节点和上一个节点的引用,于是每个节点占用的内存空间稍微大一点。
二者的使用场景有什么不同呢?
ArrayList 适用于:
- 随机访问频繁:需要频繁通过索引访问元素的场景。
- 读取操作远多于写入操作:如存储不经常改变的列表。
- 末尾添加元素:需要频繁在列表末尾添加元素的场景。
LinkedList 适用于:
- 频繁插入和删除:在列表中间频繁插入和删除元素的场景。
- 不需要快速随机访问:顺序访问多于随机访问的场景。
- 在日志记录处理的场景中,通常是按照日志产生的先后顺序依次读取和处理日志信息,不需要随机访问某一条特定的日志。例如,从日志文件中逐行读取日志内容,对每一条日志进行解析和分析。此时使用
LinkedList
存储日志信息,通过迭代器进行顺序访问,可以高效地完成日志处理任务。
- 在日志记录处理的场景中,通常是按照日志产生的先后顺序依次读取和处理日志信息,不需要随机访问某一条特定的日志。例如,从日志文件中逐行读取日志内容,对每一条日志进行解析和分析。此时使用
import java.util.Iterator;
import java.util.LinkedList;public class LogProcessingExample {public static void main(String[] args) {LinkedList<String> logList = new LinkedList<>();logList.add("Log entry 1");logList.add("Log entry 2");logList.add("Log entry 3");// 顺序访问日志Iterator<String> iterator = logList.iterator();while (iterator.hasNext()) {String log = iterator.next();System.out.println("Processing log: " + log);}}
}
- 队列和栈:由于其双向链表的特性,LinkedList 可以高效地实现队列(FIFO)和栈(LIFO)。
-
- 双向链表在头部和尾部进行插入和删除操作的时间复杂度都是 ,所以
LinkedList
能够高效地实现队列。
- 双向链表在头部和尾部进行插入和删除操作的时间复杂度都是 ,所以
-
- 同样基于双向链表的特性,
LinkedList
可以方便地实现栈的操作。对于入栈操作,可以使用addFirst(E e)
方法将元素添加到链表的头部;对于出栈操作,可以使用removeFirst()
方法将链表头部的元素移除。在链表头部进行插入和删除操作的时间复杂度为 ,因此LinkedList
能高效地实现栈。
- 同样基于双向链表的特性,
-
链表和数组又有什么区别?
- 数组在内存中占用的是一块连续的存储空间,因此我们可以通过数组下标快速访问任意元素。数组在创建时必须指定大小,一旦分配内存,数组的大小就固定了。
- 链表的元素(节点)存储在内存中的任意位置,每个节点通过指针(引用)指向下一个节点。链表不需要指定大小,可以在运行时动态变化。
相关文章:

一文讲解Java中的ArrayList和LinkedList
ArrayList和LinkedList有什么区别? ArrayList 是基于数组实现的,LinkedList 是基于链表实现的。 二者用途有什么不同? 多数情况下,ArrayList更利于查找,LinkedList更利于增删 由于 ArrayList 是基于数组实现的&#…...
CNN的各种知识点(五):平均精度均值(mean Average Precision, mAP)
平均精度均值(mean Average Precision, mAP) 1. 平均精度均值(mean Average Precision, mAP)概念:计算步骤:具体例子:重要说明:典型值范围: 总结: 1. 平均精度…...

【优先算法】专题——前缀和
目录 一、【模版】前缀和 参考代码: 二、【模版】 二维前缀和 参考代码: 三、寻找数组的中心下标 参考代码: 四、除自身以外数组的乘积 参考代码: 五、和为K的子数组 参考代码: 六、和可被K整除的子数组 参…...

gitea - fatal: Authentication failed
文章目录 gitea - fatal: Authentication failed概述run_gitea_on_my_pkm.bat 笔记删除windows凭证管理器中对应的url认证凭证启动gitea服务端的命令行正常用 TortoiseGit 提交代码备注END gitea - fatal: Authentication failed 概述 本地的git归档服务端使用gitea. 原来的用…...

基于Spring Security 6的OAuth2 系列之八 - 授权服务器--Spring Authrization Server的基本原理
之所以想写这一系列,是因为之前工作过程中使用Spring Security OAuth2搭建了网关和授权服务器,但当时基于spring-boot 2.3.x,其默认的Spring Security是5.3.x。之后新项目升级到了spring-boot 3.3.0,结果一看Spring Security也升级…...

蓝桥与力扣刷题(234 回文链表)
题目:给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 示例 1: 输入:head [1,2,2,1] 输出:true示例 2: 输入&…...

Google C++ Style / 谷歌C++开源风格
文章目录 前言1. 头文件1.1 自给自足的头文件1.2 #define 防护符1.3 导入你的依赖1.4 前向声明1.5 内联函数1.6 #include 的路径及顺序 2. 作用域2.1 命名空间2.2 内部链接2.3 非成员函数、静态成员函数和全局函数2.4 局部变量2.5 静态和全局变量2.6 thread_local 变量 3. 类3.…...
Windows图形界面(GUI)-QT-C/C++ - QT Tab Widget
公开视频 -> 链接点击跳转公开课程博客首页 -> 链接点击跳转博客主页 目录 一、概述 1.1 什么是 QTabWidget? 1.2 使用场景 二、常见样式 2.1 选项卡式界面 2.2 动态添加和删除选项卡 2.3 自定义选项卡标题和图标 三、属性设置 3.1 添加页面&…...

【大数据技术】教程05:本机DataGrip远程连接虚拟机MySQL/Hive
本机DataGrip远程连接虚拟机MySQL/Hive datagrip-2024.3.4VMware Workstation Pro 16CentOS-Stream-10-latest-x86_64-dvd1.iso写在前面 本文主要介绍如何使用本机的DataGrip连接虚拟机的MySQL数据库和Hive数据库,提高编程效率。 安装DataGrip 请按照以下步骤安装DataGrip软…...
C++:结构体和类
在之前的博客中已经讲过了C语言中的结构体概念了,重复的内容在这儿就不赘述了。C中的结构体在C语言的基础上还有些补充,在这里说明一下,顺便简单地讲一下类的概念。 一、成员函数 结构体类型声明的关键字是 struct ,在C中结构体…...

MATLAB的数据类型和各类数据类型转化示例
一、MATLAB的数据类型 在MATLAB中 ,数据类型是非常重要的概念,因为它们决定了如何存储和操作数据。MATLAB支持数值型、字符型、字符串型、逻辑型、结构体、单元数组、数组和矩阵等多种数据类型。MATLAB 是一种动态类型语言,这意味着变量的数…...

UE求职Demo开发日志#19 给物品找图标,实现装备增加属性,背包栏UI显示装备
1 将用到的图标找好,放一起 DataTable里对应好图标 测试一下能正确获取: 2 装备增强属性思路 给FMyItemInfo添加一个枚举变量记录类型(物品,道具,装备,饰品,武器)--> 扩展DataT…...
C++泛型编程指南09 类模板实现和使用友元
文章目录 第2章 类模板 Stack 的实现2.1 类模板 Stack 的实现 (Implementation of Class Template Stack)2.1.1 声明类模板 (Declaration of Class Templates)2.1.2 成员函数实现 (Implementation of Member Functions) 2.2 使用类模板 Stack脚注改进后的叙述总结脚注2.3 类模板…...

使用MATLAB进行雷达数据采集可视化
本文使用轮趣科技N10雷达,需要源码可在后台私信或者资源自取 1. 项目概述 本项目旨在通过 MATLAB 读取 N10 激光雷达 的数据,并进行 实时 3D 点云可视化。数据通过 串口 传输,并经过解析后转换为 三维坐标点,最终使用 pcplayer 进…...
【Elasticsearch】allow_no_indices
- **allow_no_indices 参数的作用**: 该参数用于控制当请求的目标索引(通过通配符、别名或 _all 指定)不存在或已关闭时,Elasticsearch 的行为。 - **默认行为**: 如果未显式设置该参数,默认值为 …...
54【ip+端口+根目录通信】
上节课讲到,根目录起到定位作用,比如我们搭建一个php网站后,注册系统是由根目录的register.php文件执行,那么我们给这个根目录绑定域名https://127.0.0.1,当我们浏览器访问https://127.0.0.1/register.php时࿰…...

python算法和数据结构刷题[3]:哈希表、滑动窗口、双指针、回溯算法、贪心算法
回溯算法 「所有可能的结果」,而不是「结果的个数」,一般情况下,我们就知道需要暴力搜索所有的可行解了,可以用「回溯法」。 回溯算法关键在于:不合适就退回上一步。在回溯算法中,递归用于深入到所有可能的分支&…...

DeepSeek横空出世,AI格局或将改写?
引言 这几天,国产AI大模型DeepSeek R1,一飞冲天,在全球AI圈持续引爆热度,DeepSeek R1 已经是世界上最先进的 AI 模型之一,可与 OpenAI 的新 o1 和 Meta 的 Llama AI 模型相媲美。 DeepSeek-V3模型发布后,在…...

聚簇索引、哈希索引、覆盖索引、索引分类、最左前缀原则、判断索引使用情况、索引失效条件、优化查询性能
聚簇索引 聚簇索引像一本按目录排版的书,用空间换时间,适合读多写少的场景。设计数据库时,主键的选择(如自增ID vs 随机UUID)会直接影响聚簇索引的性能。 什么是聚簇索引? 数据即索引:聚簇索引…...

OpenAI 实战进阶教程 - 第四节: 结合 Web 服务:构建 Flask API 网关
目标 学习将 OpenAI 接入 Web 应用,构建交互式 API 网关理解 Flask 框架的基本用法实现 GPT 模型的 API 集成并返回结果 内容与实操 一、环境准备 安装必要依赖: 打开终端或命令行,执行以下命令安装 Flask 和 OpenAI SDK: pip i…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...