Java中LinkedList与ArrayList对比

在学java数据结构的时候发现有LinkedList与ArrayList，就想知道他们的性能如何，所以做了如下的对比，

 

对比做得比较粗糙，也很不严谨，不过也有一定的参考价值吧。

 

/*
 * 测试数据大小 1000 - 100000
 * 测试List的3个方法：
 * 1、add(Element)  新加入元素
 * 2、add(index,Element)  固定位置插入元素
 * 3、remove(Element)  删除特定元素
 * 结果为执行所需时间
 */


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

public class LinkListTest {

	public static void main(String[] args) {
		
		long time;
		int TestNum ;
		List<String> link_list = null;
		List<String> array_list = null;
		
		
		for(int j = 3 ; j <=5 ;j ++){
			TestNum = (int)Math.pow(10, j);
			System.out.println("Test amount :"+TestNum);
			
			link_list = new LinkedList<String>();
			array_list = new ArrayList<String>();
			
			/*list add*/
			time = System.currentTimeMillis();
			for(int i = 0 ; i<TestNum ; i++){
				link_list.add(i+"");
			}
			time = System.currentTimeMillis() - time;
			System.out.printf("%18s:%6dms\n","link_list_add",time);
			
			time = System.currentTimeMillis();
			for(int i = 0 ; i<TestNum ; i++){
				array_list.add(i+"");
			}
			time = System.currentTimeMillis() - time;
			System.out.printf("%18s:%6dms\n","array_list_add",time);
			
			
			/*list add index*/
			time = System.currentTimeMillis();
			for(int i = 0 ; i<TestNum ; i++){
				link_list.add(i*2, i+"");
			}
			time = System.currentTimeMillis() - time;
			System.out.printf("%18s:%6dms\n","link_list_insert",time);
			
			time = System.currentTimeMillis();
			for(int i = 0 ; i<TestNum ; i++){
				array_list.add(i*2, i+"");
			}
			time = System.currentTimeMillis() - time;
			System.out.printf("%18s:%6dms\n","arry_list_insert",time);	
			
			
			/*list remove index*/
			time = System.currentTimeMillis();
			for(int i = 0 ; i<TestNum ; i++){
				link_list.remove(i);
			}
			time = System.currentTimeMillis() - time;
			System.out.printf("%18s:%6dms\n","link_list_remove",time);
			
			time = System.currentTimeMillis();
			for(int i = 0 ; i<TestNum ; i++){
				array_list.remove(i);
			}
			time = System.currentTimeMillis() - time;
			System.out.printf("%18s:%6dms\n","array_list_remove",time);
			
			
			System.out.printf("%18s:%8d\n","link_list_size",link_list.size());
			System.out.printf("%18s:%8d\n","array_list_size",array_list.size());
			
			link_list = null;
			array_list = null;
			
			System.gc();

		}
		
	}

}

 

测试结果：
Test amount :1000
     link_list_add:    15ms
    array_list_add:    31ms
  link_list_insert:     0ms
  arry_list_insert:     0ms
  link_list_remove:     0ms
 array_list_remove:     0ms
    link_list_size:    1000
   array_list_size:    1000
Test amount :10000
     link_list_add:    16ms
    array_list_add:     0ms
  link_list_insert:  1000ms
  arry_list_insert:    94ms
  link_list_remove:   750ms
 array_list_remove:   156ms
    link_list_size:   10000
   array_list_size:   10000
Test amount :100000
     link_list_add:   141ms
    array_list_add:   265ms
  link_list_insert:186797ms
  arry_list_insert: 12344ms
  link_list_remove:178812ms
 array_list_remove: 28954ms
    link_list_size:  100000
   array_list_size:  100000

 

发现一个很有趣的现象，在数据比较小的时候LinkedList的执行速度很快，

 

在数据比较大的时候，很明显的看出ArrayList的执行速度更快，

 

与自己的想象刚好相反。

评论

1 楼 yin_chinawitsky 2011-06-30  

路过了、、、、