List可以说是我们用的最多的数据结构之一了，了解其内部实现原理，是非常重要的。本文主要讲从源码的角度解读Java中ArrayList的数据结构。

一、接口继承关系

ArrayList的继承关系如下。AaaryList主要实现了List接口，同时标记为可以序列化Serializable、可复制CloneAble、支持随机访问RandomAccess。

二、数据结构

ArrayList的底层就是一个数组，使用泛型确定数组中存储的数据类型。
Java中数组的长度一般是固定的，但是ArrayList的长度确是不确定的。为什么呢？
因为ArrayList底层的数组会随着数据的增长而扩容，数组的扩容就是建立一个新的容量大的数组，然后把旧数组上面的数据复制进新数组。
因为是数组，所以支持随机访问，且有序。

三、创建ArrayList(构造函数解析)

ArrayList有三个构造函数，如下,分别是无参构造，参数为数字的构造函数和参数为集合的构造函数。

ArrayList<Object> list1 = new ArrayList<>();
ArrayList<Object> list2 = new ArrayList<>(1);
ArrayList<Object> list3 = new ArrayList<>(list2);

3.1无参构造

无参构造很简单，给elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，

elementData是一个对象数字，用来存放实际数据

注意elementData使用transient修饰。表明在采用Java默认的序列化机制的时候，被该关键字修饰的属性不会被序列化。而ArrayList类实现了java.io.Serializable接口，即采用了Java默认的序列化机制。但是elementData在网络传输的时候不序列化肯定是不行的，翻看源码会发现ArrayList自己实现了序列化和反序列化的方法。

而DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个静态的final空数组。

3.2 ArrayList(int initialCapacity)

ArrayList可以指定一个int作为参数，这个参数可以指定底层数组的初始化容量。代码很简单，如果大于0，以这个数字初始化数组，等于零，给数组赋一个空的数组，小于零，抛出异常。

3.3 ArrayList(Collection<? extends E> c)

这个方法逻辑并不复杂，直接将集合对象转换为Object数组，再赋值给了elementData属性。注意注释上面声明了可能抛出NullPointerException，看源码会发现当我们传递进来的元素是null值的时候，会在c.toArray()的时候抛出NPE。

四、为集合添加元素

4.1 添加到指定.位置add(int index, E element)

在添加元素时，会先通过ensureCapacityInternal判断是否有足够的空间给新的元素，需要的空间为当前的元素数量+1。

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

ensureCapacityInternal方法首先会确认容量是否够用，如果不够，则进行扩容。注意ArrayList的扩容时机和HashMap有区别，ArrayList只有底层数组已满，不能放下即将存入的对象才会扩容，HashMap的扩容和加载因子有关系，默认情况下，不是容器满了才扩容。
以下方法是，具体的扩容逻辑，首先是calculateCapacity方法，计算容量，如果为空，则返回默认容量10或者当前需要的容量。
ensureExplicitCapacity方法计算底层的数组容量是否满足所需要的容量，如果不能，则需要扩容。
grow是实现扩容的方法，新的数组是老数组的1.5背，把老数组的数据复制到新数组。

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

   private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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);
    }

2.2 添加到指定位置add(int index, E element)

这个订单和add方法相比，多了一个index范围判断，和数组后移，其他和add方法差不多。

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

2.3 添加所有addAll(Collection<? extends E> c)

addAll方法和add方法相比，因为是一次加入多个元素，所以ensureCapacityInternal的参数不一样，赋值方式使用System.arraycopy进行赋值。

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

五、删除元素

5.1 删除指定索引元素 E remove(int index)

删除元素时，先判断下标的合法性，然后得到需要删除的数据，之后通过数组复制的方法，吧删除位置的元素往前移动。

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

3.2 删除指定值的元素 remove(Object o)

remove(Object o)需要遍历数组，找到第一个元素，删除，和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++)
                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
    }

六、获取元素

获取元素的方法和简单，判断下标正确性，然后直接返回数组对应的下标序号就行了。

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

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

七、遍历元素 iterator()

关于数组的遍历，是基于一个内部类的迭代器，什么是迭代器，建议参考设计模式之迭代器模式。

public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

八、总结

1.ArrayList的底层是数组，没有指定默认值，默认是空，在新增数据时，扩容为10或者所需的数量，当数组满了之后，继续添加元素时，会扩容到原来的1.5倍。

2.ArrayList保存了一个modCount属性，修改集合的操作都会让其自增。目的是，如果在遍历的时候modCount被修改，则会抛出异常。

3.ArrayList内部还维护了一个size属性，它是用来记录数组中的实际元素个数。

size,modCount，elementData这些成员变量，都注定了ArrayList线程不安全。

4.ArrayList实现了Iterator接口，这表明遍历ArrayList使用普通for循环比使用foreach更快。