ArrayList和LinkedList的几种循环遍历方式及性能对比分析

主要介绍arraylist和linkedlist这两种list的五种循环遍历方式，各种方式的性能测试对比，根据arraylist和linkedlist的源码实现分析性能结果，总结结论。

通过本文你可以了解(1)list的五种遍历方式及各自性能 (2)foreach及iterator的实现 (3)加深对arraylist和linkedlist实现的了解。

阅读本文前希望你已经了解arraylist顺序存储和linkedlist链式的结构，本文不对此进行介绍。

1. list的五种遍历方式

下面只是简单介绍各种遍历示例(以arraylist为例)，各自优劣会在本文后面进行分析给出结论。

(1) for each循环

java

1

2

3

4

list<integer> list = new arraylist<integer>();

for (integer j : list) {

// use j

}

(2) 显示调用集合迭代器

for (iterator<integer> iterator = list.iterator(); iterator.hasnext();) {

iterator.next();

或

5

iterator<integer> iterator = list.iterator();

while (iterator.hasnext()) {

(3) 下标递增循环，终止条件为每次调用size()函数比较判断

for (int j = 0; j < list.size(); j++) {

list.get(j);

(4) 下标递增循环，终止条件为和等于size()的临时变量比较判断

int size = list.size();

for (int j = 0; j < size; j++) {

(5) 下标递减循环

for (int j = list.size() - 1; j >= 0; j--) {

在测试前大家可以根据对arraylist和linkedlist数据结构及iterator的了解，想想上面五种遍历方式哪个性能更优。

2、list五种遍历方式的性能测试及对比

以下是性能测试代码，会输出不同数量级大小的arraylist和linkedlist各种遍历方式所花费的时间。

arraylist和linkedlist循环性能对比测试代码

ps：如果运行报异常in thread “main” java.lang.outofmemoryerror: java heap space，请将main函数里面list size的大小减小。

其中getarraylists函数会返回不同size的arraylist，getlinkedlists函数会返回不同size的linkedlist。

looplistcompare函数会分别用上面的遍历方式1-5去遍历每一个list数组(包含不同大小list)中的list。

print开头函数为输出辅助函数。

测试环境为windows7 32位系统 3.2g双核cpu 4g内存，java 7，eclipse -xms512m -xmx512m

最终测试结果如下：

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

compare loop performance of arraylist

-----------------------------------------------------------------------

list size | 10,000 | 100,000 | 1,000,000 | 10,000,000

for each | 1 ms | 3 ms | 14 ms | 152 ms

for iterator | 0 ms | 1 ms | 12 ms | 114 ms

for list.size() | 1 ms | 1 ms | 13 ms | 128 ms

for size = list.size() | 0 ms | 0 ms | 6 ms | 62 ms

for j-- | 0 ms | 1 ms | 6 ms | 63 ms

compare loop performance of linkedlist

list size | 100 | 1,000 | 10,000 | 100,000

for each | 0 ms | 1 ms | 1 ms | 2 ms

for iterator | 0 ms | 0 ms | 0 ms | 2 ms

for list.size() | 0 ms | 1 ms | 73 ms | 7972 ms

for size = list.size() | 0 ms | 0 ms | 67 ms | 8216 ms

for j-- | 0 ms | 1 ms | 67 ms | 8277 ms

第一张表为arraylist对比结果，第二张表为linkedlist对比结果。

表横向为同一遍历方式不同大小list遍历的时间消耗，纵向为同一list不同遍历方式遍历的时间消耗。

ps：由于首次遍历list会稍微多耗时一点，for each的结果稍微有点偏差，将测试代码中的几个type顺序调换会发现，for each耗时和for iterator接近。

3、遍历方式性能测试结果分析

(1) foreach介绍

foreach是java se5.0引入的功能很强的循环结构，for (integer j : list)应读作for each int in list。

for (integer j : list)实现几乎等价于

while(iterator.hasnext()) {

integer j = iterator.next();

下面的分析会将foreach和显示调用集合迭代器两种遍历方式归类为iterator方式，其他三种称为get方式遍历。

使用foreach结构的类对象必须实现了iterable接口，java的collection继承自此接口，list实现了collection，这个接口仅包含一个函数，源码如下：

package java.lang;

import java.util.iterator;

/**

* implementing this interface allows an object to be the target of

* the "foreach" statement.

*

* @param <t> the type of elements returned by the iterator

* @since 1.5

*/

public interface iterable<t> {

* returns an iterator over a set of elements of type t.

* @return an iterator.

iterator<t> iterator();

iterator()用于返回一个iterator，从foreach的等价实现中我们可以看到，会调用这个函数得到iterator，再通过iterator的next()得到下一个元素，hasnext()判断是否还有更多元素。iterator源码如下：

public interface iterator<e> {

boolean hasnext();

e next();

void remove();

(2) arraylist遍历方式结果分析

从上面我们可以看出：

a. 在arraylist大小为十万之前，五种遍历方式时间消耗几乎一样

b. 在十万以后，第四、五种遍历方式快于前三种，get方式优于iterator方式，并且

用临时变量size取代list.size()性能更优。我们看看arraylist中迭代器iterator和get方法的实现

private class itr implements iterator<e> {

int cursor; // index of next element to return

int lastret = -1; // index of last element returned; -1 if no such

int expectedmodcount = modcount;

public boolean hasnext() {

return cursor != size;

@suppresswarnings("unchecked")

public e next() {

checkforcomodification();

int i = cursor;

if (i >= size)

throw new nosuchelementexception();

object[] elementdata = arraylist.this.elementdata;

if (i >= elementdata.length)

throw new concurrentmodificationexception();

cursor = i + 1;

return (e) elementdata[lastret = i];

……

public e get(int index) {

rangecheck(index);

return elementdata(index);

从中可以看出get和iterator的next函数同样通过直接定位数据获取元素，只是多了几个判断而已。

c . 从上可以看出即便在千万大小的arraylist中，几种遍历方式相差也不过50ms左右，且在常用的十万左右时间几乎相等，考虑foreach的优点，我们大可选用foreach这种简便方式进行遍历。

(3) linkedlist遍历方式结果分析

a 在linkedlist大小接近一万时，get方式和iterator方式就已经差了差不多两个数量级，十万时iterator方式性能已经远胜于get方式。

我们看看linkedlist中迭代器和get方法的实现

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

private class listitr implements listiterator<e> {

private node<e> lastreturned = null;

private node<e> next;

private int nextindex;

private int expectedmodcount = modcount;

listitr(int index) {

// assert ispositionindex(index);

next = (index == size) ? null : node(index);

nextindex = index;

return nextindex < size;

if (!hasnext())

lastreturned = next;

next = next.next;

nextindex++;

return lastreturned.item;

checkelementindex(index);

return node(index).item;

* returns the (non-null) node at the specified element index.

node<e> node(int index) {

// assert iselementindex(index);

if (index < (size >> 1)) {

node<e> x = first;

for (int i = 0; i < index; i++)

x = x.next;

return x;

} else {

node<e> x = last;

for (int i = size - 1; i > index; i--)

x = x.prev;

从上面代码中可以看出linkedlist迭代器的next函数只是通过next指针快速得到下一个元素并返回。而get方法会从头遍历直到index下标，查找一个元素时间复杂度为哦o(n)，遍历的时间复杂度就达到了o(n2)。

所以对于linkedlist的遍历推荐使用foreach，避免使用get方式遍历。

(4) arraylist和linkedlist遍历方式结果对比分析

从上面的数量级来看，同样是foreach循环遍历，arraylist和linkedlist时间差不多，可将本例稍作修改加大list size会发现两者基本在一个数量级上。

但arraylist get函数直接定位获取的方式时间复杂度为o(1)，而linkedlist的get函数时间复杂度为o(n)。

再结合考虑空间消耗的话，建议首选arraylist。对于个别插入删除非常多的可以使用linkedlist。

4、结论总结

通过上面的分析我们基本可以总结下：

(1) 无论arraylist还是linkedlist，遍历建议使用foreach，尤其是数据量较大时linkedlist避免使用get遍历。

(2) list使用首选arraylist。对于个别插入删除非常多的可以使用linkedlist。

(3) 可能在遍历list循环内部需要使用到下标，这时综合考虑下是使用foreach和自增count还是get方式。