前话：本次解析基于JDK1.8.0，SDK26。

一、数据结构

ArrayList 是Java提供的一个存储数据的工具类，其内部使用一个Object[] （数组）来存储我们的数据。后续的添加、删除、查询等操作实际上都是对数组进行操作。

transient Object[]elementData; //transient是序列化和反序列化的知识点

二、构造方法

使用ArrayList的前提就是定义ArrayList对象，先来看一下ArrayList类中的几个重要的成员变量：

//实际存储数据的数组
transient Object[] elementData;
//数组中实际数据的个数，注意并不是数组的长度（这块要特别注意，后边会用到）。默认为0
private int size;
//数组的默认容量或长度
private static final int DEFAULT_CAPACITY = 10;
//静态的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//静态的默认的空数组，在后边的构造函数会看到和EMPTY_ELEMENTDATA的不同
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

1、首先分析最简单的一种定义方式：

ArrayList list = new ArrayList();
其内部实现：

public ArrayList() {
        //直接把默认的静态的空数组赋值给elementData
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2、带有初始化容量的构造方法：

ArrayList list = new ArrayList(20);
其内部实现：

//指定创建一个长度为initialCapacity的数组
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //要求的长度>0，则直接创建一个该长度的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //赋值为空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //如果长度小于零，直接抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

三、add方法

对add方法的总结就是：当向ArrayList中添加一个元素时，先判断当前数组中是否还有剩余空间，如果有剩余空间则直接将该元素添加至数组中元素的末尾，如果没有剩余空间，先将数组扩容（扩容的算法简单说就是将当前的数组容量扩大1.5倍），再将元素添加至数组中元素的末尾。

public boolean add(E e) {
        //每次add一个元素之前，先判断size+1之后数组是否还有空余空间,
        //如果没有剩余空间，对elementData进行扩容，如果有剩余空间则直接进行下一步。
        // 注意：size并不是数组的长度，而是数组中实际存储对象的长度
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //注意size++，每次添加一个素，size增加1.
        elementData[size++] = e;
        return true;
    }

来重点看下ensureCapacityInternal方法：

private void ensureCapacityInternal(int minCapacity) {
        // elementData就是实际存储数据的数据结构：Object[]
        // 如果当前数组为空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //DEFAULT_CAPACITY 为 10，是默认数组的长度
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //继续调用方法
        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //等价于：minCapacity > elementData.length
        if (minCapacity - elementData.length > 0)
            // 第一次add的时候，elementData.length=0，数组为空数组，所以肯定要把当前数组扩容
            // 如果是第N次add，此时minCapacity > elementData.length,也就是数组需要更大的空间
            //所以也需要扩容。
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        //当前数组的长度(扩容之前的长度)
        int oldCapacity = elementData.length;
        //oldCapacity >> 1：位运算符，相当于oldCapacity/2,
        //新的容量等于：原来的容量 + 原来的容量的一半
        //所以每次扩容都是将数组的长度扩大为原来的1.5倍。
        int newCapacity = oldCapacity + (oldCapacity >> 1);

        //如果新的扩大1.5倍后，数组的空间仍然不够
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果需要的空间比 MAX_ARRAY_SIZE 还要大，
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //hugeCapacity:申请最大的空间
            newCapacity = hugeCapacity(minCapacity);

        //最后根据需要的空间和原来的数组中的数据，将elementData重新赋值为拥有更大空间的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

三、get方法

根据元素的坐标获取元素，先判断index是否合法，如果合法直接返回元素。

public E get(int index) {
        if (index >= size)
            //size是当前数组中元素的个数，并不是数组的长度，如果查询的index超过size，抛异常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        
        //直接返回index对应的元素
        return (E) elementData[index];
    }

四、set方法

set(int index, E element）方法是将原数组中的下标为index的元素替换为新的数据。

public E set(int index, E element) {
        if (index >= size)
            //老规矩，还是先判断size的长度
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        
        //将老的元素替换为新的元素，并把老元素返回
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

五、remove方法

public E remove(int index) {
        if (index >= size)
            //老规矩，先判断size合法
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        //获取要删除的元素
        E oldValue = (E) elementData[index];

        //  假设一个数组有3个元素，现在删除第二个元素（下标为1），numMoved= 3-1-1=1
        //numMoved表示在数组中删除一个元素后，需要将该元素后边的元素全部向前挪一位，那么一共要挪动的元素的个数即为numMoved
        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;
    }

六、indexOf 方法

indexOf 可以接受为Null的数据，如果数据为null，则返回整个数组中第一个为null的元素的下标。如果不为null，则遍历整个数组中的元素，找到相等的元素并返回下标。
需要注意的是：indexOf(E e) 方法的平均时间复杂度为O(n)，因为它内部是一个循环，所以在使用indexOf方法的时候，尽量不要再一个for循环中再使用indexOf，因为这样的时间复杂度为O(n*n)，在内存充足的情况下可以考虑使用“空间换时间”的方法，使用HashSet或者HashMap代替ArrayList。

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

七、size()方法

public int size() {
        //前边已经提到多次，ArrayList的size方法返回的是数组中元素的个数，不是整个数组的长度。
        return size;
    }

总结

其实ArrayList内部还有几个操作方法，但是总体的思路都是针对于数组进行操作，另外，在写代码的时候一定要注意indexOf的使用，这句代码的时间复杂度为O(n)。

安卓ArrayList源码解析