【3w1h1p】ArrayList的插入删除真的比LinkedList慢吗？

嗯…ArrayList的插入删除真的比LinkedList慢吗？(大更新）

代码验证

直接上代码验证：

package ShuJUandSuanFa;

import java.util.ArrayList;
import java.util.LinkedList;

public class ArrayTest1 {
    public static void main(String[] args) {
        LinkedList<Integer> linked =new LinkedList<>();
        ArrayList<Integer> array =new ArrayList<>();
        for(int i=0;i<100000;i++) {
            linked.add(i);
        }
        for(int i=0;i<100000;i++) {
            array.add(i);
        }
        long t1 =System.currentTimeMillis();
        for(int i=0;i<10000;i++) {
            linked.add((int)Math.random()*linked.size(),i);
        }
        long t2 =System.currentTimeMillis();
        for(int i=0;i<10000;i++) {
            array.add((int)Math.random()*array.size(),i);
        }
        long t3 =System.currentTimeMillis();
        System.out.println("linked用时："+(t2-t1));
        System.out.println("arr用时："+(t3-t2));

    }
}

运行截图
（更新部分）

link平均速度比不上array！！！

坦白说，这个博客是因为一次群友的奇怪运行结果

这个时候LinkedList插入删除性能会为啥直接拉跨（崩掉）

总结

Arraylist平均速度完败LinkedList
面试官：LinkedList 真的是查找慢、增删快？

---

难怪1.7版本的时候hashmap的设计者主观上选择了头插法，加链表虽然灵活了数据结构，但由于他先扩容后插入，为了节省遍历，直接头插。
而1.8，先插入后扩容，等一切计算好后直接在遍历的最后一步判断是否需要扩容，直接扩容。