ArrayList与LinkedList的性能比较

今天有时间自己也测试了下ArrayList与LinkedList在读写操作的性能,结果如下:
os:winxp sp2 JDK1.5.10 cpu:奔腾D2.8 内存:1G 
在10000条数据下:
结果一:
ArrayList add Method 耗时:0
ArrayList get Method 耗时:15
ArrayList iterator Method 耗时:0
ArrayList remove Method 耗时:79
LinkedList add Method 耗时:15
LinkedList get Method 耗时:266
LinkedList iterator Method 耗时:0
LinkedList remove Method 耗时:0
array size:0
link size:0
结果二:
ArrayList add Method 耗时:15
ArrayList get Method 耗时:0
ArrayList iterator Method 耗时:0
ArrayList remove Method 耗时:78
LinkedList add Method 耗时:16
LinkedList get Method 耗时:266
LinkedList iterator Method 耗时:0
LinkedList remove Method 耗时:15
array size:0
link size:0

比率基本是5:5
在100000条数据下:
ArrayList add Method 耗时:78
ArrayList get Method 耗时:0
ArrayList iterator Method 耗时:16
ArrayList remove Method 耗时:7672
LinkedList add Method 耗时:109
LinkedList get Method 耗时:40547
LinkedList iterator Method 耗时:0
LinkedList remove Method 耗时:16

array size:0
link size:0

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;;

/**
 * 描述:小波think
 * **/
public class Test {

	private static List array = new ArrayList();
	private static List link = new LinkedList();
	private static final int count = 10000;
	
	public static void testArrayListAddMethod(){
		long start = System.currentTimeMillis();
		for(int i=0;i<count;i++){
			array.add(i);
		}
		System.out.println("ArrayList add Method 耗时:"+(System.currentTimeMillis()-start));
	}
	
	public static void testArrayListRemoveMethod(){
		int size = count;
		long start = System.currentTimeMillis();
		for(int i=0;i<size;i++){
			array.remove(i);
			i--;
			size--;
		}
		System.out.println("ArrayList remove Method 耗时:"+(System.currentTimeMillis()-start));
	}
	
	public static void testArrayListGetMethod(){
		long start = System.currentTimeMillis();
		for(int i=0;i<count;i++){
			array.get(i);
			
		}
		System.out.println("ArrayList get Method 耗时:"+(System.currentTimeMillis()-start));
	}
	
	public static void testArrayListIteratorMethod(){
		Iterator it = array.iterator();
		long start = System.currentTimeMillis();
		while(it.hasNext()){
			it.next();
		}
		System.out.println("ArrayList iterator Method 耗时:"+(System.currentTimeMillis()-start));
	}
	
	
	public static void testLinkedListAddMethod(){
		long start = System.currentTimeMillis();
		for(int i=0;i<count;i++){
			link.add(i);
		}
		System.out.println("LinkedList add Method 耗时:"+(System.currentTimeMillis()-start));
	}
	
	public static void testLinkedListRemoveMethod(){
		int size = count;
		long start = System.currentTimeMillis();
		for(int i=0;i<size;i++){
			link.remove(i);
			i--;
			size--;
		}
		System.out.println("LinkedList remove Method 耗时:"+(System.currentTimeMillis()-start));
	}
	
	public static void testLinkedListGetMethod(){
		long start = System.currentTimeMillis();
		for(int i=0;i<count;i++){
			link.get(i);
			
		}
		System.out.println("LinkedList get Method 耗时:"+(System.currentTimeMillis()-start));
	}
	
	public static void testLinkedListIteratorMethod(){
		Iterator it = link.iterator();
		long start = System.currentTimeMillis();
		while(it.hasNext()){
			it.next();
		}
		System.out.println("LinkedList iterator Method 耗时:"+(System.currentTimeMillis()-start));
	}
	
	public static void main(String[] args) {
		testArrayListAddMethod();
		testArrayListGetMethod();
		testArrayListIteratorMethod();
		testArrayListRemoveMethod();
		
		testLinkedListAddMethod();
		testLinkedListGetMethod();
		testLinkedListIteratorMethod();
		testLinkedListRemoveMethod();
		
		System.out.println("array size:"+array.size());
		System.out.println("link size:"+link.size());
	}

}

评论

13 楼 jerry 2009-02-18  

redduke1202 写道

如果你add的时候只往最后插，那么LinkedList显然没有ArrayList有优势
LinkedList的优势在于往中间insert数据,另外你的romove测试，似乎只remove了一半数据？

你可以作一个试验，就是向中间插，奇怪的也是ArrayList快。

12 楼 Eastsun 2008-04-22  

你这个：

for(int i=0;i<size;i++){   
        link.remove(i);   
        i--;   
        size--;   
}   

完全等同于：

for(int i=0;i<size;i++){
    link.remove(0);
}   

我想这不是你的本意吧。

还有，用的着为LinkedList与ArrayList各写一套功能完全一样的测试方法么？

而且你的测试代码大有问题，不能作为一个严谨的测试来用。

11 楼 小波think 2008-04-22  

Eastsun 写道

小波think 写道

	public static void testLinkedListRemoveMethod(){
		int size = count;
		long start = System.currentTimeMillis();
		for(int i=0;i<size;i++){
			link.remove(i);
			i--;
			size--;
		}
		

这代码写的太有创意了-_-

Eastsun 兄弟 这段代码你觉得怎么写才好啊  呵呵 请指教

10 楼 小波think 2008-04-22  

默认是10

9 楼 aids198311 2008-04-22  

大家可能忽略了一个重要的问题：ArrayList的初始化。
ArrayList如果没定义大小，会初始化为一个固定的大小（具体多少忘记了，反正比较小），加数据时，超出大小后会涉及到数组的COPY和创建。很影响效率的！
比较一下
List array = new ArrayList();
和
List array = new ArrayList(100000);

的时间差！

8 楼 Eastsun 2008-04-22  

小波think 写道

	public static void testLinkedListRemoveMethod(){
		int size = count;
		long start = System.currentTimeMillis();
		for(int i=0;i<size;i++){
			link.remove(i);
			i--;
			size--;
		}
		

这代码写的太有创意了-_-

7 楼 小波think 2008-04-22  

yuankai 写道

如果是插入的话ArrayList是要比LinkList快的，如果是查询的话LinkList肯定要比ArrayList快。LinkList在插入数据的时候在内存中是要先排序的，所以插入的时候就比ArrayList慢，查询的话就快。这个跟数据库中建索引一样。

同样是调用get(index)方法因该是ArrayList快,如果是iterator 的形式是LinkedList快

6 楼 yuankai 2008-04-22  

如果是插入的话ArrayList是要比LinkList快的，如果是查询的话LinkList肯定要比ArrayList快。LinkList在插入数据的时候在内存中是要先排序的，所以插入的时候就比ArrayList慢，查询的话就快。这个跟数据库中建索引一样。

5 楼 小波think 2008-04-22  

Rocwo 写道

为啥在100000条数据下执行add Method的时候，
LinkedList比ArrayList要慢呢？

在10000下有时ArryList比LinkedList慢,有时又比LinkedList快.
请高手说明哈 呵呵

发重了呵呵

4 楼 小波think 2008-04-22  

Rocwo 写道

为啥在100000条数据下执行add Method的时候，
LinkedList比ArrayList要慢呢？

在10000下有时ArryList比LinkedList慢,有时又比LinkedList快.
请高手说明哈 呵呵

3 楼 小波think 2008-04-22  

redduke1202 写道

如果你add的时候只往最后插，那么LinkedList显然没有ArrayList有优势
LinkedList的优势在于往中间insert数据,另外你的romove测试，似乎只remove了一半数据？

是的 犯了个低级错误忘写i--了 呵呵 谢谢redduke1202的提醒!
因为在我以前看的书里讲的是,ArrayList的add方法和remove方法都比LinkedList的慢很多.ArrayList方法更适合用来读多写少的情况下用.
我没测试add(index,Object)方法 因为平时我用的多的还是add(Object).

2 楼 Rocwo 2008-04-22  

为啥在100000条数据下执行add Method的时候，
LinkedList比ArrayList要慢呢？

1 楼 redduke1202 2008-04-22  

如果你add的时候只往最后插，那么LinkedList显然没有ArrayList有优势
LinkedList的优势在于往中间insert数据,另外你的romove测试，似乎只remove了一半数据？