Java ArrayList 、LinkedList 集合

2024-06-14 19:48

本文主要是介绍Java ArrayList 、LinkedList 集合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


前言:

         ArrayList、 LinkedList 是 用于存储对象引用列表的两个Java Collection Framework类  。ArrayList、 LinkedList 都实现了  List  接口。

List Interface

       List只是元素的有序集合(也称为序列)。它添加了面向位置的操作,可用于快速访问,添加和删除列表中特定索引位置的元素。List接口具有Collection和Iterable作为超级接口。它可以允许存储重复项和空值。它提供对其元素的索引访问。


import java.util.*;
public class MyClass {// Unsynchronized or Not thread safeList<Object> arrayList = new ArrayList<>(); // declares an array listList<Object> linkedList = new LinkedList(); // declares a linked list   // ensures thread safety List<Object> tsArrayList = Collections.synchronizedList(new LinkedList<>());List<Object> tsLinkedList = Collections.synchronizedList(new LinkedList<>());   
}

       Vector类似于  ArrayList 它们提供自动同步,这使它们的线程安全,但会导致一些性能开销。 

LinkedList

      LinkedList 数据结构包含一组有序的数据元素(如知道节点),使得每个元素包含到其后继(链接或参考下一个元素)。序列的最后一个元素(或尾部)指向null元素。链表本身包含对列表第一个元素的引用,称为head元素。  Java中的LinkedList是List接口的双链表实现。在双向链表中,每个节点都指向其上一个节点和下一个节点。它实现的其他接口是  Serializable,Cloneable和  Deque  (super-interface为Queue))。 

ArrayList

      ArrayList是List接口的可调整大小的数组实现。它在内部实现为对象数组,可以根据需要增加大小以支持集合中更多数量的元素。可以ArrayList 通过构造函数  指定an的初始容量,  ArrayList(int initialCapacity)  然后void ensureCapacity(int minCapacity)在必要时使用它来增加容量   ,以确保它至少可以保存最小容量参数指定的元素数。

它还包括一种基于元素减小大小的方法。 void trimToSize()


// calling constructure ArrayList<type>(initialCapacity)
List arr = new ArrayList<Integer>(10);

     默认情况下, ArrayList 创建初始容量列表10,而  LinkedList 只构造没有任何初始容量的空列表。  LinkedList 没有实现RandomAccess接口,而是  ArrayList 实现  RandomAccess 接口(而不是Deque接口)

特 性 

数组列表

链表

添加(或删除)元素

这涉及将所有现有元素移回(或转发)一个地方,需要复制通过调用System.arraycopy()完成的项目   - 最佳案例 时间复杂度为O(1)。

平均情况时间复杂度O(n)因为System.arraycopy()是线性时间。 

这涉及为元素分配(或解除分配)内部记录,然后重新调整几个链接并具有固定成本。 - 时间复杂度为O(1)。在列表中间添加(或删除)元素将具有O(n)的时间复杂度,因为它将涉及遍历列表。

附加元素

通常,这涉及将内部数组位置设置为元素引用,时间复杂度为O(1)。但偶尔对于溢出的情况,它会导致数组被重新分配并且再次具有固定的平均成本,涉及触发调用到  System.arrayCopy(),最坏情况  时间复杂度为O(n)。

这只涉及分配内部对象,并且成本是统一的。 

内存空间开销

它有一个内存空间开销,因为必须预先分配对象列表,这意味着列表末尾的空元素。

它有一个内存空间开销,用于存储列表中每个元素的前一个和下一个元素的引用。

随机访问其元素

随机访问具有固定的时间 - 复杂度为O(1)。 

进行随机访问的时间与列表的大小成比例(除非这是成本固定的第一个或最后一个元素) - 平均情况时间复杂度为O(n)。

空值是的,它可以存储是的,它可以存储
重复是的,它可以存储

是的,它可以存储

提示

        以下用于遍历LinkedList的代码示例。下面的代码会非常慢LinkedList 不支持随机访问,每次迭代遍历时都会产生巨大的开销:


LinkedList ll = new LinkedList();
…
…
Object o = null;   
for (int i = 0; i < list.size(); i++)
{       o = list.get(i);…
}

提高性能的更好方法是使用以下代码:


LinkedList ll = new LinkedList(); 
… 
…   
Object o = null;    
ListIterator li = list.listIterator(0);   
while (li.hasNext()){o = ll.next();…    
}

总结:

     ArrayList 更快更好,因为它支持对其元素的随机访问。遍历链接列表或在中间插入项目非常昂贵,因为您必须迭代每个项目并且很可能有缓存未命中。如果需要在单次迭代中对列表的多个项执行处理,则迭代的开销可能LinkedList  比ArrayList  涉及多次复制数组元素的开销小


 

这篇关于Java ArrayList 、LinkedList 集合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1061356

相关文章

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

Spring Boot spring-boot-maven-plugin 参数配置详解(最新推荐)

《SpringBootspring-boot-maven-plugin参数配置详解(最新推荐)》文章介绍了SpringBootMaven插件的5个核心目标(repackage、run、start... 目录一 spring-boot-maven-plugin 插件的5个Goals二 应用场景1 重新打包应用

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定,动态列2、动态下拉3、自定义锁定行/列,添加密码4、合并

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

浅析Spring如何控制Bean的加载顺序

《浅析Spring如何控制Bean的加载顺序》在大多数情况下,我们不需要手动控制Bean的加载顺序,因为Spring的IoC容器足够智能,但在某些特殊场景下,这种隐式的依赖关系可能不存在,下面我们就来... 目录核心原则:依赖驱动加载手动控制 Bean 加载顺序的方法方法 1:使用@DependsOn(最直

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件