java中的集合之List

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

ArrayList: 基于动态数组实现，支持快速随机访问，适用于需要频繁读取数据的场景。
LinkedList: 基于双向链表实现，支持高效的插入和删除操作，适合需要频繁插入和删除的场景。
Vector: 基于动态数组实现，但线程安全，性能较 ArrayList 低，现代开发中不推荐使用。
Stack: 继承自 Vector，实现了栈的功能（后进先出）。
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;}

扩容机制

容量检查：每当 ArrayList 需要添加新元素时，会先检查当前容量是否足够。如果需要的容量超过当前数组容量，则会触发扩容。
计算新容量：扩容时会计算一个新的容量，通常是将当前容量增加一半。具体来说，ArrayList 在 Java 标准库中的实现中，通常将容量增加 50%（即扩容为原容量的 1.5 倍），以提供足够的余地而不会频繁触发扩容。
创建新数组：创建一个更大的数组来容纳更多的元素。新数组的大小是根据计算结果确定的。
复制元素：将原数组中的元素复制到新的数组中。此操作的时间复杂度是 O(n)，其中 n 是原数组的长度。
更新引用：将 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);}

元素删除

删除操作步骤：

找到要删除的元素的位置：根据索引或对象。
调整数组：如果删除的不是最后一个元素，需要将后续元素向前移动。
更新 size：减少列表的大小。
释放引用：将被移除的元素位置设为 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异常。