上一篇我们通过一道算法题了解了数组，数组有一个明显的缺点是需要指定容量且不能改变，而且我们不能明确数组中存了多少元素。开发中的场景很少明确的知道有多少数据，所以就有了比较高级的容器，今天我们来学习List集合中的ArrayList。

java.util.List继承了Collection接口，定义了对元素增删改的方法，由其不同的子类实现，它的所有实现类：AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector。最常用的子类如下图所示：

今天我们先学习ArrayList，这是开发中最常用的数据结构。

成员变量

//默认的初始化容量private static final int DEFAULT_CAPACITY = 10;//空数组private static final Object[] EMPTY_ELEMENTDATA = {};//默认初始容量空数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//ArrayList存放元素的数组容器transient Object[] elementData; // non-private to simplify nested class access//存储的元素的数量private int size;//最大容量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList提供了3种构造函数：

ArrayList()：构造一个初始容量为DEFAULT_CAPACITY（10）的空列表，其中elementData成员变量初始化为{}，不包含任何元素。源码如下：

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

相信看了源码的你肯定有个疑问，空参构造函数里面不就是给elementData赋值了一个空的数组吗，你怎么就说它是一个初始化容量为10的数组呢？我们后面讲添加元素的时候会讲，在这里它还是一个空数组，只是第一次添加元素的时候会将容量扩充到10.

ArrayList(int initialCapacity)：构造指定初始容量的空列表。initialCapacity需满足大于等于0，如果小于0则抛出异常IllegalArgumentException。

public ArrayList(int initialCapacity) {    //指定的容量大于0，则elementData初始化为initialCapacity大小的数组    if (initialCapacity > 0) {        this.elementData = new Object[initialCapacity];    } else if (initialCapacity == 0) {        //指定的容量等于0，则elementData初始化为{}，不包含任何元素        this.elementData = EMPTY_ELEMENTDATA;    } else {        //小于0则抛出异常        throw new IllegalArgumentException("Illegal Capacity: "+                                           initialCapacity);    }}

这里要注意initialCapacity=0得到的elementData和我们无参得到的是不一样的，这里得到的是初始容量为0的空数组，毕竟ensureCapacityInternal方法中只对DEFAULTCAPACITY_EMPTY_ELEMENTDATA做了特殊处理，所以虽然我们看到DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA都是{}，但是处理得到的结果还是不一样的。

ArrayList(Collection<? extends E> c)：构造一个包含指定集合的元素列表。

public ArrayList(Collection<? extends E> c) {    //将构造函数参数列表转换为数组并赋值给elementData    elementData = c.toArray();    //如果元素个数不为0    if ((size = elementData.length) != 0) {        // 如果elementData元素的class类不是Object类型，则重新复制elementData中的元素        if (elementData.getClass() != Object[].class)            elementData = Arrays.copyOf(elementData, size, Object[].class);    } else {        // 元素个数为0，依然把elementData初始为空数组        this.elementData = EMPTY_ELEMENTDATA;    }}

add添加元素方法有很多重载方法，我们先学习比较基础也是比较常用的add(E e)，在尾部添加元素。其源码和注释如下：

public boolean add(E e) {    //保证足够的容量，如果有必要则扩容，并且增加modCount    ensureCapacityInternal(size + 1);  // Increments modCount!!    //将添加的元素存在最后，并将size+1    elementData[size++] = e;    return true;}

勾勾在添加注释的时候以无参构造时解释各个变量的值，主要为了解释无参构造时为何初始化了一个容量为10的空数组。

private void ensureCapacityInternal(int minCapacity) {    //判断是不是成员变量DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果是就取你传入的minCapacity和DEFAULT_CAPACITY的最大值，你传的是什么？size+1=1，所以最大值就是DEFAULT_CAPACITY=10    //如果不是无参构造初始化的elementData，那么minCapacity就是指定的容量，是0它就是0，不会做特殊化    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    ensureExplicitCapacity(minCapacity);}

//我们已经得到了minCapacity为10了，那么此时elementData还是一个{}，它的length为0，此时就会进入grow方法private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // 10-0 = 10    if (minCapacity - elementData.length > 0)        grow(minCapacity);}

//这个方法我们又称为扩容 private void grow(int minCapacity) {     // 获取elementData的长度，现在还是0     int oldCapacity = elementData.length;     //0再怎么位运算也还是0     int newCapacity = oldCapacity + (oldCapacity >> 1);     //minCapacity为10，执行减数小于0，得到newCapacity=10     if (newCapacity - minCapacity < 0)         newCapacity = minCapacity;     if (newCapacity - MAX_ARRAY_SIZE > 0)         newCapacity = hugeCapacity(minCapacity);     // elementData就得到了一个长度为10的空数组了     elementData = Arrays.copyOf(elementData, newCapacity); }

add方法添加元素关键步骤：

1）首先通过size+1明确需要的容量

2）对DEFAULTCAPACITY_EMPTY_ELEMENTDATA进行特殊处理，初始容量为10

3）判断所需要的容量是否大于elementData数组可容纳的元素的数量，如果大于length，则表明位置不够了需要扩容

4）扩容时根据elementData的length属性扩容至原来的1.5倍，并不是根据你需要的容量来的，不要混淆了

5）扩容后将elementData按照新的长度拷贝新的数组并赋值给elementData，此时就得到了足够容量的数组

6）将需要添加的元素e放置在size+1的位置，并将size数量+1

添加元素除了可以在容器尾部添加元素之外，还可以在指定的下标位置添加元素，在添加的时候需要移动index之后的所有元素，如果index之后的元素特别多，性能会比较差。

public void add(int index, E element) {    //校验下标值，不能大于size，不能小于0，否则IndexOutOfBoundsException异常    rangeCheckForAdd(index); //保证有足够的容量    ensureCapacityInternal(size + 1);  // Increments modCount    //将index之后的元素统一向后移动一个位置，此时index的位置就空出来了    System.arraycopy(elementData, index, elementData, index + 1,                     size - index);    //将元素存放在index的位置    elementData[index] = element;    size++;}

添加元素还提供了addAll方法可以将集合添加到另外一个集合中，方法类似，大家可以自行查看源码。

在这里我们补充一个知识点System.arraycopy和Arrays.copyOf的区别：

Arrays.copyOf是jdk提供的工具类，它可以按照给定的源数组和长度复制指定长度的数组System.arraycopy是Java标准类库提供的工具类，用它复制数组比for循环要快很多。它需要提供的参数：源数组、从哪个位置开始复制的偏移量、目标数组、目标数组从哪个位置开始复制的偏移量、需要复制的元素个数。获取元素get

获取元素的方法比较简单，我们只需要从elementData的下标位置取出来返回即可，因数组只提供了根据下标获取元素，所以ArrayList获取元素也只能通过下标获取。

public E get(int index) {    //校验获取元素的下标位置是否合法，如果index>=size则IndexOutOfBoundsException    rangeCheck(index);    return elementData(index);}

remove删除元素方法也有很多重载方法，我们可以按照下标删除指定下标位置的元素，也可以按照元素删除容器中所有指定的元素，我们还可以删除某一段下标范围内的元素，最基础开发中最常用的是根据下标删除元素，这个方法也是我们理解其他重载方法的基础。我们接下来分析源码：

public E remove(int index) { //依然先校验传入的下标是否合法    rangeCheck(index); //这里对modCount进行+1，这是第二次出现，get方法没有    modCount++;    //获取下标位置的元素    E oldValue = elementData(index); //计算需要移动的元素，这里元素要删除，其实是将后面的元素向前移动把index位置的元素覆盖掉    int numMoved = size - index - 1;    if (numMoved > 0)        System.arraycopy(elementData, index+1, elementData, index,                         numMoved);    //把最后一个位置置为null，便于GC回收，且对size--    elementData[--size] = null; // clear to let GC do its work //返回删除的元素    return oldValue;}

看过remove方法我们要注意一点，如果在循环中删除元素，下标的位置要及时跟着变动喔。

遍历元素for

我们可以使用for循环遍历元素，也可以使用增强for循环和foreach遍历元素，或者使用迭代器遍历元素。增加for循环的底层其实也是迭代器，那我们就以迭代器为主学习ArrayList的遍历。

我们写一个遍历元素的示例：

public static void main(String[] args) {    ArrayList<String> list = new ArrayList<>(10);    list.add("Java");    list.add("Code");    //获取迭代器    Iterator<String> iterator = list.iterator();    //判断是否还有下一个元素，如果有，可以通过next方法获取    while (iterator.hasNext()){        System.out.println(iterator.next());    }}

调用ArrayList的iterator()方法，得到的是ArrayList的内部类对象Itr。

public Iterator<E> iterator() {    return new Itr();}

而hasNext()方法则就是判断指针是否移动到了最后一个元素之后的下标size的位置。

public boolean hasNext() {    return cursor != size;}

next()方法则是根据当前的指针下一个位置获取元素：

public E next() {    //校验modCount值是否被改变了    checkForComodification();    int i = cursor;    //i不能大于size    if (i >= size)        throw new NoSuchElementException();    Object[] elementData = ArrayList.this.elementData;    //如果i大于了elementData容器的容量，则抛出异常    if (i >= elementData.length)        throw new ConcurrentModificationException();    cursor = i + 1;    //返回下一个指针的元素    return (E) elementData[lastRet = i];}//校验modCount是否等于expectedModCount，不等于则抛出ConcurrentModificationExceptionfinal void checkForComodification() {    if (modCount != expectedModCount)        throw new ConcurrentModificationException();}

这个频繁出现的modCount是做什么的呢？那我们需要了解一个概念fail-fast快速失败。

快速失败fail-fast

在遍历集合的过程中，如果对集合中的元素做了增加、修改和删除操作，则会抛出异常ConcurrentModificationException，这就是快速失败。java.util包下的工具类都是fail-fast。

对应的就有另一个概念称为fail-save安全失败，在遍历集合时候，不是在原有的容器中遍历元素，而是先把原来的元素复制出来，在新的集合上遍历，原有容器中元素的增加、修改和删除并不会影响数据的遍历。java.util.concurrent包下的类都是fail-safe的。

我们看一个单线程下快速失败的例子：

public static void main(String[] args) {    ArrayList<String> list = new ArrayList<>(10);    list.add("a");    list.add("b");    list.add("c");    list.add("d");    Iterator<String> iterator = list.iterator();    while (iterator.hasNext()){        String item = iterator.next();        iterator.remove();        //随便删除一个元素        if (item.equals("a")){            //注意这里是list的删除方法，不是迭代器的删除方法            list.remove(0);        }    }}

运行结果：

Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901) at java.util.ArrayList$Itr.next(ArrayList.java:851) at com.study.test.code.girl.base.datastruct.ListTest.main(ListTest.java:22)

我们在分析ArrayList的增加和remove的方法时，都对modCount进行了修改，所以会报错。但是如果使用的是iterator的删除方法则不会报错，因为它做了处理，我们看源码：

public void remove() {    if (lastRet < 0)        throw new IllegalStateException();    checkForComodification();    try {        ArrayList.this.remove(lastRet);        cursor = lastRet;        lastRet = -1;        //这里修改了expectedModCount的值        expectedModCount = modCount;    } catch (IndexOutOfBoundsException ex) {        throw new ConcurrentModificationException();    }}

所以我们如果有必须要删除元素的场景，不要使用ArrayList的remove方法，而是要使用迭代器的remove方法来保证线程安全性，但是更好的是使用JUC包下的CopyOnWriteArrayList。

所以下一篇我们继续学习线程安全的集合CopyOnWriteArrayList。

我是勾勾，一直在努力的程序媛，感谢您的点赞、关注和转发！

我们下篇文章见！