ArrayList解析基本介绍

ArrayList底层由数组实现，默认初始化数组为空数组，可以实现数组的动态扩容，第一次添加数据时组数默认大小为10，后续每次扩容，默认为当前数组大小的1.5倍。默认线程不安全

底层数据结构

    /**     * Shared empty array instance used for default sized empty instances. We     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when     * first element is added.     */    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    /**     * The array buffer into which the elements of the ArrayList are stored.     * The capacity of the ArrayList is the length of this array buffer. Any     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA     * will be expanded to DEFAULT_CAPACITY when the first element is added.     */    transient Object[] elementData; // non-private to simplify nested class access

构造函数

初始化构造函数是否是无参构造，如果为无参构造方法则默认初始换为空数组，如果为有参构造，构造参数为int类型时，会先判断传入的大小是否为0，如果为0，则默认为空数组，如果大于0，则new 一个新的并且容量大小为当前传入值的object数组；如果传入参数为集合，会按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表。

 /**     * Constructs an empty list with the specified initial capacity.     *     * @param  initialCapacity  the initial capacity of the list     * @throws IllegalArgumentException if the specified initial capacity     *         is negative     */    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);        }    }    /**     * Constructs an empty list with an initial capacity of ten.     */    public ArrayList() {        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }    /**     * Constructs a list containing the elements of the specified     * collection, in the order they are returned by the collection's     * iterator.     *     * @param c the collection whose elements are to be placed into this list     * @throws NullPointerException if the specified collection is null     */    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;        }    }

添加元素与自动扩容add()方法

添加一个元素进入list的过程

1、调用ensureCapacityInternal方法，确保数组容量足够

2、调用calculateCapacity方法，计算数组容量，如果当前数组是初始化空数组，则返回默认数组容量大小的值与传入minCapacity（该值为当前数组元素个数+1）值中最大的一个；如果当前数组不为初始化数组，则返回minCapacity。

3、继续调用ensureExplicitCapacity方法，首先将modCount参数加1，判断需要的最小容量是否大于当前数组的容量，如果大于，则需要进行数组扩容，反之，执行elementData[size++] = e;方法，元素进入，添加完成

4、如果当前容量不满足元素进入，调用grow方法，记录oldCapacity为当前数组容量，记录newCapacity为oldCapacity的1.5倍，判断新的数组容量是否满足当前元素进入后的最小容量，如果小于，则将minCapacity赋值给newCapacity，继续判断newCapacity是否大于（Integer.MAX_VALUE - 8）的值，如果大于判断 (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;并重新设置newCapacity的值，最后创建一个大小为newCapacity的新数组并将原数组的数据拷贝过来

 /**     * Appends the specified element to the end of this list.     *     * @param e element to be appended to this list     * @return <tt>true</tt> (as specified by {@link Collection#add})     */    public boolean add(E e) {        ensureCapacityInternal(size + 1);  // Increments modCount!!        elementData[size++] = e;        return true;    }    /**     * Inserts the specified element at the specified position in this     * list. Shifts the element currently at that position (if any) and     * any subsequent elements to the right (adds one to their indices).     *     * @param index index at which the specified element is to be inserted     * @param element element to be inserted     * @throws IndexOutOfBoundsException {@inheritDoc}     */    public void add(int index, E element) {        rangeCheckForAdd(index);        ensureCapacityInternal(size + 1);  // Increments modCount!!        System.arraycopy(elementData, index, elementData, index + 1,                         size - index);        elementData[index] = element;        size++;    } private void ensureCapacityInternal(int minCapacity) {        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));    }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++;        // overflow-conscious code        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }private void grow(int minCapacity) {        // overflow-conscious code        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + (oldCapacity >> 1);        if (newCapacity - minCapacity < 0)            newCapacity = minCapacity;        if (newCapacity - MAX_ARRAY_SIZE > 0)            newCapacity = hugeCapacity(minCapacity);        // minCapacity is usually close to size, so this is a win:        elementData = Arrays.copyOf(elementData, newCapacity);    }

addAll()方法

1、将传入的对象先进行toArray操作

2、再记录toArray后数组的长度

3、同add操作一样，判断当前数组容量，扩容机制同add方法一样

4、调用System.arraycopy方法，将toArray操作后的数组拷贝至当前数组

/**     * Appends all of the elements in the specified collection to the end of     * this list, in the order that they are returned by the     * specified collection's Iterator.  The behavior of this operation is     * undefined if the specified collection is modified while the operation     * is in progress.  (This implies that the behavior of this call is     * undefined if the specified collection is this list, and this     * list is nonempty.)     *     * @param c collection containing elements to be added to this list     * @return <tt>true</tt> if this list changed as a result of the call     * @throws NullPointerException if the specified collection is null     */    public boolean addAll(Collection<? extends E> c) {        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacityInternal(size + numNew);  // Increments modCount        System.arraycopy(a, 0, elementData, size, numNew);        size += numNew;        return numNew != 0;    }    /**     * Inserts all of the elements in the specified collection into this     * list, starting at the specified position.  Shifts the element     * currently at that position (if any) and any subsequent elements to     * the right (increases their indices).  The new elements will appear     * in the list in the order that they are returned by the     * specified collection's iterator.     *     * @param index index at which to insert the first element from the     *              specified collection     * @param c collection containing elements to be added to this list     * @return <tt>true</tt> if this list changed as a result of the call     * @throws IndexOutOfBoundsException {@inheritDoc}     * @throws NullPointerException if the specified collection is null     */    public boolean addAll(int index, Collection<? extends E> c) {        rangeCheckForAdd(index);        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacityInternal(size + numNew);  // Increments modCount        int numMoved = size - index;        if (numMoved > 0)            System.arraycopy(elementData, index, elementData, index + numNew,                             numMoved);        System.arraycopy(a, 0, elementData, index, numNew);        size += numNew;        return numNew != 0;    }

set()方法

用指定元素替换数组中指定位置的元素

1、调用rangeCheck，检查给定的索引是否在范围内

2、记录原位置的元素值

3、将当前指定位置的元素替换为新的元素

4、返回旧的元素值

/**     * Replaces the element at the specified position in this list with     * the specified element.     *     * @param index index of the element to replace     * @param element element to be stored at the specified position     * @return the element previously at the specified position     * @throws IndexOutOfBoundsException {@inheritDoc}     */    public E set(int index, E element) {        rangeCheck(index);        E oldValue = elementData(index);        elementData[index] = element;        return oldValue;    }

get()方法

返回此列表中指定位置的元素

1、检查给定的索引是否在范围内

2、返回此列表中指定位置的元素

/**     * Returns the element at the specified position in this list.     *     * @param  index index of the element to return     * @return the element at the specified position in this list     * @throws IndexOutOfBoundsException {@inheritDoc}     */    public E get(int index) {        rangeCheck(index);        return elementData(index);    }

删除方法指定位置删除 remove(int index)方法

移除此列表中指定位置的元素。 将任何后续元素向左移动（从它们的索引中减去一个）。

1、检查给定的索引是否在范围内

2、操作数量统计加一

3、记录旧的元素值

4、记录需要移动元素的个数

5、将剩余元素进行向左移动，并将最后位置的元素置为null，size减一

6、返回旧的元素值

/**     * Removes the element at the specified position in this list.     * Shifts any subsequent elements to the left (subtracts one from their     * indices).     *     * @param index the index of the element to be removed     * @return the element that was removed from the list     * @throws IndexOutOfBoundsException {@inheritDoc}     */    public E remove(int index) {        rangeCheck(index);        modCount++;        E oldValue = elementData(index);        int numMoved = size - index - 1;        if (numMoved > 0)            System.arraycopy(elementData, index+1, elementData, index,                             numMoved);      //原数组 elementData = {"1","2","3","4"}      //将2删除后，元素移动      //当前数组elementData = {"1","3","4","4"}      //将最后一位元素设置为null elementData = {"1","3","4",null}        elementData[--size] = null; // clear to let GC do its work        return oldValue;    }

指定元素的删除 remove(Object o)方法

从此列表中删除第一次出现的指定元素（如果存在）。 如果列表不包含该元素，则它保持不变。 更正式地，删除具有最低索引i的元素，使得(o==null ? get(i)==null : o.equals(get(i))) （如果存在这样的元素）。 如果此列表包含指定的元素（或等效地，如果此列表因调用而更改），则返回true 。

/**     * Removes the first occurrence of the specified element from this list,     * if it is present.  If the list does not contain the element, it is     * unchanged.  More formally, removes the element with the lowest index     * <tt>i</tt> such that     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>     * (if such an element exists).  Returns <tt>true</tt> if this list     * contained the specified element (or equivalently, if this list     * changed as a result of the call).     *     * @param o element to be removed from this list, if present     * @return <tt>true</tt> if this list contained the specified element     */    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;    }

调整数组实际大小 trimToSize()方法

将此ArrayList实例的容量修剪为列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储空间

public void trimToSize() {        modCount++;        if (size < elementData.length) {            elementData = (size == 0)              ? EMPTY_ELEMENTDATA              : Arrays.copyOf(elementData, size);        }    }

总结

因为ArrayList底层是基于数组实现的，所以数组的优缺点也是ArrayList的优缺点，典型的数组优点在于随机指定所以存储和查询方便，按照索引遍历数组时方便，而在进行数组扩容和删除元素的操作的时候，调用System.arrayCopy方法时会导致大量的元素移动，性能较差。