Java集合包 - ArrayList - 《Java学习笔记》

ArrayList底层数据结构
继承体系
源码解析
总结

ArrayList底层数据结构

ArrayList是一种以数组实现的List，同时具备动态扩展能力，称为动态数组。

继承体系

实现了List，RandomAccess，Cloneable，java.io.Serializable等接口

List：基础的添加，删除，遍历操作
RandomAccess：随机访问能力，时间复杂度O(1)
Cloneable:可被克隆
Serializable：可被序列化
源码解析
参考资料：http://cmsblogs.com/?p=4727
属性
```java /**
- 默认容量 */ private static final int DEFAULT_CAPACITY = 10;

/**

空数组，如果传入的容量为0时使用 */ private static final Object[] EMPTY_ELEMENTDATA = {};

/**

空数组，传传入容量时使用，添加第一个元素的时候会重新初始为默认容量大小为DEFAULT_CAPACITY */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**

存储元素的数组 */ transient Object[] elementData; // non-private to simplify nested class access

/**

集合中元素的个数 */ private int size; ``` (1) DEFAULT_CAPACITY
默认容量，通过 new ArrayList() 创建时的默认容量。
(2) EMPTY_ELEMENTDATA
空数组，通过 new ArrayList(0) 创建时用的是这个空数组。
(3) DEFAULTCAPACITY_EMPTY_ELEMENTDATA
空数组，通过new ArrayList()创建时用的是这个空数组，与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组会初始化为DEFAULT_CAPACITY（10）个元素。
(4) elementData
真正存放元素的地方，使用transient是为了不序列话这个字段。
(5) size
真正存储元素的个数，而不是elementData数组的长度。
构造方法

ArrayList()构造方法

(1) elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

public ArrayList() {
    // 如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    // 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(int initialCapacity) 构造方法

（1）容量为0，elementData赋值为EMPTY_ELEMENTDATA。
（2）容量大于0，elementData = new Object[initialCapacity]。
（3）容量小于0，抛异常。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 如果传入的初始容量大于0，就新建一个数组存储元素
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果传入的初始容量等于0，使用空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 如果传入的初始容量小于0，抛出异常
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

ArrayList(Collection<? extends E> c) 构造方法

（1）先将传入的集合转为数组
（2）如果数组长度不为0，则判断转为数组类型是不是Object[]，不是则重新拷贝为Object[].class类型
（3）如果数组长度为0，赋值为EMPTY_ELEMENTDATA

/**
* 把传入集合的元素初始化到ArrayList中
*/
public ArrayList(Collection<? extends E> c) {
    // 集合转数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 检查c.toArray()返回的是不是Object[]类型，如果不是，重新拷贝成Object[].class类型
        if (elementData.getClass() != Object[].class)
            // 拷贝elmentData数组, 存储至Object[]数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 如果c的空集合，则初始化为空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

add方法

add(E e) — 时间复杂度O(1)。 ```java public boolean add(E e) { // 检查是否需要扩容 ensureCapacityInternal(size + 1); // 把元素插入到最后一位 elementData[size++] = e; return true; }

private void ensureCapacityInternal(int minCapacity) { // 检查是否需要扩容 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }

private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小10 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, 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); // 如果新容量发现比需要的容量还小，则以需要的容量为准 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量已经超过最大容量了，则使用最大容量 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 以新容量拷贝出来一个新数组 elementData = Arrays.copyOf(elementData, newCapacity); }

（1） 检查是否需要扩容<br />（2）如果elemData数组为空数组，则初始化默认大小为10<br />（3）检查是否需要扩容，新容量为就容量的1.5倍，如果加了容量之后发现还是比需要的容量小，则以需要的容量为准。<br />（4）创建的新容量最大容量不超过MAX_ARRAY_SIZE。<br />（5）一新的容量拷贝出来一个新数组。
- **add(int index, E e)  -- 时间复杂度O(n)**
```java
public void add(int index, E element) {
    // 检查是否越界
    rangeCheckForAdd(index);
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);
    // 将inex及其之后的元素往后挪一位，则index位置处就空出来了
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将元素插入到index的位置
    elementData[index] = element;
    // 大小增1
    size++;
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

addAll方法

求两个集合的并集 - 时间复杂度O(n)

/**
* 将集合c中所有元素添加到当前ArrayList中
*/
public boolean addAll(Collection<? extends E> c) {
    // 将集合c转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 检查是elementData数组否需要扩容
    ensureCapacityInternal(size + numNew);
    // 将c中元素全部拷贝到elementData数组的尾部
    System.arraycopy(a, 0, elementData, size, numNew);
    // 大小增加c的大小
    size += numNew;
    // 如果c不为空就返回true，否则返回false
    return numNew != 0;
}

get方法

获取指定索引位置的元素，时间复杂度O(1)。

public E get(int index) {
    // 检查是否越界
    rangeCheck(index);
    // 返回数组index位置的元素
    return elementData(index);
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
    return (E) elementData[index];
}

remove方法

remove(int index)

删除指定索引位置的元素，时间复杂度为O(n)

public E remove(int index) {
    // 检查是否越界
    rangeCheck(index);
    modCount++;
    // 获取index位置的元素
    E oldValue = elementData(index);
    // 如果index不是最后一位，则将index之后的元素往前挪一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 将最后一个元素删除，帮助GC
    elementData[--size] = null; // clear to let GC do its work
    // 返回旧值
    return oldValue;
}

remove(Object o)

删除指定元素值的元素，时间复杂度为O(n)。

public boolean remove(Object o) {
    if (o == null) {
        // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
        for (int index = 0; index < size; index++)
            // 如果要删除的元素为null，则以null进行比较，使用==
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
        for (int index = 0; index < size; index++)
            // 如果要删除的元素不为null，则进行比较，使用equals()方法
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
private void fastRemove(int index) {
    // 少了一个越界的检查
    modCount++;
    // 如果index不是最后一位，则将index之后的元素往前挪一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 将最后一个元素删除，帮助GC
    elementData[--size] = null; // clear to let GC do its work
}

retainAll方法

removeAll方法

总结

（1）ArrayList内部使用数组存储元素，当数组不够时能够进行扩容，每次增加旧容量一半的空间，不会缩容。
（2）ArrayList支持随机访问，通过索引访问元素，时间复杂度O(1)。
（3）ArrayList添加元素至尾部平均时间复杂度为O(1)。
（4）ArrayList添加元素到中间的平均时间复杂度为O(n)，因为需要搬移数据。
(5) ArrayList删除元素时间复杂度为O(1)。
（6）ArrayList删除中间元素的时间复杂度为O(n),因为要搬移数据。
（7）ArrayList支持并集（addAll），交集(retainAll)，差集(removeAll)。

ArrayList