ArrayList和LinkedList的三种遍历方式及性能效率对比

  • A+
所属分类:Java

在Java语言里,特别是在Android App开发过程中,我们会用到许多的数据结构,而List绝对是其中最常用的数据结构之一。

List是一个接口,本身并不能通过new的方式来初始化,你必须去初始化一个List的实现。而常见的2种实现是ArrayList和LinkedList,前者可能大家用得更多,但是后者也很有用。很多时候,我们需要对List进行遍历,那么如何对List进行遍历呢?

一般来说有3种方法:for循环,foreach(增强型for)循环,以及Iterator迭代器。这3种循环性能有一定差别,而且在使用中也有差别。下面我们分别对ArrayList和LinkedList进行3种遍历,并观测其性能表现。

先初始化2个List,一个是ArrayList,另一个则是LinkedList,并对它们进行数据填充:

下面给出每种遍历的代码实现:

1、下标递增的基本for循环:

2、增强型for循环,即foreach遍历:

3、迭代器Iterator遍历:

分别测试每种遍历的时间,为了使测试更准确,尽量每种测试都多跑几次,并且会把3种遍历方式的顺序颠倒几次,然后再把List的size值往大了更改,看看随着容量的增加,遍历时间会有怎样的变化。本次测试分为2大组,分别是ArrayList和LinkedList。
ArrayList遍历时间(单位:ms)

ArrayList容量 5000 10000 100000
普通for循环遍历 0 0 1
foreach遍历 1 1 15
Iterator迭代器遍历 0 1 2

LinkedList遍历时间(单位:ms)

LinkedList容量 5000 10000 100000
普通for循环遍历 30 116 16518
foreach遍历 1 2 15
Iterator迭代器遍历 0 0 4

本次测试环境是在Android手机中进行,手机为Nexus 6,系统为Android 7.1.1,手机CPU为高通骁龙805,RAM为3GB。编译JDK为1.8.0_131。之所以写这些,是因为不同的测试环境下会得到不同的结果,但在具体的对比方面,应该结果是一致的。

我们可以看到,对于ArrayList来说,3种遍历方式性能差距不大,当ArrayList的容量很大的时候,foreach的耗时似乎稍微长一些但也在15ms以内。所以使用哪一种在性能方面都不会差,选择一种你熟悉的比较方便的方式就可以。一般来说,普通的通过下标递增的循环遍历最常用,而foreach则比较简洁又不易出错(因为foreach遍历不会有越界)。

而对于LinkedList来说情况有所不同,当LinkedList的size很小的时候,3种遍历都差不多,但就算是5000这样一个不算太大的容量,普通for循环遍历的时间俨然已经比foreach和Iterator方式明显高了一个数量级。而当容量达到10万的时候,foreach耗时只有10几毫秒,Iterator迭代器甚至依然耗时是个位数,而此时的普通for循环耗时高达16秒之多,在Android里这已经造成好几次ANR了!显然,LinkedList遍历一定要用foreach或者迭代器,除非你能确定容量小到可以忽略这点性能差距。

综合来说,无论是ArrayList还是LinkedList,使用foreach和Iterator进行遍历,都一定不会有错。如果你还需要使用下标,那么可以自定义一个int变量,每次取值的时候都进行++操作。另外,如果需要在遍历的时候进行remove或者add操作,那么务必使用Iterator迭代器来操作。

KaelLi

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: