ArrayList与LinkedList的区别、源码、性能对比

public class Test5 {
    public static void main(String[] args) {
        ArrayList arr = new ArrayList<>();
        for(int j= 0 ;j<1000;j++){
            arr.add(j+"===");
        }
        //模拟查询数据库操作，等待100ms
        ThreadUtil.safeSleep(100);

        LinkedList linkedList = new LinkedList();
        long begin = System.nanoTime();
        for(String a : arr){
            linkedList.add(a);
        }
        System.out.println("linkedList花费了："+(System.nanoTime()-begin)+"纳秒，数量size：" + arr.size());
    }
}


public class Test3 {
    public static void main(String[] args)throws Exception {
        ArrayList arr = new ArrayList<>();
        for(int j= 0 ;j<1000;j++){
            arr.add(j+"===");
        }
        //模拟查询数据库操作，等待100ms
        ThreadUtil.safeSleep(100);

        ArrayList arrayList = new ArrayList();
        long begin2 = System.nanoTime();
        for(String a : arr){
            arrayList.add(a);
        }
        System.out.println("arrayList 花费了："+(System.nanoTime()-begin2)+"纳秒，数量size：" + arr.size());
    }
}

1.数据量10（LinkedList优）

2.数据量100（LinkedList优）

3.数据量1000 （多数情况arrayList优于LinkedList）

4.数据量1w（差不多）

5.数据量10w（差不多）

6.数据量100w（差不多，多数情况arrayList优于LinkedList）

7.数据量1000w（arrayList大大快于LinkedList）

探究：探究10w、100w时 arrayList为什么跟linkedList时间相近，按规律当数据量越来越大时不应该是arrayList一直优于LinkedList吗？
结论：先说结论，再看源码。当数据量71140、810325时，都会发扩容。扩容消耗了大量时间。

看图说话！！！！！！！！！！
数据量1215487是上次在810325扩容后数组的最大长度（最大容量）

当数据量1215488时，因为原数组存不了第1215488的那个元素。就会触发扩容。结果所消耗的时间是原来的三倍。

（1） arrayList的add方法做了两件事。一是走了ensureCapacityInternal(size + 1)方法；二是把元素添加进elementData[]数组

(2)ensureCapacityInternal()方法里也有两步，先去看里面那个方法是干什么的

这个方法就是来计算容量大小的

这个方法是判断当前存储的元素下标是否超过数组长度，超过就扩容。
（后面解释为什么minCapacity理解为下标更容易理解）

这个方法是讲计算新扩容数组能存储元素的最大容量是好多个，也就是计算扩容数组长度。

在这里我们先了解arrayList集合的构造方法是怎么创建对象的（构造方法源码自己去找代码看，这里说逻辑）。它是这么创建的，分两种情况：
一：当我们new ArrayList()时，没指定容量，或者是new ArrayList(0)时，那么new出来的数组就是长度为0的空数组。那么当我们往集合里添加第一个元素时，会先执行calculateCapacity()【计算容量】方法（这个方法的逻辑是如果我们创建的数组为空数组，那么它就会从算数组常量DEFAULT_CAPACITY与我们传入minCapacity取最大值！DEFAULT_CAPACITY的值为10），并且执行到以下grow()方法时，它会帮我们扩容成长度为常量10的数组。然后再往数组里存第一个元素

二：如果我们new ArrayList(5)时，指定了容量。那么new出来的数组就是长度为5的数组。如果我们是for循环存元素，存前五个元素都不会触发扩容，只有存第6个之后才会触发。比如存第6个，数组的新容量（长度）就是grow()里的那个公式，大约是上次容量的1.5倍（7=5+5/2）。当存到第8个时又触发扩容（10=7+7/2）

解释minCapacity理解为下标，同时解释【跳着存】：
（minCapacity参数相等于minCapacity=当前元素存储下标位置+1。例子：如elementData数组初始长度是5，我要跳着存，直接把某个值存入elementData数组，且下标为10。此时minCapacity的值就是11=10+1，意思就是提醒该elementData数组的最小容量至少是11，才能装得下标为10的第11个元素。此时grow（）方法里的扩容判断就是这样的：本来新扩容数组长度应该为7=5+5/2，但是7<11，肯定是存不下第11个元素的，所以把长度替换为11（最小容量），所以扩容出来的数组的长度为11，也就恰恰能存放第11个元素。如果再往新数组里存放第12位的元素，那么还是会触发扩容，长度为16=11+11/2，如果存放数组下标<=15的元素，那么都不会触发扩容，如果又存放超过数组下标15的。重复上面的【跳着存】扩容）

一、当数据量小时，咱们for循环存元素时，前期会触发多次扩容，多次扩容就会设计到数组元素的迁移，所以数据量小时arrayList插入速度比LinkdList
二、当数据量越来越大时，数组扩容的次数就会变少，毕竟每次扩容都是上次的1.5倍。效率就比LinkdList
三、如果我们能大概估量到arrayList的数量时，咱们new ArrayList(10000)时，尽量指定容量。减少扩容次数
四、LinkedList就毫无优势吗？no，LinkedList可以实现队列，栈等数据结构，这是它的优势