不要轻易使用LinkList------ArrayList与LinkList速度测试

不念不忘少年蓝@ 2023-02-14 15:39 60阅读 0赞

在Java中，ArrayList的数据结构为数组，LinkList数据结构为链表。如果我们学过算法与数据结构，我们可以很快得到以下结论：

对于数组，随机元素访问的时间复杂度是 O(1)，元素插入操作是 O(n)；

对于链表，随机元素访问的时间复杂度是 O(n)，元素插入操作是 O(1)。

因此，我们会认为在大量的元素插入、很少的随机访问的业务场景下，是不是就应该使用 LinkedList 呢。其实不对，通过下面的例子我们来演示一下在不同数据量下，ArrayList和LinkList的随机访问和插入的性能。

//LinkedList访问
    private static void linkedListGet(int elementCount, int loopCount) {
        List<Integer> 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<Integer> 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<Integer> 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<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));
        IntStream.rangeClosed(1, loopCount).forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount),1));
    }

测试代码如下，10万个元素，循环10万次

int elementCount = 100000;
    int loopCount = 100000;
    StopWatch stopWatch = new StopWatch();
    stopWatch.start("linkedListGet");
    linkedListGet(elementCount, loopCount);
    stopWatch.stop();
    stopWatch.start("arrayListGet");
    arrayListGet(elementCount, loopCount);
    stopWatch.stop();
    System.out.println(stopWatch.prettyPrint());
    
    
    StopWatch stopWatch2 = new StopWatch();
    stopWatch2.start("linkedListAdd");
    linkedListAdd(elementCount, loopCount);
    stopWatch2.stop();
    stopWatch2.start("arrayListAdd");
    arrayListAdd(elementCount, loopCount);
    stopWatch2.stop();
    System.out.println(stopWatch2.prettyPrint());

对于结果，你可能会很奇怪。在随机访问方面，我们看到了ArrayList的绝对优势，而在随机插入方面，ArrayList也占据了巨大的优势：

10W：
    StopWatch '': running time (millis) = 4520
    -----------------------------------------
    ms     %     Task name
    -----------------------------------------
    04509  100%  linkedListGet
    00011  000%  arrayListGet
    
    StopWatch '': running time (millis) = 28404
    -----------------------------------------
    ms     %     Task name
    -----------------------------------------
    26570  094%  linkedListAdd
    01834  006%  arrayListAdd

我还测试了20W，50W，100W的数据量和操作量下的结果

20W：
    StopWatch '': running time (millis) = 23972
    -----------------------------------------
    ms     %     Task name
    -----------------------------------------
    23955  100%  linkedListGet
    00017  000%  arrayListGet
    
    StopWatch '': running time (millis) = 157245
    -----------------------------------------
    ms     %     Task name
    -----------------------------------------
    149343  095%  linkedListAdd
    07902  005%  arrayListAdd
    
    
    50W ：StopWatch '': running time (millis) = 175061
    -----------------------------------------
    ms     %     Task name
    -----------------------------------------
    175020  100%  linkedListGet
    00041  000%  arrayListGet
    
    StopWatch '': running time (millis) = 2164864
    -----------------------------------------
    ms     %     Task name
    -----------------------------------------
    2115619  098%  linkedListAdd
    49245  002%  arrayListAdd
    
    100W:
    
    StopWatch '': running time (millis) = 721593
    -----------------------------------------
    ms     %     Task name
    -----------------------------------------
    721508  100%  linkedListGet
    00085  000%  arrayListGet
    
    StopWatch '': running time (millis) = 8900864
    -----------------------------------------
    ms     %     Task name
    -----------------------------------------
    8646038  097%  linkedListAdd
    254826  003%  arrayListAdd

为什么会出现这种情况呢？我们查看源码可以发现，虽然你插入的时间复杂度为O(1)，但是在插入之前你要先找到这个节点，这个操作是通过遍历来实现的。因此，对于插入，LinkList的时间复杂度也是O（n），不能只考虑插入操作的成本。而且，由于CPU缓存和内存连续性等问题，链表这种数据结构的实现方式对性能并不友好，即使在它最擅长的场景都不一定可以发挥威力。