ArrayList源码

前置知识
源码解读

前置知识

Serializeable标记性接口

用于标记实现了Serializeable接口的类是可序列化的，这个接口没用任何字段和方法，仅用于标记。

序列化

什么是序列化？

将对象的状态信息转换为可以存储或传输形式的过程（例如将对象转为String，可以用与前后端交互）

序列化目的？

已某种存储形式自定义对象持久化
将对象从一个地方传递到另一个地方（例如前后端传递）
什么是反序列化？
将字节序列转为对象

Cloneable标记性接口

标志实现了这个接口的实例是可以被克隆的，如果对没用实现Cloneable接口的实例上调用对象的克隆方法就会导致异常CloneNotSupportedException被爬出

克隆的前提

实现了Cloneable接口
重写了clone方法

RandomAccess标记接口

标志实现了这个接口的实例支持快速随机访问

在遍历集合的时候可以判断，是否实现RandomAccess接口，是则使用随机遍历，否则使用顺序遍历

if(list instanceof RandomAccess){
    // 随机访问
}else{
    // 顺序访问
}

源码解读

_public void _add(_int _index)

public boolean add(E e){
    ensureCapacityInternal(size + 1); // 确保扩容后集合长度最小为扩容前长度+1
    elementData[size++] = e;    // 扩容后，在集合末尾增加e
    return true;  // 前面方法不报错的情况下，总是返回true
}

private void ensureCapacityInternal(int minCapacity) {
    // calculateCapacity计算完成扩容操作后，list需要多大的空间
    // 参数：elementData-存储集合数据的数组 minCapacity-本次扩容操作后，list的最小空间长度
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 取最大值，Max(10,minCapacity)，扩容后集合长度最小为10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 如果集合元素长度为0，则直接返回minCapacity，也就是扩容前集合长度加上扩容数据数组的长度
    return minCapacity;
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;    // 扩容前集合长度
    // 新空间大小，为扩容前集合长度的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);    // >> 右移几位，则除以2的几次幂
    // 取minCapacity和newCapacity的最大值(也就是取DEFAULT_CAPACITY(10),扩容前集合长度+1（可以忽略，原集合长度1.5倍总是大于这个值），扩容前集合长度的1.5被中的最大值)
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果完成扩容操作后需要的长度不能超出MAX_ARRAY_SIZE
        newCapacity = hugeCapacity(minCapacity);
    // Arrays.copyOf(elementData, newCapacity)返回一个长度为newCapacity长度的数组，其中拷贝了扩容前的集合数据
    elementData = Arrays.copyOf(elementData, newCapacity);
}

_public void _add(_int _index, E element)

public void add(int index, E element) {
    // 检查下标是否越界
    rangeCheckForAdd(index);

    // 和add(E e)方法一样逻辑，确保扩容后集合大小足够
    ensureCapacityInternal(size + 1); 
    // 将elementData[index,size - index](index之后所有元素)范围内的元素后移一位，index下标位置留给E element插入
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    // 集合实际长度++
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); // 抛出索引越界异常
}

_public boolean _addAll(Collection<? _extends _E> c)

// 存放集合元素的数组
Object[] elementata;
// 集合的长度
private int size;
private static final int DEFAULT_CAPACITY = 10;

public boolean addAll(Collection<? extens E> c){
    // 将list转为数组
    Object[] a = c.toArray();
    // 追加数组的长度
    int numNew = a.length;

    // 确保扩容后集合长度足够(扩容后集合长度最小为 size（原长度） + numNew(本次增加的长度))
    ensureCapacityInternal(size + numNew);

    // 真正的拷贝操作， a-需要add的数组 0-从a开始拷贝的下表    elementData-被add的集合    size-aelementData的size下标追加a数组，也就是追加到集合末尾
    // numNew-需要追加a数组中元素的个数
    // System.arrayCopy为其他语言的方法（c或c++）
    System.arraycopy(a, 0, elementData, size, numNew);

    // 增加集合实际元素个数
    size += numNew;

    // 追加的list长度不为0且前面没有报错，则追加成功，返回true，否则返回false
    return numNew != 0;
}

private void ensureCapacityInternal(int minCapacity) {
    // calculateCapacity计算完成扩容操作后，list需要多大的空间
    // 参数：elementData-存储集合数据的数组 minCapacity-本次扩容操作后，list的最小空间长度
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 取最大值，Max(10,minCapacity)，扩容后集合长度最小为10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 如果集合元素长度为0，则直接返回minCapacity，也就是扩容前集合长度加上扩容数据数组的长度
    return 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);    // >> 右移几位，则除以2的几次幂
    // 取minCapacity和newCapacity的最大值(也就是取DEFAULT_CAPACITY(10),size + numNew，扩容前集合长度的1.5被中的最大值)
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果完成扩容操作后需要的长度不能超出MAX_ARRAY_SIZE
        newCapacity = hugeCapacity(minCapacity);
    // Arrays.copyOf(elementData, newCapacity)返回一个长度为newCapacity长度的数组，其中拷贝了扩容前的集合数据
    elementData = Arrays.copyOf(elementData, newCapacity);
}

_public boolean _addAll(_int _index, Collection<? _extends _E> c)

public boolean addAll(int index, Collection<? extends E> c) {
    // 检查下标是否越界
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    // 确保扩容后长度足够
    ensureCapacityInternal(size + numNew);


    int numMoved = size - index; // 要移动的元素个数（集合元素长度-要存放的下标）
    if (numMoved > 0)    // 如果需要移动的元素个数大于0，则是在集合非末尾位置添加，否则在末尾添加
        // 在集合非末尾位置追加,则将从index到(index+numNew)范围下标元素向后移动至（index+numNew） 到 （index+numNew + numNew），
        // 留出空间给数组插入
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);    

    size += numNew;
    return numNew != 0;
}

_public _E set(_int _index, E element)

public E set(int index, E element) {
    // 检查下标是否越界
    rangeCheck(index);

    E oldValue = elementData(index);
    // 设置指定下标为新值
    elementData[index] = element;
    // 返回被修改下标元素的值
    return oldValue;
}

public E get(int index)

public E get(int index) {
    // 检查下标是否越界
    rangeCheck(index);

    // 返回集合中指定下标元素
    return elementData(index);
}

E elementData(int index) {
    // object强转E类型
    return (E) elementData[index];
}

public boolean remove(Object o)

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {    // 找到第一个为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++;     // 修改次数+1
    int numMoved = size - index - 1;    // 要移动的元素个数
    if (numMoved > 0)    // 在非末尾位置remove，移动后面的元素到index，覆盖掉，那么末尾就会出现一个null
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work 主动设置为null，让GC回收掉
}

public Iterator iterator()

// 返回迭代器
public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // 默认光标，0
    int lastRet = -1; // 最后一次操作返回的元素下标; -1则为还没有返回过
    int expectedModCount = modCount;    // 将集合实际修改次数赋值给预期修改次数

    Itr() {}

    public boolean hasNext() {
        // 如果当前光标不在最后一个，那么后面还有元素了
        return cursor != size;
    }


    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)    // 如果当前光标位置大于集合长度，那么后面就没有元素了，抛出异常
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData; // 每次调用next()，获取集合最新数据
        if (i >= elementData.length)
            throw new ConcurrentModificationException();    // 抛出并发修改异常
        cursor = i + 1;    // 执行next()后，光标向右移动一位
        return (E) elementData[lastRet = i];    // 记录 最后一次返回的元素下标
    }


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

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

public void trimToSize()

public void trimToSize() {
    modCount++;    // 修改次数+1
    if (size < elementData.length) {    // 如果实际元素长度比集合容量小，则进行trim操作
        elementData = (size == 0)    
          ? EMPTY_ELEMENTDATA    // 如果实际元素长度为0，返回空数组
          : Arrays.copyOf(elementData, size);    // 如果不为0，则返回一个长度为元素实际长度的数组，包含elementData[0]至elementData[size]
    }
}

public void iterator.remove()

public void remove() {
    if (lastRet < 0)    // 如果一次next()还没调用，则抛出异常
        throw new IllegalStateException();
    checkForComodification();

    try {
        // 迭代器调用remove方法，实际上还是调用集合的remove方法来删除元素
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        // 更新预期修改次数，不会抛出并发修改异常
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

public void clear()

public void clear() {
    modCount++;
    for (int i = 0; i < size; i++)
        // 将数组的每一个位置都设置为null，让垃圾回收器回收，不占内存空间
        elementData[i] = null;
    size = 0;
}

public boolean contains(Object o)

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o)

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)

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

public boolean isEmpty()

public boolean isEmpty() {
    return size == 0;
}