做插入时，ArrayList居然比LinkedList快

Sky-Tiger

原帖由 justforregister 于 2008-12-16 22:32 发表

天虎也这么崇洋媚外？

公司每年都请SUN的工程师来做技术交流！

justforregister

那帮忙解释解释4楼的问题吧，高手

dearmeiw

原帖由 justforregister 于 2008-12-16 17:58 发表

呵呵， 你run run代码在说吧

强烈支持你这种有技术性的BS天虎！


的确跑过后要把那个REMOVE去了才快！

asangel

java的链表设计是不是不一样？

高手解答一下

greenflute

代码有一定迷惑性，不如把各项指标拆开来进行单项比较，代码修改如下：

1. 
   
2. import java.util.ArrayList;
   
3. import java.util.LinkedList;
   
4. import java.util.List;
   
5. 
   
6. public class TestArrayList {
   
7. 
   
8.         @SuppressWarnings("unchecked")
   
9.         public static void main(String[] args) {
   
10.                 test(new ArrayList());
    
11.                 test(new LinkedList());
    
12.         }
    
13. 
    
14.         @SuppressWarnings("unchecked")
    
15.         public static void test(List list) {
    
16.                 System.out.println(list.getClass().getName());
    
17. 
    
18.                 System.out.print("simpleadd\tsize: " + list.size());
    
19.                 Long l = System.currentTimeMillis();
    
20.                 for (int i = 0; i < 10000; i++) {
    
21.                         list.add("a" + i);
    
22.                 }
    
23.                 Long ll = System.currentTimeMillis();
    
24.                 System.out.println(" ----> " + list.size());
    
25.                 System.out.println("time elasped " + (ll - l));
    
26. 
    
27.                 System.out.print("middleadd\tsize: " + list.size());
    
28.                 l = System.currentTimeMillis();
    
29.                 for (int j = 500; j < 5500; j++) {
    
30.                         list.add(j, "test" + j);
    
31.                 }
    
32.                 ll = System.currentTimeMillis();
    
33.                 System.out.println(" ----> " + list.size());
    
34.                 System.out.println("time elasped " + (ll - l));
    
35. 
    
36.                 System.out.print("simpleremove\tsize: " + list.size());
    
37.                 l = System.currentTimeMillis();
    
38.                 for (int j = 500; j < 5500; j++) {
    
39.                         list.remove(0);
    
40.                 }
    
41.                 ll = System.currentTimeMillis();
    
42.                 System.out.println(" ----> " + list.size());
    
43.                 System.out.println("time elasped " + (ll - l));
    
44.                
    
45.                 System.out.print("middleremove\tsize: " + list.size());
    
46.                 l = System.currentTimeMillis();
    
47.                 for (int j = 500; j < 5500; j++) {
    
48.                         list.remove(j - 500);
    
49.                 }
    
50.                 ll = System.currentTimeMillis();
    
51.                 System.out.println(" ----> " + list.size());
    
52.                 System.out.println("time elasped " + (ll - l));
    
53.         }
    
54. 
    
55. }
    

复制代码

greenflute

java.util.ArrayList
simpleadd        size: 0 ----> 10000
time elasped 31
middleadd        size: 10000 ----> 15000
time elasped 94
simpleremove        size: 15000 ----> 10000
time elasped 63
middleremove        size: 10000 ----> 5000
time elasped 16

java.util.LinkedList
simpleadd        size: 0 ----> 10000
time elasped 0
middleadd        size: 10000 ----> 15000
time elasped 156
simpleremove        size: 15000 ----> 10000
time elasped 0
middleremove        size: 10000 ----> 5000
time elasped 47

这样就可以比较容易看出各自的优劣了

greenflute

可以看出，确实如SkyTiger所说，其实也是如我们大家所熟知的，ArrayList在随机寻址的添加和删除上速度较快，而LinkedList在队列头部的添加和删除较快。

greenflute

原帖由 justforregister 于 2008-12-16 09:22 发表
但是你把这句屏蔽掉al.remove(j-50);
run arraylist的时候，半天都没结果
linkedlist 10秒可以出结果

去了remove，等于需要添加5000*100条记录，jvm忙着给ArrayList分配内存了，呵呵

dearmeiw

楼上的认真，强烈支持。


BS天虎！

Sky-Tiger

SUN的工程师都是JDK设计和开发者，他们的总结一般都是准确的！