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方式。