Java中ArrayList和LinkedList的遍历与性能分析
前言
通过本文你可以了解List的五种遍历方式及各自性能和foreach及Iterator的实现，加深对ArrayList和LinkedList实现的了解。下面来一起看看吧。
一、List的五种遍历方式
1、foreach循环
List<Integer>list=newArrayList<Integer>();
for(Integerj:list){
//usej
}
2、显示调用集合迭代器
List<Integer>list=newArrayList<Integer>();
for(Iterator<Integer>iterator=list.iterator();iterator.hasNext();){
iterator.next();
}
或
List<Integer>list=newArrayList<Integer>();
Iterator<Integer>iterator=list.iterator();
while(iterator.hasNext()){
iterator.next();
}
3、下标递增循环，终止条件为每次调用size()函数比较判断
List<Integer>list=newArrayList<Integer>();
for(intj=0;j<list.size();j++){
list.get(j);
}
4、下标递增循环，终止条件为和等于size()的临时变量比较判断
List<Integer>list=newArrayList<Integer>();
intsize=list.size();
for(intj=0;j<size;j++){
list.get(j);
}
5、下标递减循环
List<Integer>list=newArrayList<Integer>();
for(intj=list.size()-1;j>=0;j--){
list.get(j);
}
List五种遍历方式的性能测试及对比
以下是性能测试代码，会输出不同数量级大小的ArrayList和LinkedList各种遍历方式所花费的时间。
packagecn.trinea.java.test;
importjava.text.DecimalFormat;
importjava.util.ArrayList;
importjava.util.Calendar;
importjava.util.Iterator;
importjava.util.LinkedList;
importjava.util.List;
/**
*JavaLoopTest
*
*@authorwww.trinea.cn2013-10-28
*/
publicclassJavaLoopTest{
publicstaticvoidmain(String[]args){
System.out.print("compareloopperformanceofArrayList");
loopListCompare(getArrayLists(10000,100000,1000000,9000000));
System.out.print("\r\n\r\ncompareloopperformanceofLinkedList");
loopListCompare(getLinkedLists(100,1000,10000,100000));
}
publicstaticList<Integer>[]getArrayLists(int...sizeArray){
List<Integer>[]listArray=newArrayList[sizeArray.length];
for(inti=0;i<listArray.length;i++){
intsize=sizeArray[i];
List<Integer>list=newArrayList<Integer>();
for(intj=0;j<size;j++){
list.add(j);
}
listArray[i]=list;
}
returnlistArray;
}
publicstaticList<Integer>[]getLinkedLists(int...sizeArray){
List<Integer>[]listArray=newLinkedList[sizeArray.length];
for(inti=0;i<listArray.length;i++){
intsize=sizeArray[i];
List<Integer>list=newLinkedList<Integer>();
for(intj=0;j<size;j++){
list.add(j);
}
listArray[i]=list;
}
returnlistArray;
}
publicstaticvoidloopListCompare(List<Integer>...listArray){
printHeader(listArray);
longstartTime,endTime;
//Type1
for(inti=0;i<listArray.length;i++){
List<Integer>list=listArray[i];
startTime=Calendar.getInstance().getTimeInMillis();
for(Integerj:list){
//usej
}
endTime=Calendar.getInstance().getTimeInMillis();
printCostTime(i,listArray.length,"foreach",endTime-startTime);
}
//Type2
for(inti=0;i<listArray.length;i++){
List<Integer>list=listArray[i];
startTime=Calendar.getInstance().getTimeInMillis();
//Iterator<Integer>iterator=list.iterator();
//while(iterator.hasNext()){
//iterator.next();
//}
for(Iterator<Integer>iterator=list.iterator();iterator.hasNext();){
iterator.next();
}
endTime=Calendar.getInstance().getTimeInMillis();
printCostTime(i,listArray.length,"foriterator",endTime-startTime);
}
//Type3
for(inti=0;i<listArray.length;i++){
List<Integer>list=listArray[i];
startTime=Calendar.getInstance().getTimeInMillis();
for(intj=0;j<list.size();j++){
list.get(j);
}
endTime=Calendar.getInstance().getTimeInMillis();
printCostTime(i,listArray.length,"forlist.size()",endTime-startTime);
}
//Type4
for(inti=0;i<listArray.length;i++){
List<Integer>list=listArray[i];
startTime=Calendar.getInstance().getTimeInMillis();
intsize=list.size();
for(intj=0;j<size;j++){
list.get(j);
}
endTime=Calendar.getInstance().getTimeInMillis();
printCostTime(i,listArray.length,"forsize=list.size()",endTime-startTime);
}
//Type5
for(inti=0;i<listArray.length;i++){
List<Integer>list=listArray[i];
startTime=Calendar.getInstance().getTimeInMillis();
for(intj=list.size()-1;j>=0;j--){
list.get(j);
}
endTime=Calendar.getInstance().getTimeInMillis();
printCostTime(i,listArray.length,"forj--",endTime-startTime);
}
}
staticintFIRST_COLUMN_LENGTH=23,OTHER_COLUMN_LENGTH=12,TOTAL_COLUMN_LENGTH=71;
staticfinalDecimalFormatCOMMA_FORMAT=newDecimalFormat("#,###");
publicstaticvoidprintHeader(List<Integer>...listArray){
printRowDivider();
for(inti=0;i<listArray.length;i++){
if(i==0){
StringBuildersb=newStringBuilder().append("listsize");
while(sb.length()<FIRST_COLUMN_LENGTH){
sb.append("");
}
System.out.print(sb);
}
StringBuildersb=newStringBuilder().append("|").append(COMMA_FORMAT.format(listArray[i].size()));
while(sb.length()<OTHER_COLUMN_LENGTH){
sb.append("");
}
System.out.print(sb);
}
TOTAL_COLUMN_LENGTH=FIRST_COLUMN_LENGTH+OTHER_COLUMN_LENGTH*listArray.length;
printRowDivider();
}
publicstaticvoidprintRowDivider(){
System.out.println();
StringBuildersb=newStringBuilder();
while(sb.length()<TOTAL_COLUMN_LENGTH){
sb.append("-");
}
System.out.println(sb);
}
publicstaticvoidprintCostTime(inti,intsize,StringcaseName,longcostTime){
if(i==0){
StringBuildersb=newStringBuilder().append(caseName);
while(sb.length()<FIRST_COLUMN_LENGTH){
sb.append("");
}
System.out.print(sb);
}
StringBuildersb=newStringBuilder().append("|").append(costTime).append("ms");
while(sb.length()<OTHER_COLUMN_LENGTH){
sb.append("");
}
System.out.print(sb);
if(i==size-1){
printRowDivider();
}
}
}
PS：如果运行报异常inthread“main”java.lang.OutOfMemoryError:Javaheapspace，请将main函数里面listsize的大小减小。
其中getArrayLists函数会返回不同size的ArrayList，getLinkedLists函数会返回不同size的LinkedList。
loopListCompare函数会分别用上面的遍历方式1-5去遍历每一个list数组(包含不同大小list)中的list。
print开头函数为输出辅助函数。
测试环境为Windows732位系统3.2G双核CPU4G内存，Java7，Eclipse-Xms512m-Xmx512m
最终测试结果如下：
compareloopperformanceofArrayList ----------------------------------------------------------------------- listsize|10,000|100,000|1,000,000|10,000,000 ----------------------------------------------------------------------- foreach|1ms|3ms|14ms|152ms ----------------------------------------------------------------------- foriterator|0ms|1ms|12ms|114ms ----------------------------------------------------------------------- forlist.size()|1ms|1ms|13ms|128ms ----------------------------------------------------------------------- forsize=list.size()|0ms|0ms|6ms|62ms ----------------------------------------------------------------------- forj--|0ms|1ms|6ms|63ms ----------------------------------------------------------------------- compareloopperformanceofLinkedList ----------------------------------------------------------------------- listsize|100|1,000|10,000|100,000 ----------------------------------------------------------------------- foreach|0ms|1ms|1ms|2ms ----------------------------------------------------------------------- foriterator|0ms|0ms|0ms|2ms ----------------------------------------------------------------------- forlist.size()|0ms|1ms|73ms|7972ms ----------------------------------------------------------------------- forsize=list.size()|0ms|0ms|67ms|8216ms ----------------------------------------------------------------------- forj--|0ms|1ms|67ms|8277ms -----------------------------------------------------------------------
第一张表为ArrayList对比结果，第二张表为LinkedList对比结果。
表横向为同一遍历方式不同大小list遍历的时间消耗，纵向为同一list不同遍历方式遍历的时间消耗。
PS：由于首次遍历List会稍微多耗时一点，foreach的结果稍微有点偏差，将测试代码中的几个Type顺序调换会发现，foreach耗时和foriterator接近。
遍历方式性能测试结果分析
1、foreach介绍
foreach是JavaSE5.0引入的功能很强的循环结构，for(Integerj:list)应读作foreachintinlist。
for(Integerj:list)实现几乎等价于
Iterator<Integer>iterator=list.iterator();
while(iterator.hasNext()){
Integerj=iterator.next();
}
foreach代码书写简单，不必关心下标初始值和终止值及越界等，所以不易出错
2、ArrayList遍历方式结果分析
a.在ArrayList大小为十万之前，五种遍历方式时间消耗几乎一样
b.在十万以后，第四、五种遍历方式快于前三种，get方式优于Iterator方式，并且
intsize=list.size();
for(intj=0;j<size;j++){
list.get(j);
}
用临时变量size取代list.size()性能更优。我们看看ArrayList中迭代器Iterator和get方法的实现
privateclassItrimplementsIterator<E>{
intcursor;//indexofnextelementtoreturn
intlastRet=-1;//indexoflastelementreturned;-1ifnosuch
intexpectedModCount=modCount;
publicbooleanhasNext(){
returncursor!=size;
}
@SuppressWarnings("unchecked")
publicEnext(){
checkForComodification();
inti=cursor;
if(i>=size)
thrownewNoSuchElementException();
Object[]elementData=ArrayList.this.elementData;
if(i>=elementData.length)
thrownewConcurrentModificationException();
cursor=i+1;
return(E)elementData[lastRet=i];
}
……
}
publicEget(intindex){
rangeCheck(index);
returnelementData(index);
}
从中可以看出get和Iterator的next函数同样通过直接定位数据获取元素，只是多了几个判断而已。
c.从上可以看出即便在千万大小的ArrayList中，几种遍历方式相差也不过50ms左右，且在常用的十万左右时间几乎相等，考虑foreach的优点，我们大可选用foreach这种简便方式进行遍历。
3、LinkedList遍历方式结果分析
a.在LinkedList大小接近一万时，get方式和Iterator方式就已经差了差不多两个数量级，十万时Iterator方式性能已经远胜于get方式。
我们看看LinkedList中迭代器和get方法的实现
privateclassListItrimplementsListIterator<E>{
privateNode<E>lastReturned=null;
privateNode<E>next;
privateintnextIndex;
privateintexpectedModCount=modCount;
ListItr(intindex){
//assertisPositionIndex(index);
next=(index==size)?null:node(index);
nextIndex=index;
}
publicbooleanhasNext(){
returnnextIndex<size;
}
publicEnext(){
checkForComodification();
if(!hasNext())
thrownewNoSuchElementException();
lastReturned=next;
next=next.next;
nextIndex++;
returnlastReturned.item;
}
……
}
publicEget(intindex){
checkElementIndex(index);
returnnode(index).item;
}
/**
*Returnsthe(non-null)Nodeatthespecifiedelementindex.
*/
Node<E>node(intindex){
//assertisElementIndex(index);
if(index<(size>>1)){
Node<E>x=first;
for(inti=0;i<index;i++)
x=x.next;
returnx;
}else{
Node<E>x=last;
for(inti=size-1;i>index;i--)
x=x.prev;
returnx;
}
}
从上面代码中可以看出LinkedList迭代器的next函数只是通过next指针快速得到下一个元素并返回。而get方法会从头遍历直到index下标，查找一个元素时间复杂度为哦O(n)，遍历的时间复杂度就达到了O(n2)。
所以对于LinkedList的遍历推荐使用foreach，避免使用get方式遍历。
4、ArrayList和LinkedList遍历方式结果对比分析
从上面的数量级来看，同样是foreach循环遍历，ArrayList和LinkedList时间差不多，可将本例稍作修改加大listsize会发现两者基本在一个数量级上。
但ArrayListget函数直接定位获取的方式时间复杂度为O(1)，而LinkedList的get函数时间复杂度为O(n)。
再结合考虑空间消耗的话，建议首选ArrayList。对于个别插入删除非常多的可以使用LinkedList。
结论总结
通过上面的分析我们基本可以总结下：
- 无论ArrayList还是LinkedList，遍历建议使用foreach，尤其是数据量较大时LinkedList避免使用get遍历。
- List使用首选ArrayList。对于个别插入删除非常多的可以使用LinkedList。
- 可能在遍历List循环内部需要使用到下标，这时综合考虑下是使用foreach和自增count还是get方式。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家学习或者使用Java的时候能有所帮助，如果有疑问大家可以留言交流。