ArrayList与LinkedList区别

先上结论：
ArrayList与LinkedList都实现了List接口。

ArrayList底层是数组，查询快、增删慢；
LinkedList底层是链表，查询慢、增删快。

样例一（增删）

代码验证：

两个插入，看运行结果耗时似乎差别也不是很大，难道结论有问题？

代码改造一下 add方法中添加插入索引，从每次从尾部追加改为每次从头部追加。

差异显著，也验证了结论：ArrayList增删比LinkedList慢的多。
源码如下：

public class Test {

    public static void main(String[] args) {

        int num = 100000;

        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
        long l1 = System.currentTimeMillis();
        for (int i = 0; i < num; i++) {
            arrayList.add(0,i);
        }
        long l2 = System.currentTimeMillis();
        System.out.println("ArrayList添加"+num+"数据耗时：" + (l2 - l1));
        for (int i = 0; i < num; i++) {
            linkedList.add(0,i);
        }
        long l3 = System.currentTimeMillis();
        System.out.println("LinkedList添加"+num+"数据耗时：" + (l3 - l2));
    }

}

样例二（查询）

代码验证：

我们先每次查询第一条元素，结果却是耗时差不多。

我们再改成遍历查询每一条元素，结果差异明显。也印证了我们的结论：ArrayList查询速度比LinkedList快。

源码如下：

public class Test {

    public static void main(String[] args) {
        int num = 100000;
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < num; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        long l1 = System.currentTimeMillis();
        for (int i = 0; i < num; i++) {
            arrayList.get(0);
        }
        long l2 = System.currentTimeMillis();
        System.out.println("ArrayList查询"+num+"数据耗时：" + (l2 - l1));
        for (int i = 0; i < num; i++) {
            linkedList.get(0);
        }
        long l3 = System.currentTimeMillis();
        System.out.println("LinkedList查询"+num+"数据耗时：" + (l3 - l2));
    }
}

看完两个样例，总会有些疑问，在某些情况下ArrayList与LinkedList的结论似乎有些不对，或者为啥会出现这样的结果，这些疑问就需要一起看看源码吧。

ArrayList源码

1.增加元素

我们知道ArrayList的底层是数组。

再看构造方法，在我们未声明集合大小时，默认是一个空数组。

接下来看看add方法 ensureCapacityInternal：确保数组不会越界，当超出数组长度需要扩容。传入的值size+1，size表示当前集合的存储的元素数量，+1保证再放一个元素也能容纳。
多说一句：数组是定长的，elementData[index] 当index大于elementData.length的时候就会报数组越界，所以为避免数组越界需要重新声明一个长度更长的数组存储。当然如果一开始声明特别长度特别长的数组就会造成资源浪费，会开辟不必要的内存空间。这里也是。ArrayList数组默认长度是10，而jdk1.8时，构造器中初始化的是一个空的数组，只有在add方法调用的时候才会初始化，创建长度10的数组。

我们跟进ensureCapacityInternal方法，calculateCapacity获取到最小的数组长度，默认的是10。ensureExplicitCapacity方法中最小长度大于当前数组长度就需要扩容了，也就是调用grow方法。

核心扩容方法，扩容的后的大小为int newCapacity = oldCapacity + (oldCapacity >> 1); >>1 右移1位也就是除二，也就是扩容到原来的1.5倍。Arrays.copyOf方法意思是将老数组复制到新数组，参数一为老数组，参数二为新数组长度，返回参数为新数组。注意真正耗费时间的是这个数组重新复制的过程。所以我们能理解：一次add如果不触发扩容grow方法是不怎么耗时间的。而每次扩容到原来的1.5倍大小，数组越大就越难触发扩容。所以我们能理解样例一中第一个截图为啥ArrayList的add并没有那么耗时。

再看样例一截图二，add(int index, E element) 方法，rangeCheckForAdd会先判断传入的下标是否越界。ensureCapacityInternal在判断是否需要扩容。System.arraycopy就是整个耗时的罪魁祸首，插入时需要把当前下标及以后的元素往后移动一位。介绍一下System.arraycopy：参数一代表源数组，参数二代表源数组要复制的起始位置，参数三代表目标数组，参数四代表目标数组复制的起始位置，参数五代表复制的长度。这一个移动位置的过程是非常消耗时间的，而且样例一截图二中每一次都是从0开始插入也就是每一次都要移动位置。这就是为啥这个耗时间。其实add(int index, E element)才是语义上的插入，add(E element)只能说是追加。所以结论还是没错，ArrayList插入慢。