GcsSloop

Just do IT later.

嗨,我是 GcsSloop,一名来自2.5次元的魔法师,Android自定义View系列文章作者,非著名程序员。


欢迎来到我的魔法世界!

ArrayList与LinkedList遍历性能比较

用实例测试ArrayList与LinkedList遍历性能。

结构差别:

我们常用的List有两种,ArrayList和LinkedList,虽然两者都是LIst,但由于内部存储结构的不同,使用不同的遍历方法性能却是千差万别的。

List 存储结构 特点
ArrayList 数组结构 可以根据下标直接取值。
LinkedList 链表结构 如果需要寻找某一个下标的数值必须从头遍历。

常见做法:

我们在遍历List的时候可能会这样做(从C语言上带来的习惯):

public void loopList(List<Integer> lists) {
    for (int i=0; i< lists.size(); i++) {
        Integer integer = lists.get(i);
        // TODO 处理数据
    }
}

这种做法很直观,乍一看并没有什么问题,但是仔细分析一下就能知道,在这种情况下使用ArrayList与LinkedList性能是完全不同的。

List 循环时间复杂度 get(i)时间复杂度 总时间复杂度
ArrayList O(n) O(1) O(n)
LinkedList O(n) O(n) O(n2)

从时间复杂度上两者就直接差了一个数量级,可能这样说不明显,为了直观的表示,下面用代码测试处理10000条数据效率:

性能测试:

创建数据:

ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i=0; i<10000; i++){
    arrayList.add(i);
    linkedList.add(i);
}

测试For循环用时:

long startTime1=System.currentTimeMillis();   //获取开始时间
loopList(arrayList);
iteratorList(arrayList);
long endTime1=System.currentTimeMillis(); //获取结束时间
Log.i("Time", "For-ArrayList: "+(endTime1-startTime1)+"ms");

long startTime2=System.currentTimeMillis();   //获取开始时间
loopList(linkedList);
long endTime2=System.currentTimeMillis(); //获取结束时间
Log.i("Time", "For-LinkedList:"+(endTime2-startTime2)+"ms");

结果:

com.gcssloop.alltest I/Time: For-ArrayList: 20ms
com.gcssloop.alltest I/Time: For-LinkedList:648ms

可以看到,仅仅处理10000条数据两者所需时间简直不能比较,当数据量越来越大的时候,LinkedList必然会耗费更多时间。

处理办法:

我们在Java中有 迭代器(Iterator) 以及 ForEach 循环,可以用它们来替代掉这个原始的 for 循环。

迭代器(Iterator):

public void iteratorList(List<Integer> lists){
    Iterator<Integer> it = lists.iterator();
    while (it.hasNext()){
        Integer integer = it.next();
        // TODO 处理数据
    }
}

测试代码与上面类似,就省略了。

结果:

com.gcssloop.alltest I/Time: Iterator-ArrayList: 4ms
com.gcssloop.alltest I/Time: Iterator-LinkedList:6ms

可以看到,两者最终耗费时间差不多而且均有大幅度提升。

ForEach循环:

public void foreachList(List<Integer> lists){
    for (Integer i : lists) {
        // TODO 处理数据
    }
}

性能:

com.gcssloop.alltest I/Time: ForEach-ArrayList: 5ms
com.gcssloop.alltest I/Time: ForEach-LinkedList:5ms

由于 ForEach 循环底层使用的也是迭代器,所以和迭代器性能类似。

总结:

推荐使用 迭代器(Iterator) 和 ForEach 遍历 List,不要使用传统的 For 循环。

以下是测试处理10000条数据性能:

数值仅供参考,与运行环境相关,每次测试结果都可能稍有差别。

迭代方式 ArrayList LinkedList
For循环 20ms 648ms
Iterator 4ms 6ms
for-each循环 5ms 5ms

About Me

作者微博: @GcsSloop


如果你觉得我的文章对你有帮助的话,捐赠一些晶石,鼓励我继续研究!

¥ 捐赠晶石
最近的文章

安卓自定义View进阶-Matrix详解

这应该是目前最详细的一篇讲解Matrix的中文文章了,在上一篇文章Matrix原理中,我们对Matrix做了一个简单的了解,偏向理论,在本文中则会详细的讲解Matrix的具体用法,以及与Matr...…

CustomView

继续阅读
更早的文章

安卓自定义View进阶-Matrix原理

本文内容偏向理论,和 画布操作 有重叠的部分,本文会让你更加深入的了解其中的原理。本篇的主角Matrix,是一个一直在后台默默工作的劳动模范,虽然我们所有看到View背后都有着Matrix的功劳...…

CustomView

继续阅读