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

一文讲解Java中的ArrayList和LinkedList

ArrayList和LinkedList有什么区别?

  • ArrayList 是基于数组实现的,LinkedList 是基于链表实现的。
    在这里插入图片描述
    二者用途有什么不同?

  • 多数情况下,ArrayList更利于查找,LinkedList更利于增删

    1. 由于 ArrayList 是基于数组实现的,所以 get(int index) 可以直接通过数组下标获取,时间复杂度是 O(1);LinkedList 是基于链表实现的,get(int index) 需要遍历链表,时间复杂度是 O(n)。
      当然,get(E element) 这种查找,两种集合都需要遍历通过 equals 比较获取元素,所以时间复杂度都是 O(n)。

    2. 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)。
      1. 双向链表在头部和尾部进行插入和删除操作的时间复杂度都是 ,所以 LinkedList 能够高效地实现队列。
      1. 同样基于双向链表的特性,LinkedList 可以方便地实现栈的操作。对于入栈操作,可以使用 addFirst(E e) 方法将元素添加到链表的头部;对于出栈操作,可以使用 removeFirst() 方法将链表头部的元素移除。在链表头部进行插入和删除操作的时间复杂度为 ,因此 LinkedList 能高效地实现栈。

链表和数组又有什么区别?

  • 数组在内存中占用的是一块连续的存储空间,因此我们可以通过数组下标快速访问任意元素。数组在创建时必须指定大小,一旦分配内存,数组的大小就固定了。
  • 链表的元素(节点)存储在内存中的任意位置,每个节点通过指针(引用)指向下一个节点。链表不需要指定大小,可以在运行时动态变化。
    在这里插入图片描述
http://www.lryc.cn/news/530879.html

相关文章:

  • CNN的各种知识点(五):平均精度均值(mean Average Precision, mAP)
  • 【优先算法】专题——前缀和
  • gitea - fatal: Authentication failed
  • 基于Spring Security 6的OAuth2 系列之八 - 授权服务器--Spring Authrization Server的基本原理
  • 蓝桥与力扣刷题(234 回文链表)
  • Google C++ Style / 谷歌C++开源风格
  • Windows图形界面(GUI)-QT-C/C++ - QT Tab Widget
  • 【大数据技术】教程05:本机DataGrip远程连接虚拟机MySQL/Hive
  • C++:结构体和类
  • MATLAB的数据类型和各类数据类型转化示例
  • UE求职Demo开发日志#19 给物品找图标,实现装备增加属性,背包栏UI显示装备
  • C++泛型编程指南09 类模板实现和使用友元
  • 使用MATLAB进行雷达数据采集可视化
  • 【Elasticsearch】allow_no_indices
  • 54【ip+端口+根目录通信】
  • python算法和数据结构刷题[3]:哈希表、滑动窗口、双指针、回溯算法、贪心算法
  • DeepSeek横空出世,AI格局或将改写?
  • 聚簇索引、哈希索引、覆盖索引、索引分类、最左前缀原则、判断索引使用情况、索引失效条件、优化查询性能
  • OpenAI 实战进阶教程 - 第四节: 结合 Web 服务:构建 Flask API 网关
  • python的pre-commit库的使用
  • 架构技能(四):需求分析
  • Linux环境下的Java项目部署技巧:安装 Nginx
  • 前端 Vue 性能提升策略
  • 深入理解linux中的文件(上)
  • Unity特效插件GodFX
  • 从 C 到 C++:理解结构体中字符串的存储与操作
  • Linux进阶——时间服务器
  • 力扣 295. 数据流的中位数
  • 【Linux】进程状态和优先级
  • 携程Java开发面试题及参考答案 (200道-上)