ArrayList 是基于数组实现的，继承了 AbstractList 抽象类，实现了 List 接口，支持动态扩容，适用于随机访问的场景，并且在大小不经常变化的情况下，ArrayList 要比 LinkedList 节省空间，所以是一个优先选项。主要有以下几个关键点：

• 可包含空元素 null
• size、isEmpty、get、set、iterator 等操作的时间复杂度为 O(1)，其它操作为线性时间
• 非线程安全

初始化

在 JDK 7 中，ArrayList 的默认构造方法会将初始化容量设为 10，不管这个大小合不合适，数组需不需要。这看似不起眼的大小为 10 的数组，在高频率的使用环境下，也是一个不小的负担。

public ArrayList() { 
    this.elementData = new Object[10]; 
}

因此在 JDK 8 中，ArrayList 的默认构造方法做了一个小变动，改动后的默认构造方法，不再分配内部数组，而是使用了一个空数组。要等到真正需要存储数据的时候，才为这个数组分配空间。

public ArrayList() { 
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 
}

这个延迟初始化的操作，经测试报告统计，改动后的内存的使用减少了 13%，平均响应时间提高了 16%。这个延迟初始化的思想后来也被运用到了 HashMap 中，在 JDK 11 以后，也将 HashMap 的默认构造方法进行了延迟初始化，不再默认分配 16 个元素空间了。

成员属性

在 JDK 8 中，ArrayList 的成员属性主要有以下成员：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // 默认容量大小
    private static final int DEFAULT_CAPACITY = 10;
    // 用于ArrayList空实例的共享空数组（指定了容量，但是容量为0）
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 用于ArrayList空实例的共享空数组（默认构造方法）
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 真正存储ArrayList中的元素的数组
    transient Object[] elementData;
    // 实际存储数组元素的个数
    private int size;
    // AbstractList类的属性，表示elementData在结构上被修改的次数,每次add或remove都会加1
    protected transient int modCount = 0;
    // 数组可扩容的最大长度
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    ......
}

EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 两个空数组主要用于不同的初始化场景。前者适用在指定了初始化容量（initialCapacity == 0）的场景下，后者适用在未指定任何参数的场景下。在扩容时针对这两种类型的空数组，其扩容策略是不一样的。

提供初始容量的构造方法：

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果容量为0，则都指向同一个共享的空数组，以减少内存占用
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

无参构造方法，默认为空数组：

public ArrayList() {
    // 此数组和上面的EMPTY_ELEMENTDATA区分开来，用来在添加第一个元素的时候，确定要扩容多少
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

通过一个集合来初始化：

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

可以看到，这三种方式针对空数组的赋值是不同的，具体区别在 add 方法里解析。

ArrayList 内部还维护了一个 modCount 属性用来记录 ArrayList 结构发生变化的次数，如果在执行一个动作前后 modCount 的值不相等，说明这个 ArrayList 被其它线程修改了。如果在创建迭代器之后的任何时候以任何方式修改了列表（增加、删除、修改），除了通过迭代器自己的 remove 或 add 方法，迭代器将抛出 ConcurrentModificationException 异常。

需要注意的是：这里异常的抛出条件是检测到 modCount != expectedmodCount，如果并发场景下一个线程修改了 modCount 值时另一个线程又 “及时地” 修改了 expectedmodCount 值，则异常不会抛出。所以不能依赖于这个异常来检测程序的正确性。

方法

// 将此ArrayList实例的容量调整为列表的当前大小。使用此操作来最大程度地减少ArrayList实例的存储
public void trimToSize()
public int size()
public boolean isEmpty()
public boolean contains(Object o)
public void clear()    
// 返回指定元素在此列表中首次出现的索引，如果此列表不包含该元素则返回-1
public int indexOf(Object o)
// 返回指定元素在此列表中最后一次出现的索引，如果此列表不包含该元素则返回-1    
public int lastIndexOf(Object o)
public Object[] toArray()    
public <T> T[] toArray(T[] a)
public E get(int index)
// 用指定的元素替换此列表中指定位置的元素
public E set(int index, E element)
public boolean add(E e)
// 将指定元素插入此列表中的指定位置。将当前在该位置的元素（如果有）和任何后续元素右移
public void add(int index, E element)  
// 将指定集合中的所有元素追加到此列表的末尾    
public boolean addAll(Collection<? extends E> c)
// 从指定位置开始，将指定集合中的所有元素插入此列表    
public boolean addAll(int index, Collection<? extends E> c)     
public E remove(int index)
public boolean remove(Object o)  
// 从此列表中删除指定集合中包含的所有元素 
public boolean removeAll(Collection<?> c)    
// 仅保留此列表中包含在指定集合中的元素。换句话说，从该列表中删除所有未包含在指定集合中的元素    
public boolean retainAll(Collection<?> c)    
public ListIterator<E> listIterator(int index)
public ListIterator<E> listIterator()
public Iterator<E> iterator()
public Spliterator<E> spliterator()    
// 返回此列表在指定的fromIndex（包括）和toIndex（不包括）之间的视图    
public List<E> subList(int fromIndex, int toIndex)   
// 循环列表元素，对其执行action    
public void forEach(Consumer<? super E> action) 
// 删除此集合中满足给定谓词的所有元素    
public boolean removeIf(Predicate<? super E> filter) 
//     
public void replaceAll(UnaryOperator<E> operator)
// 根据指定的Comparator策略对该列表进行排序    
public void sort(Comparator<? super E> c)

1. add

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

添加元素时主要进行了两步操作，通过 ensureCapacityInternal() 方法来保证容量足够使用，添加单元素时 size+1 即为最少需要的空间大小，批量添加时则为 size + numNew。然后对 elementData 数组赋值。

ensureCapacityInternal 方法内部会根据传入的最小所需容量进行扩容。

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算最少需要的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 默认的空数组实例第一次添加元素时，使用默认的容量大小与minCapacity的最大值
        // 如果使用new ArrayList()创建，则默认容量为DEFAULT_CAPACITY=10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    // 修改次数+1，用于fail-fast处理
    modCount++;
    // 如果需要的容量大于elementData的长度，则进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

在 calculateCapacity 方法处，会先判断当前实例数组是否是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 实例，这个数组在通过 new ArrayList() 构造实例时被赋值，用来区别于 EMPTY_ELEMENTDATA ，在第一次进行数组操作的时候会进行判断。

要注意通过这几种构造函数创建的 ArrayList 实例后续在扩容机制上的不同！

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 扩容为原来的 1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 与最小可用容量比较，取两者最大值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    // 上面在相加的时候可能产生整型溢出
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

进行扩容时，会把标准扩容容量和最小可用容量进行对比，取两者较大值 ，也就是旧容量的 1.5 倍与最小可用容量之间的较大值。最后调用 Arrays.copyOf 复制原数组，将 elementData 赋值为得到的新数组。由于数组复制代价较高，所以建议在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

2. remove

删除指定下标的元素时，如果下标没有越界，则取出下标对应的值，如果是数组最后一个元素则将其置为空，否则将数组中该下标后面的元素都往前挪一位，需要挪的元素数量是 size - index - 1，时间复杂度为 O(n)，所以删除元素的代价比较高。

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;
}

删除第一个值为指定值的元素则使用 remove(Object o) 方法，参数 o 可以为 null，内部通过 fastRemove 来删除指定元素，其与 remove(int index) 几乎一样，只不过不返回被删除的元素。

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            // 比较对象时依赖equals方法，因此类型变量E对应的类注意重写equlas方法
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
private void fastRemove(int index) {
    modCount++;
    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
}

从上面的源码可以看出，ArrayList 的增删改查操作实质上就是对底层数组的操作，新增元素时需要对数组进行扩容操作，删除也需要对数组进行复制操作，所以 ArrayList 的新增和删除效率会非常低，但是相对的，得益于底层的数组结构，在进行查找和更改操作时，可以根据下标直接进行操作，只有 O(1) 的复杂度，因此在查找需求比较频繁的操作中，推荐使用 ArrayList，可以极大的增加操作效率，但是在增删比较频繁的时候，就需要考虑其他的数据结构了。

同时，要注意合理的使用 ArrayList 的构造方法，初始化时如果已经知道当前数据的大小，可以直接使用 ArrayList(int initialCapacity) 构造方法指定初始容量，这样可以避免在添加数据时频繁进行扩容降低性能，同时也可以避免 1.5 倍的扩容机制造成的空间浪费。

3. 遍历

ArrayList 支持三种遍历方式：

• for 循环下标遍历
• 迭代器（Iterator、ListIterator、Spliterator），其中 Spliterator 支持并行遍历
• foreach 语句

其中，迭代器 Iterator 和 ListIterator 的主要区别如下：

• ListIterator 有 add()、set() 方法，可以在遍历时更新 List 中的元素，而 Iterator 不能。

• ListIterator 和 Iterator 都有 hasNext() 和 next() 方法，可以实现顺序向后遍历，但是 ListIterator 还有 hasPrevious() 和 previous() 方法，可以实现逆向遍历。

• ListIterator 可以定位当前的索引位置，nextIndex() 和 previousIndex() 可以实现。

4. 排序

List<String> strList = new ArrayList<String>(4);
strList.add("1");
strList.add("2");
strList.add("3");
// 可以使用以下三种排序方式
Collections.sort(strList);
Collections.sort(strList, String::compareTo);
strList.sort(String::compareTo);

Collections.sort() 底层调用的是 Arrays.sort() 方法，具体的排序过程会根据数据类型、数据集大小等因素选择不同的排序算法：

• 对于原始数据类型，目前使用的是双轴快速排序（Dual-Pivot QuickSort），是一种改进的快速排序算法，早期版本是相对传统的快速排序。

• 对于对象数据类型，目前则是使用 TimSort，思想上也是一种归并和二分插入排序（binarySort）结合的优化排序算法。TimSort 并不是 Java 的独创，简单说它的思路是查找数据集中已经排好序的分区，然后合并这些分区来达到排序的目的。

• 另外 Java 8 引入了并行排序算法（parallelSort），这是为了充分利用现代多核处理器的计算能力，底层实现基于 fork-join 框架，当处理的数据集比较小时，差距不明显，甚至还表现差一点；但当数据集增长到数万或百万以上时，提高就非常大了，具体还是取决于处理器和系统环境。

5. 集合转数组

public Object[] toArray() {
    // 直接复制ArrayList的elementData
    return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // 利用反射生成特定类型的数组并复制
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

6. 数组转集合

// 另外，除了根据ArrayList转化成数组，同样可以根据Arrays的asList将数组转换成List
// 备注：Arrays是数组操作的util类，可以进行排序、查找、复制、遍历等
List<String> strList = Arrays.asList("1", "2", "3");

Arrays 类是数组操作的工具类，它提供了 asList() 方法用来将数组转换成 List 对象。但是在使用时需要注意：asList() 方法返回的 List 是 Arrays 类的私有静态内部类 ArrayList，它跟 java.util.ArrayList 不同，它没有重写 java.util.AbstractList 的 remove、add 等方法，默认实现是直接抛 UnsupportedOperationException，因此如果我们直接操作 asList 方法返回的集合会报错。

序列化

ArrayList 有两个属性被 transient 关键字修饰，当某个字段被声明为 transient 后，JDK 默认的序列化机制就会忽略该字段，反序列化后该字段会自动获得 0 或者 null 值。

transient Object[] elementData; 
protected transient int modCount = 0;

那为什么最为重要的数组元素 elementData 要用 transient 修饰呢？

答案是：

ArrayList 不想用 JDK 默认的序列化机制来序列化 elementData 数组，因为默认机制会序列化整个数组，但并不是整个数组都存储实际元素。因此 ArrayList 重写了 readObject、writeObject 方法自定义了自己的序列化和反序列化策略。根据 size 序列化实际使用的元素，忽略数组中的其它位置，提高了效率并节省了空间。

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    int expectedModCount = modCount;
    // 调用JDK默认的序列化策略，序列化其它的字段
    s.defaultWriteObject();
    // size为实际使用的长度，而不是容量
    s.writeInt(size);
    // 只序列化size元素
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    // 调用JDK默认的反序列化机制，反序列化没有标记为static、transient的字段，包括size等
    s.defaultReadObject();
    s.readInt();
    if (size > 0) {
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        // 数组扩容
        ensureCapacityInternal(size);
        Object[] a = elementData;
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

Collections

Collections 是 JDK 提供的一个工具类，包含了很多方便、实用的静态方法，具体如下：

排序：

public static <T extends Comparable<? super T>> void sort(List<T> list)
public static <T> void sort(List<T> list, Comparator<? super T> c)
// 二分查找，注意集合必须是有序的    
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
// 反转列表
public static void reverse(List<?> list)    
// 随机对列表元素重排序
public static void shuffle(List<?> list)    
// 最大值    
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
// 最小值    
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)

不可修改试图：
从 Java 8 开始，Java 核心类库通过 Collections 类提供了一系列的生成不可更改的集合的方法。这些方法极大地减轻了集合的共享和维护问题。

空集合：

List.subList

我们通常会使用 List.subList 方法对 List 做切片处理，即取出其中部分元素构成一个新的 List。但我们要注意 List.subList 返回的子 List 不是一个普通的 ArrayList。这个子 List 可以认为是原始 List 的视图，它会和原始 List 相互影响。如果不注意，很可能会因此产生 OOM 问题。

如下代码示例：

private static List<List<Integer>> data = new ArrayList<>();
private static void oom() {
    for (int i = 0; i < 1000; i++) {
        List<Integer> rawList = IntStream.rangeClosed(1, 100000).boxed().collect(Collectors.toList());
        data.add(rawList.subList(0, 1));
    }
}

你可能会觉得，这个 data 变量里面最终保存的只是 1000 个具有 1 个元素的 List，不会占用很大空间，但程序运行不久就出现了 OOM。原因是循环中的 1000 个具有 10 万个元素的 List 始终得不到回收，因为它始终被 subList 方法返回的 List 强引用。

我们分析下 ArrayList 的源码，看看为什么会是这样。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, offset, fromIndex, toIndex);
    }
    private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;
        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }
        ......
    }
}

可以看到，获得的子 List 其实是内部类 SubList 的实例，并不是普通的 ArrayList 实例，只是在初始化的时候传入了 this，这个 SubList 中的 parent 字段就是原始的 List。

SubList 初始化时并没有把原始 List 中的元素复制到独立的变量中保存。我们可以认为 SubList 是原始 List 的视图而不是独立的 List。双方对元素的修改会相互影响，而且 SubList 强引用了原始的 List，所以大量保存这样的 SubList 会导致 OOM。