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入参值是 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方法
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, 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异常。