一、什么是ArrayList

ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

• ArrayList 继承了 AbstractList ，并实现了 List 接口。
• ArrayList类实现了java.io.Serializable接口，即采用了Java默认的序列化机制
• ArrayList类实现了RandomAccess接口，支持随机访问（当一个List拥有快速访问功能时，其遍历方法采用for循环最快速。而没有快速访问功能的List，遍历的时候采用Iterator迭代器最快速）

一、ArrayList的创建

1、ArrayList的主要成员变量

// 当ArrayList的构造方法中没有显示指出ArrayList的数组长度时，类内部使用默认缺省时对象数组的容量大小，为10。
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中存放的元素的个数，默认时为0个元素。
private int size;

//ArrayList中的对象数组的最大数组容量为Integer.MAX_VALUE – 8。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

//ArrayList的底层数据结构，只是一个对象数组，用于存放实际元素，并且被标记为transient，也就意味着在序列化的时候此字段是不会被序列化的。
transient Object[] elementData;

2、ArrayList继承了Serializable，但底层数据结构却使用了transient使得数组不序列化，为什么？

transient用来表示一个域不是该对象序行化的一部分，当一个对象被序行化的时候，transient修饰的变量的值是不包括在序行化的表示中的。但是ArrayList又是可序行化的类，elementData是ArrayList具体存放元素的成员，用transient来修饰elementData，岂不是反序列化后的ArrayList丢失了对象数组？

发现源码下边有两个方法，ArrayList是自己实现了序列化和反序列化的方法。

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
    
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
    
        throw new ConcurrentModificationException();
    }
}

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
    
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
    
            a[i] = s.readObject();
        }
    }
}

首先我们要了解ArrayList的机制，即他是一个可以动态拓展的数组，但因为数组的长度是固定的，所以当ArrayList存满的时候再add元素进来就需要进行扩容，所以ArrayList的实际长度并不是数组的长度而是size这个变量存储的。
那么答案就显而易见了，因为ArrayList扩容后通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

3、ArrayList三种构造器

①int构造器

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

• 如果initialCapacity大于0，则创建一个大小为initialCapacity的对象数组赋给elementData。
• 如果initialCapacity等于0，则将EMPTY_ELEMENTDATA赋给elementData。
• 如果initialCapacity小于0，抛出异常（非法的容量）。

②无参构造器

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

对于无参构造方法，将成员变量elementData的值设为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

③传入一个集合

public ArrayList(Collection<? extends E> c) {
    
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
    
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
    
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

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

三、ArrayList的方法

1、add()

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!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

不难发现在插入元素之前都要进行ensureCapacityInternal(size + 1);操作
主要目的是确保ArrayList的容量能存的下插入的这个元素，（不能存下的话就扩容）

ArrayList扩容机制

minCapacity可以理解为数组至少需要的长度

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    
	//判断元素数组是不是空数组，即是不是刚通过空参构造器构造的数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
    	//是的话返回数组的初始默认长度(10)和要插入的位置的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //如果不是初始化的空数组，那么
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    
	//calculateCapacity主要目的是防止当数组为空数组时，如果扩容数组长度为minCapacity为1导致后续无法扩容，或扩容太慢。
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    
    modCount++;
	//如果至少需要的长度比数组目前的长度长的话就执行扩容操作
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    
    //记录目前数组长度
    int oldCapacity = elementData.length;
    //扩容数组长度为当前长度的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果扩容后的数组长度比至少需要的长度短的话就把扩容后的数组长度设为minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //判断扩容后的数组长度是否比定义的最长的长度还长
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //扩容数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    
	//如果数组至少需要的长度超出int数据范围，那么报内存溢出异常
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
    	//如果需要的数组长度比最大数组长度大且没有超出int的范围那么使用 Integer.MAX_VALUE
        Integer.MAX_VALUE :
        //否则使用MAX_ARRAY_SIZE
        MAX_ARRAY_SIZE;
}

第一步：calculateCapacity(elementData, minCapacity)
将对象数组和数组至少需要的长度传入方法中，目的是防止当数组为空数组时，后续操作扩容数组长度为minCapacity为1导致后续扩容太慢。

第二步：private void ensureExplicitCapacity(int minCapacity)
如果至少需要的长度（minCapacity）比对象数组长度小，那么不需要进行扩容，否则进入扩容操作。

第三步：扩容数组grow(int minCapacity)
预期将数组扩容为原数组长度的1.5倍，若扩容后的长度仍小于minCapacity，那么将扩容后的数组长度设为minCapacity。
判断预期扩容的长度是否比允许的最大值大
最后就是执行扩容操作了

四、ArrayList的优缺点

1、ArrayList的优点

• ArrayList在不需要扩容的情况下顺序添加一个元素非常方便，只是往数组里面添加了一个元素而已。
• 根据下标遍历元素，效率高。
• 可以自动扩容，默认为每次扩容为原来的1.5倍。

2、ArrayList的缺点

• 插入和删除元素的效率不高。
• 根据元素值查找元素需要遍历整个元素数组，效率不高。
• 线程不安全。