1、概述

一上来，先来看看源码中的这一段注释，我们可以从中提取到一些关键信息：

/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)
 */

​ 从这段注释中，我们可以得知 ArrayList 是一个动态数组，实现了 List 接口以及 list相关的所有方法，它允许所有元素的插入，包括 null。另外，ArrayList 和 Vector 除了线程不同步之外，大致相等。

2、属性

// 默认容量的大小
private static final int DEFAULT_CAPACITY = 10;

// 当ArrayList的构造方法中显示指出ArrayList的数组长度为0时，类内部将EMPTY_ELEMENTDATA这个空对象数组赋给elemetData数组。
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认的空数组常量 当ArrayList的构造方法中没有显示指出ArrayList的数组长度时，类内部使用默认缺省时对象数组为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存放元素的数组，从这可以发现 ArrayList 的底层实现就是一个 Object数组
transient Object[] elementData;

// 数组中包含的元素个数 默认时为0个元素。
private int size;

// 数组的最大上限
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

​ ArrayList 的属性非常少，就只有这些。其中最重要的莫过于 elementData 了，ArrayList所有的方法都是建立在 elementData 之上。接下来，我们就来看一下一些主要的方法吧。

3、方法

1、构造方法

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) { // 初始容量大于0
        this.elementData = new Object[initialCapacity]; // 初始化元素数组
    } else if (initialCapacity == 0) { // 初始容量为0
        this.elementData = EMPTY_ELEMENTDATA; // 为空对象数组
    } else { // 初始容量小于0，抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}


public ArrayList() {
    // 无参构造函数，设置元素数组为空
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) { // 集合参数构造函数
    elementData = c.toArray(); // 转化为数组
    if ((size = elementData.length) != 0) { // 参数为非空集合
        if (elementData.getClass() != Object[].class) // 是否成功转化为Object类型数组
            elementData = Arrays.copyOf(elementData, size, Object[].class); // 不为Object数组的话就进行复制
    } else { // 集合大小为空，则设置元素数组为空
        this.elementData = EMPTY_ELEMENTDATA;
    }

​ 从构造方法中我们可以看见，默认情况下，elementData 是一个大小为 0 的空数组，当我们指定了初始大小的时候，elementData 的初始大小就变成了我们所指定的初始大小了。

• Collection<? extends E>类型构造方法
  • 将参数中的集合转化为数组赋给elementData
  • 参数集合是否是空。通过比较size与第一步中的数组长度的大小
  • 如果参数集合为空，则设置元素数组为空，即将EMPTY_ELEMENTDATA赋给elementData
  • 如果参数集合不为空，接下来判断是否成功将参数集合转化为Object类型的数组，如果转化成Object类型的数组成功，则将数组进行复制，转化为Object类型的数组

2、get 方法

public E get(int index) {
    rangeCheck(index); // 检验索引是否合法

    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
    return (E) elementData[index];
}

​ 因为 ArrayList 是采用数组结构来存储的，所以它的 get 方法非常简单，先是判断一下有没有越界，之后就可以直接通过数组下标来获取元素了，所以 get 的时间复杂度是 O(1)。

3、add 方法

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //调用一个 native 的复制方法，把 index 位置开始的元素都往后挪一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 判断元素数组是否为空数组
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 取较大值
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 结构性修改加 1

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

​ ArrayList 的 add 方法也很好理解，在插入元素之前，它会先检查是否需要扩容，然后再把元素添加到数组中最后一个元素的后面。在ensureCapacityInternal 方法中，我们可以看见，如果当 elementData 为空数组时，它会使用默认的大小去扩容。所以说，通过无参构造方法来创建 ArrayList 时，它的大小其实是为 0 的，只有在使用到的时候，才会通过 grow 方法去创建一个大小为 10 的数组。

​ 第一个 add 方法的复杂度为 O(1)，虽然有时候会涉及到扩容的操作，但是扩容的次数是非常少的，所以这一部分的时间可以忽略不计。如果使用的是带指定下标的 add方法，则复杂度为 O(n)，因为涉及到对数组中元素的移动，这一操作是非常耗时的。

4、set 方法

public E set(int index, E element) {
    rangeCheck(index); // 检验索引是否合法
	// 旧值
    E oldValue = elementData(index);
    // 赋新值
    elementData[index] = element; 
    // 返回旧值
    return oldValue;
}

• set 方法的作用是把下标为 index 的元素替换成 element，跟 get 非常类似，所以就不在赘述了，时间复杂度度为 O(1)。

5、remove 方法

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);
    // 赋值为空，有利于进行GC
    elementData[--size] = null; // clear to let GC do its work
	// 返回旧值
    return oldValue;
}

• remove 方法与 add 带指定下标的方法非常类似，也是调用系统的 arraycopy 方法来移动元素，时间复杂度为 O(n)。

6、grow 方法

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍
    if (newCapacity - minCapacity < 0) // 新容量小于参数指定容量，修改新容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量大于最大容量
        newCapacity = hugeCapacity(minCapacity); // 指定新容量
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity); // 拷贝扩容
}

​ grow 方法是在数组进行扩容的时候用到的，从中我们可以看见，ArrayList 每次扩容都是扩 1.5 倍，然后调用 Arrays 类的 copyOf 方法，把元素重新拷贝到一个新的数组中去。

7、size 方法

public int size() {
    return size;
}

• size 方法非常简单，它是直接返回 size 的值，也就是返回数组中元素的个数，时间复杂度为 O(1)。这里要注意一下，返回的并不是数组的实际大小

8、indexOf 方法和 lastIndexOf

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


public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

​ indexOf 方法的作用是返回第一个等于给定元素的值的下标。它是通过遍历比较数组中每个元素的值来查找的，所以它的时间复杂度是 O(n)。lastIndexOf 的原理跟 indexOf 一样，而它仅仅是从后往前找起罢了。

4、Vector

​ 因为很多方法都跟 ArrayList 一样，只是多加了个 synchronized 来保证线程安全罢了。如果照着 ArrayList 的方式再将一次就显得没意思了，所以只把 Vector 与 ArrayList的不同点提一下就可以了。

• Vector 比 ArrayList 多了一个属性：

protected int capacityIncrement;

• 这个属性是在扩容的时候用到的，它表示每次扩容只扩 capacityIncrement 个空间就足够了。该属性可以通过构造方法给它赋值。先来看一下构造方法：

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

• 从构造方法中，我们可以看出 Vector 的默认大小也是 10，而且它在初始化的时候就已经创建了数组了，这点跟 ArrayList 不一样。再来看一下 grow 方法：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

​ 从 grow 方法中我们可以发现，newCapacity 默认情况下是两倍的 oldCapacity，而当指定了 capacityIncrement 的值之后，newCapacity 变成了oldCapacity+capacityIncrement。

5、总结

1. ArrayList 创建时的大小为 0；当加入第一个元素时，进行第一次扩容时，默认容量大小为 10。
2. ArrayList 每次扩容都以当前数组大小的 1.5 倍去扩容。
3. Vector 创建时的默认大小为 10。
4. Vector 每次扩容都以当前数组大小的 2 倍去扩容。当指定了 capacityIncrement 之后，每次扩容仅在原先基础上增加 capacityIncrement 个单位空间。
5. ArrayList 和 Vector 的 add、get、size 方法的复杂度都为 O(1)，remove 方法的复杂度为 O(n)。
6. ArrayList 是非线程安全的，Vector 是线程安全的。
7. ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，类似于C语言中的动态申请内存，动态增长内存。
8. ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。
9. ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。
10. 每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。