ArrayList与LinkedList遍历性能比较

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

结构差别:

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

Lis t 存储结构 特点

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 LinkedListFor

循环 20ms6 48ms

Iterator 4ms 6ms

for-each 循环 5ms 5ms