ArrayList和LinkedList的幾種循環(huán)遍歷方式及性能對比分析

1、根據(jù)ArrayList和LinkedList的源碼實(shí)現(xiàn)分析性能結(jié)果，總結(jié)結(jié)論。通過本文你可以了解(1)List的五種遍歷方式及各自性能(2)foreach及Iterator的實(shí)現(xiàn)(3)加深對ArrayList和LinkedList實(shí)現(xiàn)的了解。閱讀本文前希望你已經(jīng)了解ArrayList順序存儲和LinkedList鏈?zhǔn)降臉?gòu)造，本文不對此進(jìn)展介紹。相關(guān)：HashMap循環(huán)遍歷方式及其性能比照1.List的五種遍歷方式下面只是簡單介紹各種遍歷例如(以ArrayList為例)，各自優(yōu)劣會在本文后面進(jìn)展分析給出結(jié)論。foreach循環(huán)Java3dIjT11 Listlist=newArrayList()

2、;2 for(Integerj:list)3 /usej4 (2)顯示調(diào)用集合迭代器JavaI3山/1 Listlist=newArrayList();2 for(Iteratoriterator=list.iterator();iterator.hasNext();)3 iterator.next();4 或JavaIid/1 Listlist=newArrayList();2 Iteratoriterator=list.iterator();3 while(iterator.hasNext()4 iterator.next();5 (3)下標(biāo)遞增循環(huán)，終止條件為每次調(diào)用sizeO數(shù)比擬判斷

3、JavaI3山/1 Listlist=newArrayList();2 for(intj=0;jlist.size();j+)3 list.get(j);4 (4)下標(biāo)遞增循環(huán)，終止條件為和等于size()的臨時(shí)變量比擬判斷JavaI3_j/1 Listlist=newArrayList();2 intsize=list.size();3 for(intj=0;jsize;j+)4 list.get(j);5 (5)下標(biāo)遞減循環(huán)Java1 Listlist=newArrayList();2 for(intj=list.size()-1;j=0;j-)3 list.get(j);4 在測試前大家

4、可以根據(jù)對ArrayList和LinkedList數(shù)據(jù)構(gòu)造及Iterator的了解，想想上面五種遍歷方式哪個(gè)性能更優(yōu)。2、List五種遍歷方式的性能測試及比照以下是性能測試代碼，會輸出不同數(shù)量級大小的ArrayList和LinkedList各種遍歷方式所花費(fèi)的時(shí)間。ArrayList和LinkedList循環(huán)性能比照測試代碼1pareloopperformanceofArrayList23listsize|10,000|100,000|1,000,000|10,000,00045foreach|1ms|3ms|14ms|152ms67foriterator|0ms|1ms|12ms|114ms

5、89forlist.size()|1ms|1ms|13ms|128ms1011forsize=list.size()|0ms|0ms|6ms|62ms1213forj-|0ms|1ms|6ms|63ms141516pareloopperformanceofLinkedList1718listsize|100|1,000|10,000|100,0001920foreach10ms|1ms|1ms|2ms2122foriterator|0ms|0ms|0ms|2ms2324forlist.size()|0ms|1ms|73ms|7972ms2526forsize=list.size()|0ms|0

6、ms|67ms|8216ms2728forj-|0ms|1ms|67ms|8277ms29第一X表為ArrayList比照結(jié)果，第二X表為LinkedList比照結(jié)果。表橫向?yàn)橥槐闅v方式不同大小list遍歷的時(shí)間消耗，縱向?yàn)橥籰ist不同遍歷方式遍歷的時(shí)間消耗。PS:由于首次遍歷List會稍微多耗時(shí)一點(diǎn)，foreach的結(jié)果稍微有點(diǎn)偏差，將測試代碼中的幾個(gè)Type順序調(diào)換會發(fā)現(xiàn)，foreach耗時(shí)和fo門terator接近。3、遍歷方式性能測試結(jié)果分析(1)foreach介紹foreach是JavaSE5.0H入的功能很強(qiáng)白循環(huán)構(gòu)造，for(Integerj:list)應(yīng)讀作foreach

7、intinlist。for(Integerj:list)實(shí)現(xiàn)幾乎等價(jià)于JavaI3山/1 Iteratoriterator=list.iterator();2 while(iterator.hasNext()3 Integerj=iterator.next();4 下面的分析會將foreach和顯示調(diào)用集合迭代器兩種遍歷方式歸類為Iterator方式，其他三種稱為get方式遍歷。這時(shí)我們已經(jīng)發(fā)現(xiàn)foreach的一大好處，簡單一行實(shí)現(xiàn)了四行的功能，使得代碼簡潔美觀，另一大好處是相對于下標(biāo)循環(huán)而言的，foreach不必關(guān)心下標(biāo)初始值和終止值及越界等，所以不易出錯(cuò)。Effective-Java中推薦

8、使用此種寫法遍歷，本文會驗(yàn)證這個(gè)說法。使用foreach構(gòu)造的類對象必須實(shí)現(xiàn)了Iterable接口，Java的Collection繼承自此接口，List實(shí)現(xiàn)了Collection,這個(gè)接口僅包含一個(gè)函數(shù)，源碼如下：Javaad/1 packagejava.lang;23 importjava.util.Iterator;45 /*6 *Implementingthisinterfaceallowsanobjecttobethetargetof7 *theforeachstatement.8 *9 *paramthetypeofelementsreturnedbytheiterator10 *1

9、1 *since1.512 */13 publicinterfaceIterable1415 /*16 *ReturnsaniteratoroverasetofelementsoftypeT.17 *18 *returnanIterator.19 */20 Iteratoriterator。；21 iterator。用于返回一個(gè)Iterator,從foreach的等價(jià)實(shí)現(xiàn)中我們可以看到，會調(diào)用這個(gè)函數(shù)得到Iterator,再通過Iterator的next()得到下一個(gè)元素，hasNext()判斷是否還有更多元素。Iterator源碼如下：JavaI5,11jT11 publicinterfac

10、eIterator2 booleanhasNext();34 Enext();56 voidremove();7 (2)ArrayList遍歷方式結(jié)果分析1pareloopperformanceofArrayList23listsize|10,000|100,000|1,000,000|10,000,00045foreach|1ms|3ms|14ms|152ms67foriterator|0ms|1ms|12ms|114ms89forlist.size()|1ms|1ms|13ms|128ms1011forsize=list.size()|0ms|0ms|6ms|62ms1213forj-|0

11、ms|1ms|6ms|63ms14PS:由于首次遍歷List會稍微多耗時(shí)一點(diǎn)，foreach的結(jié)果稍微有點(diǎn)偏差，將測試代碼中的幾個(gè)Type順序調(diào)換會發(fā)現(xiàn)，foreach耗時(shí)和fo門terator接近。從上面我們可以看出：a.在ArrayList大小為十萬之前，五種遍歷方式時(shí)間消耗幾乎一樣b.在十萬以后，第四、五種遍歷方式快于前三種，get方式優(yōu)于Iterator方式，并且Java3山/1 intsize=list.size();2 for(intj=0;jsize;j+)3 list.get(j);4 用臨時(shí)變量size取彳弋list.size()f生能更優(yōu)。我們看看ArrayList中迭代器

12、Iterator和get方法的實(shí)現(xiàn)Java1privateclassItrimplementsIterator2 intcursor;/indexofnextelementtoreturn3 intlastRet=-1;/indexoflastelementreturned;-1ifnosuch4 intexpectedModCount=modCount;56 publicbooleanhasNext()7 returncursor!=size;8 910 SuppressWarnings(unchecked)11 publicEnext()12 checkForodification();1

13、3 inti=cursor;14 if(i=size)15 thrownewNoSuchElementException();16 Object口elementData=ArrayList.this.elementData;17 if(i=elementData.length)18 thrownewConcurrentModificationException();19 cursor=i+1;20 return(E)elementDatalastRet=i;21 2223 2425 publicEget(intindex)26 rangeCheck(index);2728 returnelem

14、entData(index);29 從中可以看出get和Iterator的next函數(shù)同樣通過直接定位數(shù)據(jù)獲取元素，只是多了幾個(gè)判斷而已。c.從上可以看出即便在千萬大小的ArrayList中，幾種遍歷方式相差也不過50ms左右，且在常用的十萬左右時(shí)間幾乎相等，考慮foreach的優(yōu)點(diǎn)，我們大可選用foreach這種簡便方式進(jìn)展遍歷。(3)LinkedList遍歷方式結(jié)果分析1pareloopperformanceofLinkedList23listsize|100|1,000|10,000|100,0005 for each10ms|1ms|1ms|2ms67foriterator|0ms|0

15、ms|0ms|2ms89forlist.size()|0ms|1ms|73ms|7972ms1011forsize=list.size()|0ms|0ms|67ms|8216ms1213forj-|0ms|1ms|67ms|8277ms14PS:由于首次遍歷List會稍微多耗時(shí)一點(diǎn)，foreach的結(jié)果稍微有點(diǎn)偏差，將測試代碼中的幾個(gè)Type順序調(diào)換會發(fā)現(xiàn)，foreach耗時(shí)和fo門terator接近。從上面我們可以看出：a在LinkedList大小接近一萬時(shí)，get方式和Iterator方式就已經(jīng)差了差不多兩個(gè)數(shù)量級，十萬時(shí)Iterator方式性能已經(jīng)遠(yuǎn)勝于get方式。我們看看LinkedL

16、ist中迭代器和get方法的實(shí)現(xiàn)JavaI5dI/1 privateclassListItrimplementsListIterator2 privateNodelastReturned=null;3 privateNodenext;4 privateintnextIndex;5 privateintexpectedModCount=modCount;67 ListItr(intindex)8 /assertisPositionIndex(index);9 next=(index=size)?null:node(index);10 nextIndex=index;11 1213 publicb

17、ooleanhasNext()14 returnnextIndexsize;15 1617 publicEnext()18 checkForodification();19 if(!hasNext()20 thrownewNoSuchElementException();2122 lastReturned=next;23 next=next.next;24 nextIndex+;25 returnlastReturned.item;26 2728 2930 publicEget(intindex)31 checkElementIndex(index);32 returnnode(index).

18、item;33 3435 /*36 *Returnsthe(non-null)Nodeatthespecifiedelementindex.37 */38 Nodenode(intindex)39 /assertisElementIndex(index);4041 if(index1)42 Nodex=first;43 for(inti=0;iindex;i+)44 x=x.next;45 returnx;46 else47 Nodex=last;48 for(inti=size-1;iindex;i-)49 x=x.prev;50 returnx;51 52 從上面代碼中可以看出LinkedList迭代器的next函數(shù)只是通過next指針快速得到下一個(gè)元素并返回。而get方法會從頭遍歷直到index下標(biāo)，查找一個(gè)元素時(shí)間復(fù)雜度為哦O(n),遍歷的時(shí)間復(fù)雜度就到達(dá)了O(n2)。所以對于LinkedList的遍歷推薦使用foreach,防止使用get方式遍歷。(4)ArrayList和LinkedList遍歷方式結(jié)果比照分析從上面的數(shù)量級來看，同樣是foreach循環(huán)遍歷，ArrayList和LinkedList時(shí)間差不多，可將本例稍作修改加大listsize會發(fā)現(xiàn)兩者根本在一個(gè)數(shù)量級上。但ArrayListget函數(shù)直