一、ArrayList

1、继承图

ArrayList.png

2、特点：

1）、随机访问
2）、可以被序列化
3）、可以被克隆
4）、会进行动态扩容，但不会缩容

3、属性的说明

/** 默认初始容量 */
private static final int DEFAULT_CAPACITY = 10;
/** 扩容时，若扩容后的容量超过该值，则以Integer.MAX_VALUE作为新的容量值 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** 空对象数组，当初始化集合时，传入的指定数量为0时使用 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 空对象数组，当初始化集合时，使用“无参”构造函数时，使用该参数初始化elementData，
 * 在第一次添加元素时，若elementData为该类型，则扩容为默认容量，即DEFAULT_CAPACITY = 10
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** 真正存储元素的数组，不参与序列化 */
transient Object[] elementData;
/** 集合中元素的数量 */
private int size;
/** 修改次数的统计 */
protected transient int modCount = 0;

4、三种构造方式

1）、有参构造函数：指定大小

public ArrayList(int initialCapacity) {
    if (initialCapacity < 0) {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }
    else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA; }
    else { this.elementData = new Object[initialCapacity];
    }
}

2）、无参构造函数：不指定大小，以空对象数组初始化，在第一次添加元素时，会将容量扩充为DEFAULT_CAPACITY，即10

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

3）、将另一个集合以Iterate遍历的顺序添加到当前集合中

public ArrayList(Collection<? extends E> c) {
    //TODO 略
}

5、常用API说明：

5.1、add(E element)

步骤：
1）、检查是否需要扩容
2）、若elementData等于
DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则初始的容量大小设为DEFAULT_CAPACITY，即10；
3）、按照1.5倍的速度扩容（newCapacity = oldCapacity + (oldCapacity >> 1)）；若扩容后的容量小于所需容量（newCapacity < minCapacity），则按照所需容量返回
4）、对数组进行拷贝和移位

@Override 
public boolean add(E element) { 
    //检查是否需要扩容 
    ensureCapacityInternal(size + 1); 
    elementData[size++] = element; 
    return true; 
} 

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

private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        //按照最大值取，只需要扩容一次，若按照最小值取，则需要多次扩容 
        return Math.max(DEFAULT_CAPACITY, minCapacity); 
    } 
    return minCapacity; 
}
 
private void ensureExplicitCapacity(int minCapacity) { 
    modCount++; 
    if (minCapacity > elementData.length) { 
        //对elementData进行扩容 
        grow(minCapacity); 
    }
} 
/** 
 * 按照1.5倍的速度扩容 
 * 若扩容后的容量小于指定容量MAX_ARRAY_SIZE，则返回指定容量 
 * 若超出MAX_ARRAY_SIZE，则返回Integer.MAX_VALUE 
 * @param minCapacity 
 */ 
private void grow(int minCapacity) { 
    int oldCapacity = elementData.length; 
    int newCapacity = oldCapacity + (oldCapacity >> 1); 
    if (newCapacity < minCapacity) { 
        newCapacity = minCapacity; 
    } 
    if (newCapacity > MAX_ARRAY_SIZE) { 
        newCapacity = hugeCapacity(minCapacity); 
    } 
    System.out.println("扩容过后，newCapacity = " + newCapacity);       
    elementData = Arrays.copyOf(elementData, newCapacity); 
} 
/**
 * 如果容量超出默认的最大值MAX_ARRAY_SIZE，则按照Integer的最大值处理
 * @param minCapacity
 * @return
 */ 
private static int hugeCapacity(int minCapacity) { 
    if (minCapacity < 0) { 
        throw new OutOfMemoryError(); 
    } 
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; 
}

5.2、add(int index, E element)

步骤
1）、检查索引是否越界，索引的有效范围为闭区间：[0, size]
2）、检查是否需要扩容
3）、指定位置的元素往后移动一位
4）、把新的元素值添加到index对应的位置
5）、数组的实际长度size，加1

/**
 * index的范围为[0-size]，闭区间
 * @param index
 * @param element
 */
@Override public void add(int index, E element) {
    //TODO 检查索引是否越界
    rangeCheckForAdd(index);
    //检查是否需要扩容 ensureCapacityInternal(size + 1);
    //把index往后的元素依次往后移动
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    //将element插入到index的位置 elementData[index] = element;
    //数组的大小加1 size++; } private void rangeCheckForAdd(int index) {
    if (index > size || index < 0) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

5.3、get(int index)

注意：在jdk源码中，如果越上界（index>=size）抛出IndexOutOfBoundsException异常，如果越下界（index<0）抛出的是ArrayIndexOutOfBoundsException异常。

@Override
public E get(int index) {
    rangeCheck(index); return elementData(index);
}
/**
 * 只检查上界
 */
private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

5.4、remove(int index)

删除指定索引位置的元素，步骤如下：
1）、检查索引是否越界；
2）、获取指定索引位置的元素；
3）、如果删除的不是最后一位，则其它元素往前移一位；
4）、将最后一位置为null，方便GC回收；
5）、返回删除的元素。

public E remove(int index) {
    //1、检查索引是否越界；
    //2、获取指定索引位置的元素；
    //3、如果删除的不是最后一位，则其它元素往前移一位；
    //4、将最后一位置为null，方便GC回收；
    //5、返回删除的元素。
    rangeCheck(index); modCount++;
    E removeValue = elementData(index);
    //如果删除的元素不是最后的位置(size-1)，则index后面的元素，都要依次往前移动一位
    if (index < size - 1) {
        System.arraycopy(elementData, index+1, elementData, index, size - 1 - index);
    }
    elementData[--size] = null; return removeValue; }

5.5、remove(Object o)

注意：
1）、需要区分的是传入的对象是否是null
2）、是否相等，用的是equals方法，而不是 ==
3）、使用的是无需检查索引越界的fastRemove，因为该方法的参数是由内部循环传入，因此不需要检查索引值是否在范围里
4）、删除的是第一个找到的那个元素

@Override
public boolean remove(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++) {
            if (elementData[i] == null) {
                fastRemove(i); return true;
            }
        }
    } else {
          for (int i = 0; i < size; i++) {
              if (o.equals(elementData[i])) {
                  fastRemove(i); return true;
              }
          }
    }
    return false;
}