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的执行速度更快，

 

与自己的想象刚好相反。

本身两个的数据结构都不同，不同场景适合不同的List，没什么可比性。。看原理就行了。。

你的测试根本不公平，不能两个放在一起测试，即使计时分开。因为，前面的大List的操作，可能会导致后续的操作过程中发生GC,而被回收的，却全是前面一个List的内容

把

link_list.add(i*2, i+"");  array_list.add(i*2,i+"");link_list.remove(i);array_list.remove(i);

改成

link_list.add(0, i+"");  array_list.add(0,i+"");link_list.remove(0);array_list.remove(0);

结果就大不一样了：

Test amount :1000
     link_list_add:     0ms
    array_list_add:    15ms
  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:     0ms
    array_list_add:    15ms
  link_list_insert:    16ms
  arry_list_insert:   141ms
  link_list_remove:     0ms
 array_list_remove:   140ms
    link_list_size:   10000
   array_list_size:   10000
Test amount :100000
     link_list_add:   125ms
    array_list_add:    94ms
  link_list_insert:    63ms
  arry_list_insert: 17125ms
  link_list_remove:    15ms

ArrayList和LinkedList内部实现的数据结构都不一样 有啥好比的?
ArrayList使用Object数组实现的,LinkedList内部有一个Entry实现的
这有啥好比的!

我新手，为什么每次做list声明的时候都是 List<E> list=new ArrayList<E>();呢 我也不明白。

。。。问错了，一个是接口，一个是实现。。不好意思。

线性表  和 链表
没有可比性  使用场景都不一样

非常感谢你的提醒，最开始还只是一时兴起，没有考虑太多的东西，只是比较随意的让他们进行相同的操作。
现在想想，确实是自己太欠考虑了，我应该多考虑的是数据的加入删除时，数据所在的位置，而不是单单只将其当做一个简单的方法看待。

LinkedList更改比较快，ArrayList读取比较快
这个取决于内部实现方式吧