java中的集合之List

embedded/2024/9/25 14:56:53/

Java 中的 List 是一个接口,定义了一组有序的元素集合,允许重复元素。List 接口有多个实现形式,主要包括:

  1. ArrayList: 基于动态数组实现,支持快速随机访问,适用于需要频繁读取数据的场景。
  2. LinkedList: 基于双向链表实现,支持高效的插入和删除操作,适合需要频繁插入和删除的场景。
  3. Vector: 基于动态数组实现,但线程安全,性能较 ArrayList 低,现代开发中不推荐使用。
  4. Stack: 继承自 Vector,实现了栈的功能(后进先出)。
  5. CopyOnWriteArrayList: 线程安全的 ArrayList 实现,通过在写操作时复制数组,适合读操作远多于写操作的场景。

每种实现都有其特定的特点和适用场景,可以根据具体需求选择使用。这里主要学习平时最常用的ArrayList

ArrayList

ArrayList 的底层数据结构是动态数组,具有快速的随机访问和动态扩容能力。虽然在增加和删除元素时可能会有性能开销,但其访问操作具有 O(1) 的时间复杂度。

内部几个属性

java">private int size;
transient Object[] elementData; 
private static final int DEFAULT_CAPACITY = 10;
  • elementData 是存储元素的底层数组。
  • size 记录当前 ArrayList 中的元素个数。
  • DEFAULT_CAPACITY默认容量大小。

ArrayList默认无参构造函数,elementData 是个空数组,int参数可以指定elementData 初始化大小。

java">    public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
插入操作

添加元素时,如果数组有足够的空间,就直接插入到数组的末尾。如果没有足够的空间,就触发扩容操作。

java">    public boolean add(E e) {//检查扩容ensureCapacityInternal(size + 1);  // Increments modCount!!//插入元素elementData[size++] = e;return true;}
扩容机制
  1. 容量检查:每当 ArrayList 需要添加新元素时,会先检查当前容量是否足够。如果需要的容量超过当前数组容量,则会触发扩容。

  2. 计算新容量:扩容时会计算一个新的容量,通常是将当前容量增加一半。具体来说,ArrayList 在 Java 标准库中的实现中,通常将容量增加 50%(即扩容为原容量的 1.5 倍),以提供足够的余地而不会频繁触发扩容。

  3. 创建新数组:创建一个更大的数组来容纳更多的元素。新数组的大小是根据计算结果确定的。

  4. 复制元素:将原数组中的元素复制到新的数组中。此操作的时间复杂度是 O(n),其中 n 是原数组的长度。

  5. 更新引用:将 ArrayList 的内部数组引用更新为新的数组。

    扩容操作在ensureCapacityInternal()方法内完成。

java">   // minCapacity入参值是 size+1 private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}//计算容量private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//当前list是空,创建时未设置容量//返回默认容量(10)和新增后实际容量的最大值return Math.max(DEFAULT_CAPACITY , minCapacity);}return minCapacity;}
//确认是否扩容private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious code//计算操作后的容量大于当前可变数组的大小,存不下了。if (minCapacity - elementData.length > 0)grow(minCapacity);}

按照上面的逻辑,如果使用默认无参构造函数创建list,第一次执行add方法,计算容量会返回默认容量10,然后在创建一个10长度的数组,也就是第一次add时候才创建数组。

来看具体的grow方法

java">    private void grow(int minCapacity) {// 旧容量int oldCapacity = elementData.length;//新容量 = 旧容量 + 旧容量右移位1(相当于除以2) 这也就是扩容1.5的来源int newCapacity = oldCapacity + (oldCapacity >> 1);//再次判断新容量是否小于需要的最小容量,这里第一次添加的时候会走这里,因为旧容量=0,计算出新容量还是0if (newCapacity - minCapacity < 0)newCapacity = minCapacity;/**判断是否超过最大容量,MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8,一般走不到这里,这么大容量使用场景不合适,可能已经内存溢出了*/if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win://使用Arrays.copyOf扩容至新容量elementData = Arrays.copyOf(elementData, newCapacity);}
元素删除

删除操作步骤:

  1. 找到要删除的元素的位置:根据索引或对象。
  2. 调整数组:如果删除的不是最后一个元素,需要将后续元素向前移动。
  3. 更新 size:减少列表的大小。
  4. 释放引用:将被移除的元素位置设为 null 以帮助垃圾回收。
java">    public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);//需要移动的元素数量,从被删除元素往后的所有元素int numMoved = size - index - 1;if (numMoved > 0)//复制移动数组System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its workreturn oldValue;}

System.arraycopy(Object src, int srcPos,Object dest, int destPos, int length);4个参数的意思:

  • src: 源数组,从中复制元素。
  • srcPos: 源数组中的起始位置(起始索引),从该位置开始复制元素。
  • dest: 目标数组,将元素复制到该数组中。
  • destPos: 目标数组中的起始位置(起始索引),从该位置开始写入元素。
  • length: 复制的元素数量。
Arrays.asList操作

Arrays.asList 将数组转换为一个固定大小的 List。使用的时候要特别注意,返回的 List 不能改变大小,但可以修改元素。因为返回的实例是Arrays对应的一个内部类ArrayList,不是java.util.ArrayList。这个内部类ArrayList中存储数据的数组是final类型的,虽然继承自AbstractList,但是add()和remove()方法没有实现,添加或删除操作会抛出UnsupportedOperationException异常。


http://www.ppmy.cn/embedded/111500.html

相关文章

Gitbook 本地安装教程

Gitbook 本地安装教程 安装 node [nodejs的v10.21.0版本&#xff0c;下载地址&#xff1a;https://nodejs.org/dist/v10.21.0/node-v10.21.0-x64.msi] 其他版本有问题 npmnpm install -g gitbook-cligitbook init [初始化目录结构]gitbook build [编译]gitbook serve [运行] …

Probabilistic Embeddings for Cross-Modal Retrieval 论文阅读

Probabilistic Embeddings for Cross-Modal Retrieval 论文阅读 Abstract1. Introduction2. Related work3. Method3.1. Building blocks for PCME3.1.1 Joint visual-textual embeddings3.1.2 Probabilistic embeddings for a single modality 3.2. Probabilistic cross-modal…

计算机网络八股总结

这里写目录标题 网络模型划分&#xff08;五层和七层&#xff09;及每一层的功能五层网络模型七层网络模型&#xff08;OSI模型&#xff09; 三次握手和四次挥手具体过程及原因三次握手四次挥手 TCP/IP协议组成UDP协议与TCP/IP协议的区别Http协议相关知识网络地址&#xff0c;子…

鸿蒙轻内核M核源码分析系列十九 Musl LibC

往期知识点记录&#xff1a; 鸿蒙&#xff08;HarmonyOS&#xff09;应用层开发&#xff08;北向&#xff09;知识点汇总 轻内核M核源码分析系列一 数据结构-双向循环链表 轻内核M核源码分析系列二 数据结构-任务就绪队列 鸿蒙轻内核M核源码分析系列三 数据结构-任务排序链表 轻…

基于Python的B站热门视频可视化分析与挖掘系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 随着互联网视频平台的迅猛发展&#xff0c;如何从海量的数据中提炼出有价值的信息成为了内容创作者们关注的重点之一。B站&#xff08;哔哩哔哩&#xff09;作为国内领先的年轻人文化社区&#xf…

ThreeJS入门(002):学习思维路径

查看本专栏目录 - 本文是第 002篇入门文章 文章目录 如何使用这个思维导图 Three.js 学习思维导图可以帮助你系统地了解 Three.js 的各个组成部分及其关系。下面是一个简化的 Three.js 学习路径思维导图概述&#xff0c;它包含了学习 Three.js 的主要概念和组件。你可以根据这个…

首批通过!华为云CodeArts Snap智能开发助手通过可信AI智能编码工具评估,获当前最高等级

近日&#xff0c;华为云CodeArts Snap智能开发助手在中国信通院组织的智能编码工具首轮评估中&#xff0c;最终获得4级评级, 成为国内首批通过该项评估并获得当前最高评级的企业之一。 此次评估以《智能化软件工程技术和应用要求 第2部分&#xff1a;智能开发能力》为依据&…

【Kubernetes】常见面试题汇总(十三)

目录 39.简述 Kubernetes Scheduler 使用哪两种算法将 Pod 绑定到 worker 节点&#xff1f; 40.简述 Kubernetes kubelet 的作用&#xff1f; 41.简述 Kubernetes kubelet 监控 Worker 节点资源是使用什么组件来实现的&#xff1f; 39.简述 Kubernetes Scheduler 使用哪两种算…