网站建设与设计试题,电子产品开发流程图,西安市高新规划建设局网站,建设银行成都官网招聘网站Java 中的 List 是一个接口#xff0c;定义了一组有序的元素集合#xff0c;允许重复元素。List 接口有多个实现形式#xff0c;主要包括#xff1a;
ArrayList: 基于动态数组实现#xff0c;支持快速随机访问#xff0c;适用于需要频繁读取数据的场景。LinkedList: 基于…Java 中的 List 是一个接口定义了一组有序的元素集合允许重复元素。List 接口有多个实现形式主要包括
ArrayList: 基于动态数组实现支持快速随机访问适用于需要频繁读取数据的场景。LinkedList: 基于双向链表实现支持高效的插入和删除操作适合需要频繁插入和删除的场景。Vector: 基于动态数组实现但线程安全性能较 ArrayList 低现代开发中不推荐使用。Stack: 继承自 Vector实现了栈的功能后进先出。CopyOnWriteArrayList: 线程安全的 ArrayList 实现通过在写操作时复制数组适合读操作远多于写操作的场景。
每种实现都有其特定的特点和适用场景可以根据具体需求选择使用。这里主要学习平时最常用的ArrayList
ArrayList
ArrayList 的底层数据结构是动态数组具有快速的随机访问和动态扩容能力。虽然在增加和删除元素时可能会有性能开销但其访问操作具有 O(1) 的时间复杂度。
内部几个属性
private int size;
transient Object[] elementData;
private static final int DEFAULT_CAPACITY 10;elementData 是存储元素的底层数组。size 记录当前 ArrayList 中的元素个数。DEFAULT_CAPACITY默认容量大小。
ArrayList默认无参构造函数elementData 是个空数组int参数可以指定elementData 初始化大小。 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);}}插入操作
添加元素时如果数组有足够的空间就直接插入到数组的末尾。如果没有足够的空间就触发扩容操作。 public boolean add(E e) {//检查扩容ensureCapacityInternal(size 1); // Increments modCount!!//插入元素elementData[size] e;return true;}扩容机制 容量检查每当 ArrayList 需要添加新元素时会先检查当前容量是否足够。如果需要的容量超过当前数组容量则会触发扩容。 计算新容量扩容时会计算一个新的容量通常是将当前容量增加一半。具体来说ArrayList 在 Java 标准库中的实现中通常将容量增加 50%即扩容为原容量的 1.5 倍以提供足够的余地而不会频繁触发扩容。 创建新数组创建一个更大的数组来容纳更多的元素。新数组的大小是根据计算结果确定的。 复制元素将原数组中的元素复制到新的数组中。此操作的时间复杂度是 O(n)其中 n 是原数组的长度。 更新引用将 ArrayList 的内部数组引用更新为新的数组。 扩容操作在ensureCapacityInternal()方法内完成。 // minCapacity入参值是 size1 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方法 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);}元素删除
删除操作步骤
找到要删除的元素的位置根据索引或对象。调整数组如果删除的不是最后一个元素需要将后续元素向前移动。更新 size减少列表的大小。释放引用将被移除的元素位置设为 null 以帮助垃圾回收。 public E remove(int index) {rangeCheck(index);modCount;E oldValue elementData(index);//需要移动的元素数量从被删除元素往后的所有元素int numMoved size - index - 1;if (numMoved 0)//复制移动数组System.arraycopy(elementData, index1, 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异常。
