本文旨在介绍 java.util.ArrayList<E> 集合类的实现原理；

概要

ArrayList 底层是基于数组实现的，集合所有的操作都是对数组的操作，即是由数组实现的各种方法功能。

内部封装了一个动态再分配的数组，即ArrayList 大小是可变的；

是非线程安全的，java.util.Vector<E> 是线程安全的；

ArrayList 不是 java 程序设计语言的一部分，是某人编写放进标准库的一个使用工具；

ArrayList 中元素是有序可重复的；

主要字段介绍

// 数组初始容量，即内部数组初始大小，final修饰
private static final int DEFAULT_CAPACITY = 10;

// final 修饰，表示不可变数组对象
// 如果是有参构造 ArrayList 对象时，空数组时用该数组对象为 elementData 赋值
private static final Object[] EMPTY_ELEMENTDATA = {};

// final 修饰，表示不可变数组对象
// 如果是无参构造 ArrayList 对象时，用该数组对象为 elementData 赋值
// elementData 赋值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，初始容量为 DEFAULT_CAPACITY
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 内部数组，用于实现 ArrayList 的各种功能
transient Object[] elementData;

// 数组中元素个数，而不是数组容量大小
private int size;

// 集合被修改次数，主要使用是在 Iterator，是防止在迭代的过程中集合被修改
// java.util.AbstractList.modCount 是定义在抽象父类中
protected transient int modCount = 0;

构造

1、空构造函数

2、指定集合容量

指定的容量其实就是底层数组的大小；

3、指定集合构造 ArrayList

1）指定集合为空，则构造空数组的 ArrayList 对象；

2）指定集合类型是 ArrayList，则直接转成数组赋值给内部数组对象；

3）指定集合类型是非 ArrayList，则转成数组后，copy元素来创建内部数组对象；

主要方法解析

1、添加元素 add(E e)

1）modCount 加 1；

2）容量超过数组大小则扩容；

3）在数组后面的空位置插入元素；

2、添加元素 add(int index, E element)

1）在指定索引位置插入指定的元素；

2）index 取值范围为 [0, size]，超出则抛下标越界异常；

3）其他同 add(E e) 方法；

3、查询元素 get(int index)

1）获取指定索引位置的元素；

4、替换元素 set(int index, E element)

1）替换指定索引位置的元素为指定的元素，并返回旧元素（即被替换的元素）；

5、删除元素 remove(int index)

1）删除指定索引位置的元素，并返回被删除的元素；

6、删除元素 remove(Object o)

1）删除集合中第一个和指定元素相等的元素；

2）入参对象可以为 null；

7、获取大小 size()

1）取集合大小，即集合中有多少个元素；

8、判断集合是否为空 isEmpty()

1）如果集合中元素个数为0，则表示集合是空的；

9、获取指定元素在集合中索引位置 indexOf(Object o)

1）入参对象可以为 null，为 null 时取内部数组中第一个为 null 的元素的索引；

2）入参对象不为 null 时，取内部数组中第一个和入参对象相等的元素的索引；

10、获取指定元素在集合中最后的索引位置 lastIndexOf(Object o)

1）从后往前找，从内部数组中找出第一个和指定元素相同的索引位置；

2）其他同 indexOf(Object o)；

11、集合中是否包含指定元素 contains(Object o)

1）调用了 indexOf(Object o) 方法，如果返回的索引值大于或等于0，则说明包含指定的元素；

2）入参对象可以为 null；

12、清空集合 clear()

1）其实就是循环内部数组，把前 size 个元素赋值为 null；

13、集合转数组 toArray()

1）把 ArrayList 集合转成 Object[] 集合；

2）返回类型是 Object[]；

3）其实是根据集合内部数组，复制出一个新的数组返回；

14、集合转数组 toArray(T[] a)

1）该方法会返回指定类型的元素数组；

2）传入的数组 T[] 的长度小于集合大小时，根据集合内部数组，复制出一个新的数组返回，并强转成类型 T[]，返回的数组和集合内部数组相同；

3）如果传入的数组的长度大于或等于集合大小时，把集合内部数组所有元素复制到数组 T[] 中，并返回 T[]；

15、取交集 retainAll(Collection<?> c)

1）a.retainAll(b) 把a集合中未出现在b集合中的元素删除，相当于取两个集合的交集；

16、获取迭代器 iterator()

1）java.util.ArrayList.Itr<E> 是 ArrayList 的内部类，实现了 java.util.Iterator<E> 迭代器接口；

17、获取子集 subList(int fromIndex, int toIndex)

1）java.util.ArrayList.SubList<E> 是 ArrayList 的内部类；

18、给集合中元素排序 sort(Comparator<? super E> c)

1）必须指定用于元素比较的比较器；

2）内部调用了 java.util.Arrays.sort(T[], int, int, Comparator<? super T>) 工具类排序方法；

19、replaceAll(UnaryOperator<E> operator)

1）把集合中所有的元素都进行相同的操作；

20、removeIf(Predicate<? super E> filter)

1）把集合中符合条件的元素全部删掉；