ArrayList源码

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    //默认的初始容量
    private static final int DEFAULT_CAPACITY = 10;

    //用于空实列共享的空数组
     private static final Object[] EMPTY_ELEMENTDATA = {};

     //用于默认大小的空实例的共享空数组实例。我们将其与空元素数据区分开来，
     //以了解添加第一个元素时要膨胀多少。
     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

     transient Object[] elementData;

    //元素的数量
     private int size;  

}

构造方法

ArrayList提供三种构造方法

第一种接收一个initialCapacity
- 如果传入initialCapacity大于0则会根据initialCapacity的大小创建一个Object数组
- 如果等于0，则会把成员变量中的EMPTY_ELEMENTDATA空数组实例赋值给elementData
- 如果少于0，则会抛出IllegalArgumentException异常
第二种无参的构造方法，创建默认大小的空实例的共享空数组实例

第三种接收一个被泛型E继承的数据的容器，它把接收到容器生成一个Object数组，只要容器存储的元素数量不等于0，会根据容器c是否为ArrayList类的实例，如果是就直接进行赋值，不是就调用ArrayList的拷贝方法Arrays.copyOf。如果容器c存储的元素数量为0，则直接赋值空实列共享的空数组。

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

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

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

Size方法

返回元素数量
1
2
3
public int size() {
return size;
}
isEmpty方法

判断是为空

1
2
3

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

contains方法

是否包含o元素

1
2
3

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

indexOf方法

返回元素o的下标

1
2
3

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

indexOfRange方法

Range(范围)：在(stact-end)范围中寻找元素o，如果存在则返回它的下标

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

Get方法

返回下标index处的元素

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

Set方法

保留index处的旧元素，把新的element赋值覆盖index处，返回旧元素

    public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

Add方法

ArrayList扩容时机，是当数组满的时候

插入index处时，它调用 System.arraycopy对数组下标index到size之间的元素用拷贝的方式往后移动一位，在对index处进行赋值

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();       
    elementData[s] = e;
    size = s + 1;
}

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                        elementData, index + 1,
                        s - index);
    elementData[index] = element;
    size = s + 1;
}

扩容

oldCapacity保存原来数组的容量,newCapacity为新数组的容量，其大小为oldCapacity的1.5倍，
如果newCapacity新数组容量小于等于所需要minCapacity最小容量则有两种情况：
- 原来的elementData为默认的空实列数组，返回DEFAULT_CAPACITY默认容量、minCapacity最小容量两个间的最大值
- 返回minCapacity
- 还要进行判断minCapacity是否溢出了

如果newCapacity新数组容量大于所需要minCapacity最小容量

newCapacity小于等于MAX_ARRAY_SIZE允许的最大数组容量，则返回newCapacity

newCapacity大于MAX_ARRAY_SIZE允许的最大数组容量，则判断是否溢出，无溢出则返回Integer.MAX_VALUE。

    private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(
        elementData,newCapacity(minCapacity)
        );
}

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Integer.java:
@Native public static final int   MAX_VALUE = 0x7fffffff;

Remove方法

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

Clear方法

清楚所有元素

public void clear() {
        modCount++;
        final Object[] es = elementData;
        for (int to = size, i = size = 0; i < to; i++)
            es[i] = null;
    }