ArrayList<E>

ArrayList 是 Java 集合框架中 List 接口的一个动态数组实现类，位于 java.util 包下。下面详细介绍其底层数据结构和实现原理。

底层数据结构概述

ArrayList 的底层是基于数组实现的，这个数组用于存储元素。在 Java 中，数组是一种连续的内存空间，它可以通过索引快速访问元素，这使得 ArrayList 具备了快速随机访问的能力。

核心属性

ArrayList 类中有几个核心属性，它们在实现动态数组的过程中起着关键作用：

// 存储元素的数组
transient Object[] elementData; 
// 数组中实际存储的元素数量
private int size;

elementData：这是一个 Object 类型的数组，用于存储 ArrayList 中的元素。使用 transient 关键字修饰意味着该数组在序列化时会被忽略，ArrayList 有自己的序列化和反序列化逻辑。
size：表示 ArrayList 中实际存储的元素数量，而不是数组的长度。

构造方法

ArrayList 提供了多个构造方法，用于初始化 elementData 数组：

// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 共享的空数组实例，用于空实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 共享的空数组实例，用于默认大小的空实例
private static final Object[] DEFAULTCAPACITY_EMPTY_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 ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

默认构造方法：创建一个空的 ArrayList，初始时 elementData 是一个空数组，第一次添加元素时会将数组扩容为默认容量（10）。
指定初始容量的构造方法：根据传入的初始容量创建一个指定大小的数组。
包含指定集合元素的构造方法：将指定集合中的元素复制到 ArrayList 中。

动态扩容机制

当向 ArrayList 中添加元素时，如果数组的容量不足，就需要进行扩容操作。扩容的主要步骤如下：

// 添加元素的方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保容量足够
    elementData[size++] = e;
    return true;
}

// 确保内部容量足够
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算所需的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// 确保明确的容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 如果所需最小容量大于当前数组长度，进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 数组最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 数组扩容方法
private void grow(int minCapacity) {
    // 获取旧容量
    int oldCapacity = elementData.length;
    // 新容量为旧容量的 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量小于所需最小容量，将新容量设置为所需最小容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量大于最大数组容量，调用 hugeCapacity 方法处理
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 调用 Arrays.copyOf 方法将旧数组元素复制到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 处理大容量需求
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

添加元素：调用 add 方法添加元素时，首先会调用 ensureCapacityInternal 方法确保数组容量足够。
计算容量：calculateCapacity 方法会根据数组的初始状态计算所需的最小容量。
扩容判断：ensureExplicitCapacity 方法会比较所需最小容量和当前数组长度，如果容量不足则调用 grow 方法进行扩容。
扩容操作：grow 方法会将新容量设置为旧容量的 1.5 倍，如果新容量仍然不足，则将新容量设置为所需最小容量。最后，使用 Arrays.copyOf 方法将旧数组元素复制到新数组。

元素的增删改查操作

添加元素：可以使用 add(E e) 方法在列表末尾添加元素，也可以使用 add(int index, E element) 方法在指定位置插入元素。插入元素时，需要将插入位置之后的元素依次后移。

// 在指定位置插入元素
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // 确保容量足够
    // 将插入位置之后的元素依次后移
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

删除元素：可以使用 remove(int index) 方法删除指定位置的元素，也可以使用 remove(Object o) 方法删除指定元素。删除元素时，需要将删除位置之后的元素依次前移。

// 删除指定位置的元素
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 work

    return oldValue;
}

修改元素：可以使用 set(int index, E element) 方法修改指定位置的元素。

// 修改指定位置的元素
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

查找元素：可以使用 get(int index) 方法根据索引查找元素，也可以使用 indexOf(Object o) 方法查找元素的索引。

// 根据索引查找元素
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

// 查找元素的索引
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}