Java容器——ArrayList VS LinkedList(Java9) 性能比较

时间:2022-10-27 19:16:22

    ArrayList和LinkedList都继承自List, 内在实现机制有所不同,关于区别方面已经有很多优秀的文章进行了介绍。本文从实践角度出发,对比两种List在不同操作中的性能,便于读者在特定场景中参考选型。由于电脑配置,JDK版本,IDE等会导致测试结果又出入甚至有结论不太一致的结果,本文的试验结果仅具备一定的参考价值。

    一 插入数据

    以同样的方式向两种List中插入数据,首先插入简单类型数据,这里插入简单字符串。表中数据以毫秒为单位,不到1毫秒的近似为1毫秒。

     /**
     * add element for List
     * @param sourceArray  source element array
     * @param list  list to add element
     */
    public void setEleForList(Object[] sourceArray, List list){
        int len = sourceArray.length;
        for (int i = 0; i < len; i++){
            list.add(sourceArray[i]);
        }
    }
表1 两种List插入性能对比
操作条数 ArrayList         LinkedList
1000 6     1
10000 13     1
100000 10 19
1000000 24 45
1000000 347     939

    表中的数据时间单位都是毫秒。明显可见,在数量较少的情况下,LinkedList有绝对的速度优势,超过100000条以上,ArrayList就占据了明显的优势。

二 读取List数据

    查找数据是容器的一项重要操作,通常而言取数据要比存入和修改来得更频繁。在遍历列表方面,二者对比如何呢。这里采用两种读取的方式,一种是顺序读取,一种是随机选择。

     /**
     * iterate through list
     *
     * @param list list to iterate through
     */
    public void getAllEleFromList(List list){
        int size = list.size();
        for (int i = 0; i < size; i++){
            Object object = list.get(i);
        }
    }
表2 两种List顺序遍历性能对比
操作条数 ArrayList         LinkedList
1000 1 2
10000 1 34
100000 2 5435
  /**
     * get random elements form list
     *
     * @param list list to get from
     * @param num number of elements to get
     */
    public void getRandomEleFromList(List list,int num){
        int size = list.size();
        Random random = new Random();
        for (int i = 0; i < num; i++){
            Object object = list.get(random.nextInt(size - 1));
        }
    }
表3 两种List随机遍历性能对比
操作条数 ArrayList         LinkedList
1000 1 1
10000 3 40
100000 6

6420

    List的顺序遍历有多重方式,二者统一采取了按下标递增遍历的方式进行。随机读取的次数和列表的长度相同,在测试时间上需要加上产生随机数的时间。鉴于二者在十万条数据上差别已经巨大,不再继续测试。
   

三 删除List数据

    对List的删除操作是容易产生异常的地方,日常操作时要格外小心。这里随机对列表已有元素进行删除。删除的数量为列表长度的十分之一。

 /**
     * remove random number elements form list
     *
     * @param list list to remove
     * @param num  number to remove
     */
    public void removeEleFromList(List list, int num){
        int size = list.size();
        Random random = new Random();
        for (int i = 0; i < num; i++){
            Object object = list.remove(random.nextInt(size - 1 - i));
        }
    }
表4 两种List删除性能对比
操作条数 ArrayList         LinkedList
1000 1 1
10000 2 8
100000 45 893
1000000 6261 73234

    可见,和插入、查询相比,List的删除是最耗时间的操作也最容易出问题。

四 清除List数据

    有建立,就有销毁,如果销毁List采用上面逐个删除的方式,那这个时间代价是不能接受的。系统采用的清除List的方式要简便快速许多,这里就不贴系统代码了,直接看时间对比。

表5 两种List销毁对比
操作条数 ArrayList         LinkedList
1000 1 1
10000 1 1
100000 1 3
1000000 3 6
1000000 11 42

总结

    通过测试数据可得,在大部分场景下,ArrayList是优于LinkedList的,只有在少量数据插入时,LinkedList有一定优势。

    本文对List的重要操作性能进行了对比,List接口还有很多实现方法,感兴趣的话可以自己亲手实践。

    理论要联系实际,从实践中总结理论。造成测试结果的原因是多方面的,不仅仅依赖接口的实现,与参数类型,操作系统,虚拟机都可能有关,后面我们会从源码的角度解读测试结果。