ArrayList

简介

ArrayList是一种以数组实现的List，与数组相比，它具有动态扩展的能力，称之为动态数组。

ArrayList 整体架构

类图

ArrayList实现了List, RandomAccess, Cloneable, Serializable等接口。

ArrayList实现了List，提供了基础的添加、删除、遍历等操作。
ArrayList实现了RandomAccess，提供了随机访问的能力。
ArrayList实现了Cloneable，可以被克隆。
ArrayList实现了Serializable，可以被序列化。

源码

属性

//默认容量
private static final int DEFAULT_CAPACITY = 10;
//空数组，如果传入的容量为0时使用
private static final Object[] EMPTY_ELEMENTDATA = {};
//空数组，传传入容量时使用，添加第一个元素的时候会重新初始为默认容量大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储元素的数组
transient Object[] elementData;
//集合中元素的个数
private int size;

构造函数

ArrayList(int initialCapacity)

传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，如果小于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);
        }
    }

ArrayList()

不传初始容量，初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，会在添加第一个元素的时候扩容为默认的大小，即10。

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

ArrayList(Collection<? extends E> c)

传入集合并初始化elementData，这里会使用拷贝把传入集合的元素拷贝到elementData数组中，如果元素个数为0，则初始化为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;
        }
    }

add(E e)

添加元素到末尾，平均时间复杂度为O(1)。

    public boolean add(E e) {
        //是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //数组最后一个
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        //如果是空数组，就初始化为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
    }   

    private void grow(int minCapacity) {
        
        int oldCapacity = elementData.length;
        //新容量=旧容量+旧容量/2
        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);
    } 

检查是否需要扩容；
如果elementData等于空数组则初始化容量大小为10；
新容量是老容量的1.5倍（oldCapacity + (oldCapacity » 1)），如果计算后新容量比需要的容量还小，则以需要的容量为准；
创建新容量的数组并把老数组拷贝到新数组；

add(int index, E element)

添加元素到指定位置，平均时间复杂度为O(n)。

    public void add(int index, E element) {
        //数组边界检查
        rangeCheckForAdd(index);
        //检查是否需要扩容
        ensureCapacityInternal(size + 1);
        //将inex及其之后的元素往后挪一位，则index位置处就空出来了
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    //src:源数组
    //srcPos:起始索引
    //dest:目标数组
    //destPos:目的起始索引
    //length:拷贝数组元素数量
    public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

数组边界检查；
检查是否需要扩容；
把插入索引位置后的元素都往后挪一位；
在插入索引位置放置插入的元素；
size+1

addAll(Collection<? extends E> c)

两个集合的并集

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        //检查数组扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //将c中元素全部拷贝到数组的最后
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

拷贝c中的元素到数组a中；
检查是否需要扩容；
数组a中的元素拷贝到elementData的尾部；

get(int index)

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

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

        return elementData(index);
    }

检查索引是否越界，只检查是否越上界，如果越上界抛出IndexOutOfBoundsException异常，如果越下界抛出的是ArrayIndexOutOfBoundsException异常。
返回索引位置处的元素；

remove(int index)

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

    public E remove(int index) {
        //检查数组越界
        rangeCheck(index);
        
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        //如果index不是最后一位，则将index之后的元素往前挪一位
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

检查索引是否越界；
获取指定索引位置的元素；
如果删除的不是最后一位，则其它元素往前移一位；
将最后一位置为null，方便GC回收；
返回删除的元素。

ArrayList删除元素的时候不缩容。

remove(Object o)

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

    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;
    }
    //快速删除
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }    

找到第一个等于指定元素值的元素；
快速删除；

fastRemove(int index)相对于remove(int index)少了检查索引越界的操作

retainAll(Collection<?> c)

两个集合的交集。

    public boolean retainAll(Collection<?> c) {
        //非空检查
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            //如果r!=size说明异常，把r后边的元素拷贝到w后边
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                //w以后的元素置空
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

遍历elementData数组；
如果元素在c中，则把这个元素添加到elementData数组的w位置并将w位置往后移一位；
遍历完之后，w之前的元素都是两者共有的；
将w之后（包含）的元素置为null，方便GC回收；

removeAll(Collection<?> c)

求两个集合的单向差集，只保留当前集合中不在c中的元素，不保留在c中不在当前集体中的元素。

    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

迭代器

ArrayList.iterator()

    public Iterator<E> iterator() {
        return new Itr();
    }

ArrayList内部类Itr实现迭代器。

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        //期望的列表修改次数
        int expectedModCount = modCount;

        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;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

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

总结

ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
ArrayList添加元素到中间比较慢，因为要挪动元素，平均时间复杂度为O(n)；
ArrayList从尾部删除元素极快，时间复杂度为O(1)；
ArrayList从中间删除元素比较慢，因为要挪动元素，平均时间复杂度为O(n)；
ArrayList支持并集，调用addAll(Collection<? extends E> c)方法即可；
ArrayList支持交集，调用retainAll(Collection<? extends E> c)方法即可；
ArrayList支持单向差集，调用removeAll(Collection<? extends E> c)方法即可；

Java集合-02丨ArrayList