老徐和阿珍的故事：ArrayList和LinkedList的效率到底哪个高？

雨点打透心脏的1/2处 2023-09-30 11:17 15阅读 0赞

> **人物背景**：
> 
> **老徐**，男，本名徐福贵，从事Java相关研发工作多年，职场老油条，摸鱼小能手，虽然岁数不大但长的比较着急，人称老徐。据说之前炒某币败光了所有家产，甚至现在还有欠债。
> 
> **阿珍**，女，本名陈家珍，刚刚入职不久的实习生，虽然是职场菜鸟但聪明好学。据说是学校的四大校花之一，追求她的人从旺角排到了铜锣湾，不过至今还单身。

老徐问道：“阿珍，你知道ArrayList和LinkedList的区别吗？”

阿珍微微一笑，说：“这也太小儿科了，ArrayList是基于数组实现，LinkedList是基于链表实现。”

老徐竖起了大拇指，说：“不错，有进步！那你知道ArrayList和LinkedList的效率到底哪个高？”

阿珍回答：“这也难不倒我，这要分不同情况的。在新增、删除元素时，LinkedList的效率要高于ArrayList，而在遍历的时候，ArrayList的效率要高于LinkedList。”

老徐反问到：“不一定哦。在新增、删除元素时，LinkedList的效率有可能低于ArrayList，而在遍历的时候，ArrayList的效率有可能低于LinkedList。”

阿珍回答：“不可能，绝对不可能，书上都是这么写的。”

老徐得意地笑了，说：“实践是检验真理的唯一标准。趁着老板不在，咱两写个程序实践一下。”

#### ArrayList和LinkedList的新增元素对比 ####

首先，写一段计算新增元素耗时的代码：

/**
     * 从List的头部新增元素
     * @param list list
     * @param count 新增元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static long addHeader(List<String> list, int count) {
        
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
        
            list.add(0, "onemore-" + i);
        }
        long end = System.nanoTime();
        return (end - start) / 1000000;
    }
    
    /**
     * 从List的中部新增元素
     * @param list list
     * @param count 新增元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static long addMiddle(List<String> list, int count) {
        
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
        
            list.add(list.size() / 2, "onemore-" + i);
        }
        long end = System.nanoTime();
        return (end - start) / 1000000;
    }
    
    /**
     * 从List的尾部新增元素
     * @param list list
     * @param count 新增元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static long addTail(List<String> list, int count) {
        
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
        
            list.add("onemore-" + i);
        }
        long end = System.nanoTime();
        return (end - start) / 1000000;
    }

然后，我们把新增元素的个数设置为50000，对比一下：

public static void main(String[] args) {
        
        int count = 50000;
    
        System.out.println("从ArrayList的头部新增元素：" + addHeader(new ArrayList<>(count), count) + "ms");
        System.out.println("从LinkedList的头部新增元素：" + addHeader(new LinkedList<>(), count) + "ms");
    
        System.out.println("从ArrayList的中部新增元素：" + addMiddle(new ArrayList<>(count), count) + "ms");
        System.out.println("从LinkedList的中部新增元素：" + addMiddle(new LinkedList<>(), count) + "ms");
    
        System.out.println("从ArrayList的尾部新增元素：" + addTail(new ArrayList<>(count), count) + "ms");
        System.out.println("从LinkedList的尾部新增元素：" + addTail(new LinkedList<>(), count) + "ms");
    }

运行结果如下：

ArrayList从头部新增元素：204ms
    LinkedList从头部新增元素：17ms
    ArrayList从中部新增元素：71ms
    LinkedList从中部新增元素：8227ms
    ArrayList从尾部新增元素：13ms
    LinkedList从尾部新增元素：21ms

我们可以看出，从头部新增元素时，ArrayList的效率低于LinkedList；从中部新增元素时，ArrayList的效率高于LinkedList；从尾部新增元素时，ArrayList的效率高于LinkedList。

阿珍惊呆了，说：“怎么可能？这是为什么呀？”老徐回答：“我来帮你简单分析一下。”

ArrayList是基于数组实现的，在添加元素到数组头部的时候，在添加元素之前需要把头部以后的元素一个一个地往后挪，所以效率很低；而LinkedList是基于链表实现，从头部添加元素的时候，通过头部指针就可以直接添加，所以效率很高。

ArrayList在添加元素到数组中间的时候，同样有部分元素需要一个一个地往后挪，所以效率也不是很高；而LinkedList从中部添加元素的时候，是添加元素最低效率的，因为靠近中间位置，在添加元素之前需要循环查找遍历部分元素，所以效率很低。

ArrayList从尾部添加元素的时候，不需要挪动任何元素，直接把元素放入数组，效率非常高。而LinkedList虽然不需要循环查找遍历元素，但LinkedList中多了实列化节点对象和变换指针指向的过程，所以效率较低一些。

当然，这里有一个大前提，就是ArrayList初始化容量足够，不需要动态扩容数组容量。所以，在我们的日常开发中，**最好指定ArrayList的初始化容量**。

#### ArrayList和LinkedList的删除元素对比 ####

首先，写一段计算删除元素耗时的代码：

/**
     * 从List的头部删除元素
     * @param list list
     * @param count 删除元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double deleteHeader(List<String> list, int count) {
        
        for (int i = 0; i < count; i++) {
        
            list.add("onemore-" + i);
        }
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
        
            list.remove(0);
        }
        long end = System.nanoTime();
        return (end - start) / 1000000.0;
    }
    
    /**
     * 从List的中部删除元素
     * @param list list
     * @param count 删除元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double deleteMiddle(List<String> list, int count) {
        
        for (int i = 0; i < count; i++) {
        
            list.add("onemore-" + i);
        }
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
        
            list.remove(list.size() / 2);
        }
        long end = System.nanoTime();
        return (end - start) / 1000000.0;
    }
    
    /**
     * 从List的尾部删除元素
     * @param list list
     * @param count 删除元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double deleteTail(List<String> list, int count) {
        
        for (int i = 0; i < count; i++) {
        
            list.add("onemore-" + i);
        }
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
        
            list.remove(list.size() - 1);
        }
        long end = System.nanoTime();
        return (end - start) / 1000000.0;
    }

然后，我们把删除元素的个数设置为50000，对比一下：

public static void main(String[] args) {
        
        int count = 50000;
    
        System.out.println("从ArrayList的头部删除元素：" + deleteHeader(new ArrayList<>(count), count) + "ms");
        System.out.println("从LinkedList的头部删除元素：" + deleteHeader(new LinkedList<>(), count) + "ms");
    
        System.out.println("从ArrayList的中部删除元素：" + deleteMiddle(new ArrayList<>(count), count) + "ms");
        System.out.println("从LinkedList的中部删除元素：" + deleteMiddle(new LinkedList<>(), count) + "ms");
    
        System.out.println("从ArrayList的尾部删除元素：" + deleteTail(new ArrayList<>(count), count) + "ms");
        System.out.println("从LinkedList的尾部删除元素：" + deleteTail(new LinkedList<>(), count) + "ms");
    
    }

运行结果如下：

从ArrayList的头部删除元素：260.7014ms
    从LinkedList的头部删除元素：14.2948ms
    从ArrayList的中部删除元素：95.9073ms
    从LinkedList的中部删除元素：3602.6931ms
    从ArrayList的尾部删除元素：1.6261ms
    从LinkedList的尾部删除元素：3.9645ms

我们可以看出，从头部删除元素时，ArrayList的效率低于LinkedList；从中部删除元素时，ArrayList的效率高于LinkedList；从尾部删除元素时，ArrayList的效率高于LinkedList。

阿珍抢着说：“删除元素这个我知道，和新增元素的原理差不多。”老徐回答：“既然你知道了，我就不啰嗦了，我们继续看遍历元素。”

#### ArrayList和LinkedList的遍历元素对比 ####

遍历元素一般有两种方式：for循环和foreach，写一段计算这两种遍历方式耗时的代码：

/**
     * 通过for循环遍历List
     *
     * @param list  list
     * @param count 遍历元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double getByFor(List<String> list, int count) {
        
        for (int i = 0; i < count; i++) {
        
            list.add("onemore-" + i);
        }
        String name = "万猫学社";
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
        
            if (name.equals(list.get(i))) {
        
                System.out.println(name);
            }
        }
        long end = System.nanoTime();
        return (end - start) / 1000000.0;
    }
    
    /**
     * 通过foreach遍历List
     *
     * @param list  list
     * @param count 遍历元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double getByForeach(List<String> list, int count) {
        
        for (int i = 0; i < count; i++) {
        
            list.add("onemore-" + i);
        }
        String name = "万猫学社";
        long start = System.nanoTime();
        for (String str : list) {
        
            if (name.equals(str)) {
        
                System.out.println(name);
            }
        }
        long end = System.nanoTime();
        return (end - start) / 1000000.0;
    }

然后，我们把遍历元素的个数设置为50000，对比一下：

public static void main(String[] args) {
        
        int count = 50000;
    
        System.out.println("通过for循环遍历ArrayList：" + getByFor(new ArrayList<>(count), count) + "ms");
        System.out.println("通过for循环遍历LinkedList：" + getByFor(new LinkedList<>(), count) + "ms");
    
        System.out.println("通过foreach遍历ArrayList：" + getByForeach(new ArrayList<>(count), count) + "ms");
        System.out.println("通过foreach遍历LinkedList：" + getByForeach(new LinkedList<>(), count) + "ms");
    }

运行结果如下：

通过for循环遍历ArrayList：3.4403ms
    通过for循环遍历LinkedList：3563.1219ms
    通过foreach遍历ArrayList：3.7388ms
    通过foreach遍历LinkedList：3.7953ms

我们可以看到，通过for循环遍历时，ArrayList的效率高于LinkedList，而且LinkedList的效率极低；通过foreach遍历时，ArrayList的效率和LinkedList相差不大。

老徐：“阿珍，你知道为什么for循环遍历LinkedList的效率那么低吗？”

阿珍：“因为LinkedList基于链表实现的，每一次for循环都要遍历找到对应的节点，所以严重影响了遍历的效率；而ArrayList直接可以通过数组下标直接找到对应的元素，所以for循环效率非常高。对不对？”

老徐：“是的，所以我们**不要使用for循环遍历LinkedList**。”

#### 总结 ####

ArrayList是基于数组实现，LinkedList是基于链表实现。

在ArrayList初始化容量足够的情况下，从头部新增元素时，ArrayList的效率低于LinkedList；从中部新增元素时，ArrayList的效率高于LinkedList；从尾部新增元素时，ArrayList的效率高于LinkedList。

从头部删除元素时，ArrayList的效率低于LinkedList；从中部删除元素时，ArrayList的效率高于LinkedList；从尾部删除元素时，ArrayList的效率高于LinkedList。

通过for循环遍历时，ArrayList的效率高于LinkedList，而且LinkedList的效率极低；通过foreach遍历时，ArrayList的效率和LinkedList相差不大。

> 最后，谢谢你这么帅，还给我**点赞**和**关注**。