前言

ArrayList是Java集合框架中比较常用的数据结构了。继承自AbstractList，实现了List接口。底层基于数组实现容量大小动态变化。一看就是一个比较重要的模块，所以我们今天就来学习一下ArrayList相关知识。

ArrayList的数据结构和作用

ArrayList数据结构是数组，用来装载数据。

相对于LinkedList，查询效率高，因为底层是数组，分配的是连续的内存空间，CPU在读取时可以缓存连续的内存空间，大幅度降低读取的性能开销；增删效率低，相对于Vector来说是线程不安全。

虽然ArrayList是线程不安全的，但在我们实际的应用过程中，一般都是用来查询，涉及到增删的操作比较少，如果涉及到的增删操作比较频繁的场景，我们可以选择LinkedList，如果想保证线程安全，可以使用Vector、CopyOrWriteArray。

如何实现存放任意数量的对象

ArrayList构造器有无参构造和有参构造。在有参构造器中，ArrayList可以通过构造方法在初始化的时候进行指定底层数组的大小。但是我们在使用有参构造时，会不会初始化数组大小呢？我们先来看一下代码：

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 static void main(String[] args){
    //此处使用有参构造，大小为10
    ArrayList<String> arrayList = new ArrayList<>(10);
    System.out.println("size:" + arrayList);
    arrayList.set(1, "A");
}

 

看到这里是不是已经懵圈了？不要慌，我们慢慢来分析。我们的参数是 initialCapacity，这里是将参数基于 elementData 设置的，并不是直接设置的数组大小（值得注意的是，ensureCapacity();方法也是这种原理）。我们也可以理解为这个数组现在理论上最大可以装10个数据，但是他现在还是空的。

在无参构造器中，初始化出一个默认空的数组，数组容量为 0，当我们调用add();方法是，默认分配【DEFAULT_CAPACITY = 10】的初始容量。下面会具体介绍新增过程，此处不再赘述。

/**
 * 数组默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 用于默认大小的空实例的共享空数组实例。 
 * 与 EMPTY_ELEMENTDATA 区分开来，以了解何时膨胀多少添加第一个元素。
  */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 构造一个初始空列表。
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

但是，对于无参构造和有参构造，数组都是有长度限制的，ArrayList是通过什么方式去实现可以存放任意数量的对象，长度没有限制的呢？不要慌，原来这个地方也是用到了数组的扩容。

数组的扩容

当前我们有一个初始容器为10的数组，且每个位置已经插满数据，但是现在又要新增一条数据，这个时候当前数组已经不能满足我们的要求了，那我们就需要进行扩容；

 

然后我们就需要进行扩容，扩大到原来的1.5倍，即【10 + 10 / 2】；

 

最后将原数组的数据原封不动地移动到新数组，再返回新数组的地址，这样ArrayList中数据就是新的数组了。

 

接下来，我们就看一下源码中的具体实现吧

//扩容前置判断
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    //minCapacity: 插入数据后容器大小或者默认容器大小
    //当minCapacity比当前数组大时，说明需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//扩容具体过程
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //此处java 8采用了位运算，提升效率
    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);
}

ArrayList的的新增

在ArrayList中，新增有三个方法分别是以下三种：

//1\. 将指定的元素附加到此列表的末尾
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//2\. 在此指定位置插入指定元素列表。
public void add(int index, E element) {
    //判断指定参数是否超过范围
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

//3\. 将指定集合中的所有元素追加到末尾这个列表，
//   按照它们返回的顺序指定集合的迭代器。
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(); 方法来校验数组长度，如果长度不够，就进行扩容，前面我们已经了解过。 对于指定位置新增时，我们在校验完成之后通过调用 arraycopy(); 方法来实现数组的复制。下面我们就来了解一下指定位置插入的过程。

当前我们有一个长度为10，还有一个空位的数组；

 

现在我们需要插入一个【a】，目标位置是【5】，则先复制一个数组，指定位置之前的数据不变，从【5】开始把后面的数据从【5+1】的位置开始复制，新数组空出位置【5】；

 

上一步我们已经把【5】这个位置空出来了，然后将数据【a】插入空位，这样就完成了指定位置插入的操作了。

 

由上可知，ArrayList在新增的需要把数据复制一份，这个操作如果是针对大数据量List，再加上扩容的操作，那效率就慢了。

ArrayList的删除

话不多说，我们先来看一下代码：

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

由代码可知，如果是删除末位，则直接删除就完成了操作；如果是将中间数据删除，则此过程中也是类似于插入操作，将数组进行了复制，调用arraycopy();方法。下面我们就来了解一下指定位置删除的过程。

当前我们有一个长度为10；

 

现在我们需要删除目标位置为【5】的数据，则先复制一个数组，指定位置之前的数据不变，从【5+1】之后的数据进行复制到新数组；

 

得到新的数组，就是删除了指定位置【5】数据的数组了。

 

同理，ArrayList的删除和新增一样效率比较低。对于数据量大的数组需要复制和移动的位置就比较大了。

ArrayList适合做队列吗

一般的队列是先进先出队列（FIFO），从尾部出入，头部删除。

对于数组是十分适合做队列的，比如 ArrayBlockingQueue内部的实现就是通过一个定长数组来实现一个环形定长队列，使用两个偏移量来标记数组的读位置和写位置，如果超过长度就折回到数组开头。但是前提必须是一个定长的数组。

因为在ArrayList中，底层虽然是数组，但是数组长度是不确定的。这样我们就需要进行大量的增加和删除操作，就算是指定位置的删除和新增，它也是需要经过数组复制，这样的话，会比较消耗性能。

因此，定长数组适合做队列，ArrayList不适合做队列。