Java-LinkedList和ArrayList的区别、Get/Add操作性能分析以及常见的遍历方式

2024-06-18 18:12
文章标签 java 分析 遍历 常见 操作 性能 方式 区别 arraylist get add linkedlist

本文主要是介绍Java-LinkedList和ArrayList的区别、Get/Add操作性能分析以及常见的遍历方式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LinkedList和ArrayList的区别、Get/Add操作性能分析以及常见的遍历方式

    • 一、LinkedList
      • 基本特性
      • 主要方法
    • 二、ArrayList
      • 初始化及基本操作
      • ArrayList注意点（待完善）
      • 代码示例
    • 三、ArrayList与LinkedList的区别
    • 四、Get/Add操作性能分析
    • 五、LinkedList遍历方式
    • 六、ArrayList遍历方式

一、LinkedList

LinkedList 是 Java 集合框架中的一个类，它实现了 List 接口和 Deque 接口，位于 java.util 包下。与其他 List 实现（如 ArrayList）不同，LinkedList 是基于双向链表的数据结构实现的，这为它提供了一些独特的特性和性能优势。

基本特性

  • 动态大小：由于链表的特性，LinkedList 可以在运行时高效地增加或减少元素，不需要像数组那样重新分配内存。
  • 双向链表：每个节点（或元素）都包含其前一个和后一个节点的引用，这允许在列表的两端进行高效地插入和删除操作。
  • 非随机访问：虽然可以快速地在链表的头部或尾部添加/删除元素，但访问链表中间的某个元素需要从头或尾开始遍历，因此随机访问的时间复杂度较高（O(n)）。

主要方法

添加和删除操作
1.add(E element): 在链表末尾添加元素。

   LinkedList<String> list = new LinkedList<>();list.add("Hello");

2.addFirst(E e) 和 addLast(E e): 分别在链表的开头和末尾添加元素。

   list.addFirst("First");list.addLast("Last");

3.remove(Object o): 移除链表中第一个匹配给定对象的元素。

   list.remove("Hello");

4.removeFirst() 和 removeLast(): 移除链表的第一个或最后一个元素。

   list.removeFirst();list.removeLast();

检索元素
1.get(int index): 返回指定位置的元素。

   String element = list.get(0);

2.peek(), peekFirst(), peekLast(): 查看但不移除链表的第一个或最后一个元素。

   String first = list.peekFirst();String last = list.peekLast();

转换为数组
1.toArray() 和 toArray(T[] a): 将链表转换成数组。

   String[] array = list.toArray(new String[0]);

迭代器和列表迭代器
1.Iterator: 用于遍历集合中的元素。

   Iterator<String> iterator = list.iterator();while(iterator.hasNext()) {System.out.println(iterator.next());}

2.ListIterator: 在Iterator的基础上增加了向前遍历和修改元素的能力。

   ListIterator<String> listIterator = list.listIterator();while(listIterator.hasNext()) {String current = listIterator.next();if(current.equals("First")) {listIterator.set("New First");}}

二、ArrayList

ArrayList也是Java集合框架中的一个重要成员，它实现了List接口，内部是基于动态数组实现的。下面是关于ArrayList的一些主要方法及其代码示例：

初始化及基本操作

import java.util.ArrayList;public class ArrayListExample {public static void main(String[] args) {ArrayList<String> arrayList = new ArrayList<>(); // 初始化ArrayList// 添加元素arrayList.add("Apple");arrayList.add("Banana");arrayList.add("Cherry");// 添加元素到指定位置arrayList.add(1, "Blueberry");// 获取元素String element = arrayList.get(5); // 注意：这里的索引是从0开始的// 删除指定位置的元素arrayList.remove(0);// 删除指定元素的第一个实例arrayList.remove("Banana");// 判断是否包含某元素boolean contains = arrayList.contains("Cherry");// 设置指定位置的元素arrayList.set(1, "Blackberry");// 遍历ArrayListfor (String fruit : arrayList) {System.out.println(fruit);}}
}

特殊方法

1.size(): 返回ArrayList的大小。

2.clear(): 清空ArrayList中的所有元素。

3.indexOf(Object o): 返回指定元素首次出现的位置，未找到返回-1。

4.ensureCapacity(int minCapacity): 确保ArrayList至少能容纳minCapacity个元素。

5.转换为数组

Object[] array = arrayList.toArray();

迭代器

Iterator<String> iterator = arrayList.iterator();
while(iterator.hasNext()) {System.out.println(iterator.next());
}

ArrayList注意点（待完善）

1.ArrayList两个重载的remove方法区别

​ 工作中应该会经常用到ArrayList相关的集合操作，接下来，我打算分析ArrayList两个重载的remove方法的区别

先看一看ArrayList的相关源码：

在这里插入图片描述

在这里插入图片描述

有上述源码可知：

两个重载的remove方法区别

  • 一个是根据int类型索引下标删除元素；
  • 一个是根据传入的对象值删除集合中相应值的第一个匹配项

代码示例

    private static void removeByIndex(int index) {List<Integer> list =IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toCollection(ArrayList::new));System.out.println(list.remove(index));     //按索引删除对应下标元素，返回删除的元素值System.out.println(list);}private static void removeByValue(Integer index) {List<Integer> list =IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toCollection(ArrayList::new));System.out.println(list.remove(index));     //按值删除第一个匹配值的元素，返回trueSystem.out.println(list);}

运行结果

在这里插入图片描述

三、ArrayList与LinkedList的区别

  • 数据结构：ArrayList基于动态数组，LinkedList基于双向链表。
  • 访问速度：ArrayList支持快速随机访问（O(1)），LinkedList更适合顺序访问（某些操作O(n)）。
  • 插入和删除：ArrayList在中间插入或删除较慢（需移动后续元素，O(n)），LinkedList在此类操作上更快（O(1)，特别是在列表两端）。
  • 内存占用：ArrayList通常比LinkedList更节省内存，因为LinkedList每个节点都需要额外的引用空间。

​ 根据具体应用场景选择ArrayList或LinkedList：当需要快速随机访问且元素数量相对稳定时，ArrayList更优；而当频繁进行插入和删除操作，特别是表头或表尾操作时，LinkedList更有优势，但是如果随机插入和修改，可能ArrayList更好。

四、Get/Add操作性能分析

import org.springframework.util.StopWatch;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.IntStream;public class LinkedListApplication {public static void main(String[] args) {int elementCount = 100000;int loopCount = 100000;StopWatch stopWatch = new StopWatch();stopWatch.start("linkedListGet");linkedListGet(elementCount, loopCount);stopWatch.stop();stopWatch.start("arrayListGet");arrayListGet(elementCount, loopCount);stopWatch.stop();System.out.println(stopWatch.prettyPrint());StopWatch stopWatch2 = new StopWatch();stopWatch2.start("linkedListAdd");linkedListAdd(elementCount, loopCount);stopWatch2.stop();stopWatch2.start("arrayListAdd");arrayListAdd(elementCount, loopCount);stopWatch2.stop();System.out.println(stopWatch2.prettyPrint());}private static void linkedListGet(int elementCount, int loopCount) {List<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new));IntStream.rangeClosed(1, loopCount).forEach(i -> list.get(ThreadLocalRandom.current().nextInt(elementCount)));}private static void arrayListGet(int elementCount, int loopCount) {List<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));IntStream.rangeClosed(1, loopCount).forEach(i -> list.get(ThreadLocalRandom.current().nextInt(elementCount)));}private static void linkedListAdd(int elementCount, int loopCount) {List<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new));IntStream.rangeClosed(1, loopCount).forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount), 1));}private static void arrayListAdd(int elementCount, int loopCount) {List<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));IntStream.rangeClosed(1, loopCount).forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount), 1));}}

这段代码用于比较LinkedList和ArrayList在get和add操作上的性能差异。主要包含以下函数：

  • main函数：创建两个StopWatch对象，分别用于计时get和add操作。通过调用linkedListGet、arrayListGet、linkedListAdd和arrayListAdd方法，分别执行对应的操作并计时。最后打印出计时结果。
  • linkedListGet函数：创建一个包含100000个元素的LinkedList，然后进行100000次随机get操作。
  • arrayListGet函数：创建一个包含100000个元素的ArrayList，然后进行100000次随机get操作。
  • linkedListAdd函数：创建一个空的LinkedList，然后进行100000次在随机位置插入数字1的操作。
  • arrayListAdd函数：创建一个空的ArrayList，然后进行100000次在随机位置插入数字1的操作。

运行结果

在这里插入图片描述

根据提供的测试结果，我们可以分析如下：
随机Get操作性能对比：

  • linkedListGet: 执行时间约为2,992,441,200纳秒（或2.992秒）。
  • arrayListGet: 执行时间约为9,835,300纳秒（或0.098秒）。

​ 这意味着，在随机get操作上，ArrayList的性能明显优于LinkedList。ArrayList的访问时间仅占LinkedList的约0.003%，这是因为ArrayList提供了基于索引的直接访问，而LinkedList需要遍历链表至指定位置。

随机Add操作性能对比：

  • linkedListAdd: 执行时间约为25,455,273,500纳秒（或25.455秒）。
  • arrayListAdd: 执行时间约为1,452,162,900纳秒（或1.452秒）。

​ 对于在随机位置的add操作，虽然两者都需要移动元素以插入新值，但结果显示LinkedList的性能仍然较差。在这个特定场景下（随机位置插入），尽管两者都不是最佳选择（因为都涉及元素的移动）

​ 总结来说，这个测试展示了ArrayList在随机访问（get操作）上的巨大优势，以及在随机位置插入（add操作）相对较好的性能，相对于LinkedList而言。这反映了两种数据结构的基本特性：ArrayList适合于快速访问，而LinkedList更适合于频繁的插入和删除操作（特别是当这些操作发生在列表的开始或结束时）但是当在随机位置add操作，LinkedList的插入性能按照测试结果来看是比ArrayList差的，ArrayList更快

五、LinkedList遍历方式

​ 遍历LinkedList有几种常见方式，每种方法在不同场景下的性能表现各异。以下是遍历LinkedList的几种方法及其简要分析：

1.使用Iterator（迭代器）

Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {String element = iterator.next();// 处理element
}

性能分析：这是最通用的方法，适用于大多数情况。性能良好，特别是在不需要知道当前索引位置时。

2.使用增强for循环（foreach）

for (String element : linkedList) {// 处理element
}
  • 性能分析：增强for循环底层也是通过Iterator实现的，因此性能与直接使用Iterator相似。代码更加简洁，但同样不适用于需要索引或并发修改集合的情况。

3.使用ListIterator（列表迭代器）

ListIterator<String> listIterator = linkedList.listIterator();
while (listIterator.hasNext()) {String element = listIterator.next();// 可以使用listIterator.previous()等方法进行双向遍历// 处理element
}
  • 性能分析：ListIterator提供了额外的功能，如向后遍历和修改元素，但遍历性能与普通Iterator相似。在需要反向遍历或在遍历时修改集合时非常有用。

性能比较

  • 遍历效率：对于LinkedList，使用Iterator或增强for循环通常是最高效且代码最简洁的遍历方式，因为它们直接利用了LinkedList的结构，避免了不必要的索引查找开销。
  • 功能性需求：如果需要在遍历时同时进行元素的添加、删除或获取前一个/后一个元素等操作，ListIterator提供了最佳灵活性。
  • 避免：直接通过索引遍历LinkedList（如传统for循环结合get(index)），因为这会严重降低遍历效率。

​ 综上所述，对于大多数遍历LinkedList的场景，使用Iterator或增强for循环是性能较好且代码更简洁的选择。如果需要额外的遍历控制能力，则考虑使用ListIterator

六、ArrayList遍历方式

​ ArrayList作为基于动态数组实现的集合，它的遍历方式与LinkedList类似，但因为数据结构的不同，遍历性能上会有所区别。以下是遍历ArrayList的几种方法及其性能分析：

1.使用Iterator（迭代器）

Iterator<String> iterator = arrayList.iterator();
while (iterator.hasNext()) {String element = iterator.next();// 处理element
}
  • 性能分析：Iterator遍历对于ArrayList同样适用，性能良好。虽然ArrayList支持快速随机访问，但直接使用Iterator遍历在大多数情况下仍然是可行的选择。

2.使用增强for循环（foreach）

for (String element : arrayList) {// 处理element
}
  • 性能分析：增强for循环同样适用于ArrayList，代码简洁。由于ArrayList支持快速随机访问，这种方式遍历的性能非常高，几乎等同于直接通过索引访问。

3.使用普通for循环（通过索引访问）

for (int i = 0; i < arrayList.size(); i++) {String element = arrayList.get(i);// 处理element
}
  • 性能分析：对于ArrayList，直接通过索引遍历是非常高效的，因为数组支持O(1)时间复杂度的随机访问。在需要索引位置或频繁访问特定位置元素的场景下，这是最佳选择

4.使用ListIterator（列表迭代器）

ListIterator<String> listIterator = arrayList.listIterator();
while (listIterator.hasNext()) {String element = listIterator.next();// 处理element
}
  • 性能分析：虽然ArrayList也可以使用ListIterator，但相比直接通过索引访问或增强for循环，这种方法在ArrayList上的优势不大，除非你需要进行双向遍历或在遍历时修改集合。

性能比较

  • 遍历效率：增强for循环和直接通过索引的普通for循环对于ArrayList来说最为高效，特别是当不需要额外的迭代器功能时。直接索引访问尤其适合需要频繁访问元素索引或进行特定位置操作的场景。
  • 简洁性：增强for循环提供了最简洁的遍历方式，代码可读性好。
  • 灵活性：如果需要在遍历时进行更复杂的操作（如双向遍历、修改元素等），ListIterator提供了必要的灵活性，尽管在ArrayList中，其性能优势不如直接索引访问明显。

​ 综上，对于ArrayList，增强for循环和直接通过索引的普通for循环在性能和实用性上都是很好的选择，具体取决于是否需要索引信息。而Iterator和ListIterator提供了额外的遍历控制能力，但在纯遍历效率上并不比直接索引访问或增强for循环有明显优势。

这篇关于Java-LinkedList和ArrayList的区别、Get/Add操作性能分析以及常见的遍历方式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1072732。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
性能测试介绍

性能测试介绍

性能测试是一种测试方法，旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试，可以确定系统是否能够满足预期的性能要求，找出性能瓶颈和潜在的问题，并进行优化和调整。 发现性能瓶颈：性能测试可以帮助发现系统的性能瓶颈，即系统在高负载或高并发情况下可能出现的问题
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2