首页 > 编程语言 >【java】ArrayList与LinkedList的区别

【java】ArrayList与LinkedList的区别

时间:2024-11-09 19:45:52浏览次数:5  
标签:存储 遍历 java LinkedList ArrayList 元素 操作

目录

1. 说明
  • 1.Java中的ArrayList和LinkedList是两种常用的集合实现类,都属于Java集合框架的一部分,但它们在内部实现、性能特点、使用场景等方面存在明显的区别。
2. 内部实现
2.1 ArrayList
  • 1.是动态数组的实现,底层使用数组来存储元素。
  • 2.元素在物理内存中是连续存储的。
2.2 LinkedList
  • 1.是链表(特别是双向链表)的实现。
  • 2.每个元素都包含数据本身以及指向前一个元素和后一个元素的指针(或引用)。
  • 3.元素在物理内存中不一定是连续存储的。
3. 性能特点
3.1 插入和删除操作
  • 1.ArrayList:在ArrayList中进行插入和删除操作时,需要移动插入或删除点之后的所有元素来保持元素的连续性,因此这些操作的时间复杂度为O(n)。特别地,在列表的末尾添加元素时,ArrayList的性能相对较好,因为不需要移动元素。
  • 2.LinkedList:在LinkedList中插入和删除元素时,只需要修改相关节点的指针即可。因此,这些操作的时间复杂度为O(1)(在列表的头部或尾部操作时)或O(n)(在列表的中间位置操作时,因为需要遍历到该位置)。然而,由于LinkedList的节点是分散存储的,所以这些操作在实际执行时可能比ArrayList更快,因为它们避免了大量数据的移动。
3.2 访问操作
  • 1.ArrayList:由于ArrayList中的元素是连续存储的,因此可以通过索引在O(1)时间内访问到任何位置的元素。
  • 2.LinkedList:LinkedList不支持通过索引快速访问元素,因为元素在物理内存中不是连续存储的。访问LinkedList中的元素需要从头或尾开始遍历链表,直到找到目标元素,因此访问操作的时间复杂度为O(n)。
3.1 遍历操作
  • 1.使用迭代器遍历ArrayList时,由于元素是连续存储的,所以遍历效率较高。
  • 2.使用迭代器遍历LinkedList时,由于元素是分散存储的,迭代器需要不断通过指针跳转来访问下一个元素,因此遍历效率相对较低。然而,在特定情况下(如只需要遍历列表的一部分元素时),LinkedList的遍历性能可能优于ArrayList。
4. 使用场景
  • 1.ArrayList:适用于需要频繁进行随机访问和遍历操作的场景。特别是在列表大小相对稳定、不经常进行插入和删除操作的情况下。
  • 2.LinkedList:适用于需要频繁进行插入和删除操作的场景。特别是在列表的头部或尾部进行操作时。此外,LinkedList还可以用作栈(LIFO)或队列(FIFO)等数据结构的实现。
5. 扩容机制
  • 1.ArrayList在初始化时需要指定初始容量(默认为10),并且会在元素数量超过当前容量时自动扩容(通常是将容量增加为原来的1.5倍),这会导致一定的内存浪费和复制开销。
  • 2.LinkedList不需要在添加元素时进行扩容操作,因此可以避免ArrayList在扩容时可能产生的内存浪费和复制开销。
6. 空间开销
  • 1.ArrayList中的元素是连续存储的,因此空间开销相对较小(除了元素本身外,还需要一些额外的空间来存储数组的长度和容量等信息)。
  • 2.LinkedList的每个节点都需要额外的空间来存储指向前一个节点和后一个节点的指针(或引用),因此其空间开销相对较大。

标签:存储,遍历,java,LinkedList,ArrayList,元素,操作
From: https://blog.csdn.net/qq_32088869/article/details/143478427

相关文章

  • Java入门程序之一维数组的基础运用
    Java入门程序之一维数组的基础运用​本文详细介绍了Java中数组的概念、创建与初始化、一维数组的使用、内存分布以及二维数组。讲解了数组的静态与动态初始化、元素访问与修改、遍历方式。一、数组的基本概念数组的初始化例如:int[]array1=newint[20];//创建一个......
  • Java 单例模式
    Java单例模式示例 packagecom.joyupx.cms.example.single;/***多线程环境中保证单例的写法。*@authorhapday*/publicclassSingleInstanceExample{privatestaticSingleInstanceExamplesingleInstanceExample;privateSingleInstanceExample()......
  • (JAVA)基于TCP通信多人聊天系统
    一、目标 这个项目是一个基于TCP协议的简单多人聊天系统,包含一个服务器和多个客户端。服务器接受多个客户端的连接,每个客户端发送的消息都可以转发给其他所有在线的客户端,实现了一个基本的多人实时聊天功能。项目使用Java编程语言编写,利用ServerSocket和Socket 创建......
  • 104.力扣(leetcode)二叉树的最大深度(JAVA)
    一、目标给定一个二叉树 root ,返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。二、代码分析总代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeN......
  • 力扣(Leetcode)112. 路径总和(JAVA)
    一、目标 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。叶子节点 是指没有子节点的节点。二、代码解读......
  • 257. 力扣(LeetCode)二叉树的所有路径(JAVA)
    一、目标给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。二、代码解读总代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*......
  • Java毕业设计-基于SSM的新生报到系统【代码+论文+PPT+开题】
    全文内容包括:1、采用技术;2、系统功能;3、系统截图;4、部分代码;5、配套内容。索取方式见文末微信号,欢迎关注收藏!一、采用技术语言:Java1.8框架:SSM数据库:MySQL5.7、8.0开发工具:IntelliJIDEA旗舰版其他:Maven3.8以上二、系统功能个人中心:提供学生个人信息查看与编辑,以及报到进度......
  • java毕业设计-基于SSM的购物商城系统【代码+论文+PPT+开题+任务书】
    全文内容包括:1、采用技术;2、系统功能;3、系统截图;4、部分代码;5、配套内容。索取方式见文末微信号,欢迎关注收藏!一、采用技术语言:Java1.8框架:SSM数据库:MySQL5.7、8.0开发工具:IntelliJIDEA旗舰版其他:Maven3.8以上二、系统功能个人中心:管理用户个人信息,包括资料编辑、密码修改......
  • java毕业设计-基于ssm的汽车配件销售业绩管理系统【代码+论文+PPT+任务书+开题报告】
    全文内容包括:1、采用技术;2、系统功能;3、系统截图;4、部分代码;5、配套内容。索取方式见文末微信号,欢迎关注收藏!一、采用技术语言:Java1.8框架:SSM数据库:MySQL5.7、8.0开发工具:IntelliJIDEA旗舰版其他:Maven3.8以上二、系统功能个人中心:管理用户个人信息,包括账户设置、资料编辑......
  • JAVA自动化扫描并使用Driver进行小型DDOS-----JAVA
    packagecom.alatus.searchinfo.config;importcom.alatus.searchinfo.Entity.AccountEntity;importcom.alatus.searchinfo.utils.HttpUtils;importcom.alibaba.excel.context.AnalysisContext;importcom.alibaba.excel.metadata.CellExtra;importcom.alibaba.excel......