Java中LinkedList遍历速度可比ArrayList快!

import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Random;

 public class TestList {
     private static Random random = new Random();
     public static void main(String[] args){
         ArrayList<String> arraylist = new ArrayList<String>();
         LinkedList<String> linkedlist = new LinkedList<String>();
         for(int i=0;i<50000;i++){
             String r = randomString();
             arraylist.add(r);
             linkedlist.add(r);
         }
         
         System.out.println("arraylist size "+arraylist.size());
         System.out.println("linkedlist size "+linkedlist.size());
         System.out.println("------");
         long begin = System.currentTimeMillis();
         for(int i=0;i<1000;i++){
             for(int j=0;j<arraylist.size();j++){
            	 String s=arraylist.get(j);
             }
         }
         System.out.println("arraylist get(n) time "+(System.currentTimeMillis()-begin));
         
         begin = System.currentTimeMillis();
         for(int i=0;i<1000;i++){
             for(String s:arraylist){
             }
         }
         System.out.println("arraylist foreach time "+(System.currentTimeMillis()-begin));
         
         begin = System.currentTimeMillis();
         for(int i=0;i<1;i++)
         for(int j=0;j<linkedlist.size();j++){
        	 String s=linkedlist.get(j);
         }
         System.out.println("linkedlist get(n) time "+(System.currentTimeMillis()-begin)*1000);
         
         begin = System.currentTimeMillis();
         for(int i=0;i<1000;i++)
         for(String s:linkedlist){
//             linkedlist.get(j);
         }
         System.out.println("linkedlist foreach time "+(System.currentTimeMillis()-begin));
         
         
     }
     protected static String randomString() {
         return Long.toString(random.nextLong(), 36);
     }
 }

arraylist size 50000
linkedlist size 50000
------
arraylist get(n) time 562
arraylist foreach time 1703
linkedlist get(n) time 1922000
linkedlist foreach time 813

结论linkedlist foreach比arraylist foreach快

评论

8 楼 cloverprince 2011-07-13  

$ java -version
java version "1.6.0_20"
OpenJDK Runtime Environment (IcedTea6 1.9.8) (fedora-53.1.9.8.fc14-x86_64)
OpenJDK 64-Bit Server VM (build 19.0-b09, mixed mode)

7 楼 cloverprince 2011-07-13  

arraylist size 50000
linkedlist size 50000
------
arraylist get(n) time 736
arraylist foreach time 966
省略了那个linkedlist get(n)
linkedlist foreach time 2034

6 楼 zxh603 2011-07-13  

这个不一定哦，楼主这样写有点误导群众啦

5 楼 wanbin021614 2011-07-12  

遍历应该是arraylist快 删除和添加是linkedlist快 大致是这样 数组大小会影响效率

4 楼 qingming.com 2011-07-12  

二者进行遍历到底谁快的问题还真的很难说。
这样有点误导别人。
本来二者主要区别就是一个是随机读取快，一个是易维护（增加/删除）。不过也没试过linkedlist在首尾增删跟在链的中部增删与arrylist的效率相比如何，在size很小和很大的情况有什么异同。

3 楼 ericslegend 2011-07-12  

对于for(int i =0;i<list.size();i++)这种遍历，ArrayList的运行时间为O(N),LinkedList的运行时间为O(n*n),因为对于LinkedList来说调用get(N)操作耗时O(N)，但对于增强的for循环，这里即foreach，任意list的运行时间都为O（N）,因为迭代器将有效地从一项到下一项前进。所以对于arraylist一般直接通过下标取（index）是最快的，对于linkedlist由于每次都从链头处开始，所以适合顺序操作，除非使用iterator，这时才是每次从当前位置开始。

2 楼 cectsky 2011-07-12  

arraylist size 50000
linkedlist size 50000
------
arraylist get(n) time 484
arraylist foreach time 2172
linkedlist get(n) time 2983000
linkedlist foreach time 1391

32位Java6 确实是LinkedList foreach要快些

1 楼 deepnighttwo 2011-07-12  

arraylist size 50000
linkedlist size 50000
------
arraylist get(n) time 559
arraylist foreach time 481
linkedlist get(n) time 3723000
linkedlist foreach time 3080

64位Java6，加了参数-Xms300m -Xmx500m。跑了n次，每次都是ArrayList完胜LinkedList。不知道lz是不是debug跑的？