八股文死记硬背打脸记

•  背景

        我们都知道，再编程领域数据结构的重要性，常见的数据结构包括 List、Set、Map、Queue、Tree、Graph、Stack 等，其中 List、Set、Map、Queue 可以从广义上统称为集合类数据结构。而Java也提供了很多的集合数据结构以供开发者开箱即用，其中ArrayList和LinkedList区别的问题早已成为烂大街的八股文面试题其中之一                

        作为一名Javaer，不论是日常开发还是作为面试官，都不得不承认八股文在如今的江湖中占有举足轻重的地位。"面试造火箭，入职拧螺丝"  这是许多面试同学吐槽最多的一句话，但就我个人而言，我认为背八股文对于大多数开发同学而言仍然是一个不错的提升技术途径(特别是对于一些小公司接触不到复杂业务的开发同学)

        凡事都有一个但是，此八股文非彼八股文，不能像读书时背课文似的死记硬背，最好结合自己开发中的实践，要学会有自己的理解，否则有时就会闹笑话，此处引申一则自己的亲身面试经历

       A同学："ArrayList的底层实现是数组，而LinkedList是双向列表"

       我内心："马上及格"

       A同学："所以ArrayList适合查询频繁的业务场景而LinkedList适合增删频繁的业务场景"

       我内心 ："及格，但有无自己的理解呢"        

       我 ："你平时开发中是怎么使用LinkedList的？"

       A同学："就像我刚才讲的，有频繁增删的场景我便使用LinkedList来存储数据，因为它的效率更高"

       我 ："你确定吗？"

       A同学："我确定（这面试官行不行，这八股文必背的还能有错？）"

• 实践

       检验真理的唯一标准就是开整

    //LinkedList访问
    private static void linkedListGet(int elementCount, int loopCount) {
        List list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new));
        IntStream.rangeClosed(1, loopCount).forEach(i -> list.get(ThreadLocalRandom.current().nextInt(elementCount)));
    }
 
    //ArrayList访问
    private static void arrayListGet(int elementCount, int loopCount) {
        List list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));
        IntStream.rangeClosed(1, loopCount).forEach(i -> list.get(ThreadLocalRandom.current().nextInt(elementCount)));
    }
 
    //LinkedList插入
    private static void linkedListAdd(int elementCount, int loopCount) {
        List list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new));
        IntStream.rangeClosed(1, loopCount).forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount),1));
    }
 
    //ArrayList插入
    private static void arrayListAdd(int elementCount, int loopCount) {
        List list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));
        IntStream.rangeClosed(1, loopCount).forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount),1));
    }

        //元素个数10W
        int elementCount = 100000;
        //循环次数10W
        int loopCount = 100000;
        StopWatch getWatch = new StopWatch();
        getWatch.start("linkedListGet");
        linkedListGet(elementCount, loopCount);
        getWatch.stop();
        getWatch.start("arrayListGet");
        arrayListGet(elementCount, loopCount);
        getWatch.stop();
        System.out.println(getWatch.prettyPrint());
 
        StopWatch addWatch = new StopWatch();
        addWatch.start("linkedListAdd");
        linkedListAdd(elementCount, loopCount);
        addWatch.stop();
        addWatch.start("arrayListAdd");
        arrayListAdd(elementCount, loopCount);
        addWatch.stop();
        System.out.println(addWatch.prettyPrint());

StopWatch '': running time = 5798625399 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
5789125500  100%   linkedListGet
009499899  00%   arrayListGet
 
StopWatch '': running time = 27658489400 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
26271657500  95%   linkedListAdd
1386831900  05%   arrayListAdd

        可以看到 LinkedList 无论是查询还是插入， 完败

• 总结

        通过查看LinkedList 源码发现，插入操作的时间复杂度是 O(1) 的前提是，已经获得要插入节点的指针。但在实现的时候，我们需要先遍历获取到该节点的 Node，然后再执行插入操作，前者也是有开销的，不可能只考虑插入操作本身的代价

        最后以一个讽刺的图作为结尾