【Java基础】ArrayLsit 和 LinkedList区别、底层原理以及扩容算法

一、ArrayList与LinkedList

• ArrayList底层是一个Object类型的数组，初始容量是10，支持动态扩容，扩容后的容量是当前容量的1.5倍，它的最大容量是 Integer.MAX_VALUE - 8（但是仍可以扩容到Integer.MAX_VALUE），对于空出的8位，目前的解释是避免一些机器内存溢出，减少出错几率。
• 底层源码：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 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 maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• LinkedList底层是一个双向链表，初始容量是0，扩容只需新建节点进行指针指向即可。
• 底层源码：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

二、ArrayList和LinkedList的区别

1. 同步性
   ArrayList和LinkedList是不同步的。所以如果不要求线程安全的话，可以使用ArrayList或LinkedList，可以节省为同步而耗费的开销。但在多线程的情况下，有时候就不得不使用Vector了。当然，也可以通过一些办法包装ArrayList,LinkedList，使他们也达到同步，但效率可能会有所降低。
2. 数据增长
   从内部实现机制来讲ArrayList是使用Objec的数组形式来存储的。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，ArrayList扩容是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。
3. 检索、插入、删除对象的效率
   • ArrayList随机访问效率很高，因为元素的存储是有序的，通过下标index可以知道所查询数据在内存中的位置，寻址快，时间复杂度O(1)。LinkedList查询效率较低，它在查询指定数据的时候需要遍历链表逐个查询，时间复杂度O(n)。
   • ArrayList的插入和删除效率都比较低，因为首先要遍历数据找到插入/删除位置，此外还需要进行大量的数据移动，时间复杂度O(n)。LinkedList的插入/删除元素的效率比较高，插入和删除的过程中只需要修改链表的指针即可，但是在中间指定位置插入元素，需要先遍历找到元素的位置，然后插入，时间复杂度O(n)。

三、ArrayList的扩容机制

• ensureCapacityInternal
  只有调用了默认构造函数，才可能返回默认为10的容量，如果是构造函数中传入的 Capacity为0，则不会生成默认大小。此时隐含有 minCapacity = size + 1的信息。

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

// 判断当前数组是否是默认构造函数法生成的空数组
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果是则取容量为 max(10, minCapacity)
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 不是就根据原来的值传入下一个方法完成后面的扩容判断
        return minCapacity;
}

• ensureExplicitCapacity
  判断当前ArrayList是否需要进行扩容，如果修改后的数组容量大于当前的数组长度，就需要调用grow() 进行扩容。

// 判断当前ArrayList是否需要进行扩容
private void ensureExplicitCapacity(int minCapacity) {
	// 快速报错机制：防止多个进程同时修改同一个容器的内容
	// 不一致会抛出ConcurrentModificationException
	modCount++;
	if (minCapacity - elementData.length > 0)
	    // 容量过小，需要扩容
            grow(minCapacity);
}

• 扩容核心方法——grow（）

    // 扩容方法
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);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}

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;

1. 如果当前数组是由默认构造函数生成的空数组且第一次添加数据，则minCapacity默认等于10，此时数组的容量会从0扩容为10。之后的数组扩容才是1.5倍扩容。
2. 如果当前数组是由带参构造函数生成且初始容量为0，则minCapacity等于1，此时数组的容量会从0变成1。但是设定初始容量为0，会导致前四次扩容每次都+1，只有在第5次添加数据进行扩容的时候才是按照当前容量的1.5倍进行扩容。
3. 当扩容量大于ArrayList定义的最大值后进行判断，根据与MAX_ARRAY_SIZE的比较确定是返回Integer最大值还是MAX_ARRAY_SIZE。ArrayList允许的最大容量就是Integer的最大值。

四、ArrayList的常用方法

• add(E e) ：默认尾插将元素添加到数组末尾

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
}

• add(int index, E element)：在执行索引位置插入元素，插入完成会进行元素的迁移，效率比较低下

// 按 index进行插入操作
public void add(int index, E element) {
	// 越界判断
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  
        // 复制操作
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
}

• remove(int index)：删除指定索引位置元素，删除后也需要元素的迁移，效率比较低下

// 删除指定位置的元素
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);
        // 便于GC回收最后一个的空间
        elementData[--size] = null;
        return oldValue;
}

• iterator()：

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

private class Itr implements Iterator<E> {
        int cursor;       // 下一个要返回元素的索引
        int lastRet = -1; // 最后一个返回元素的索引; -1 代表没有
        // 快速报错机制的标志，如果最后两者相等，则说明是同步的
        int expectedModCount = modCount;
	
	@SuppressWarnings("unchecked")
        public E next() {
            // 进行同步判定
            checkForComodification();
            ...
        }
	// 同步判定函数
	final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

}

1. 该方法实现了Iterator接口，并对几个方法都进行了自定义实现，同时保证了Java容器的快速报错机制。
2. 快速报错机制能够防止多个进（线）程同时修改同一个容器的内容。在使用迭代器Iterator或者forEach进行迭代遍历时，如果有其它进程想要进行修改，就会抛出ConcurrentModificationException异常。
3. iterator()方法在迭代遍历时会调用checkForComodification方法判断当前ArrayList是否是同步的。
4. 迭代遍历时不能进行add和remove等操作，但是对于Iterator迭代器可以使用remove进行操作，因为此时操作的不是ArrayList而是它的Iterator对象。

参考文档：jdk1.8ArrayList主要方法和扩容机制（源码解析）