ArrayList & LinkedList 区别对比

ArrayList & LinkedList 区别对比：

 

一、源代码：

 

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 

public class LinkedList<E> extends AbstractSequentialList<E>

        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

 

可以看出：ArrayList实现了随机访问的接口，LinkedList实现了Deque的接口。ArrayList是基于数据实现的list，而LinkedList是基于链表实现的list。所以，ArrayList拥有着数组的特性，LinkedList拥有着链表的特性。

 

二、使用对比：

1、对于随机访问get和set，ArrayList要优于LinkedList；

例子：

 

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

public class TestArrayListAndLinkedList {

	/**
	 * 测试类演示在对于随机访问get和set时，ArrayList要优于LinkedList
	 * @author cdzhujun
	 */
    public static void main(String args[]){   
    	testPerformance();
    }
    
    public static void testPerformance() {  
        ArrayList<Integer> arrayList = new ArrayList<Integer>();  
        LinkedList<Integer> linkedList = new LinkedList<Integer>();  
      
        int times = 10000;
        //int times = 100000;  
        //int times = 1000000;  
        System.out.println("Test times = " + times);  
        long startTime = System.nanoTime();
        long endTime = System.nanoTime();  
        long duration = endTime - startTime;
        System.out.println("-----------add--------------");  
        // ArrayList add  
        for (int i = 0; i < times; i++) {  
            arrayList.add(i);  
        }  
        endTime = System.nanoTime();  
        duration = endTime - startTime;  
        System.out.println(duration + " <--ArrayList add");  
      
        // LinkedList add  
        startTime = System.nanoTime();  
      
        for (int i = 0; i < times; i++) {  
            linkedList.add(i);  
        }  
        endTime = System.nanoTime();  
        duration = endTime - startTime;  
        System.out.println(duration + " <--LinkedList add"); 
        System.out.println("-------------set------------");  
        // ArrayList set  
        startTime = System.nanoTime();  
      
        for (int i = 0; i < times; i++) {  
            arrayList.set(i,i);  
        }  
        endTime = System.nanoTime();  
        duration = endTime - startTime;  
        System.out.println(duration + " <--ArrayList set");  
      
        // LinkedList set  
        startTime = System.nanoTime();  
      
        for (int i = 0; i < times; i++) {  
            linkedList.set(i,i);  
        }  
        endTime = System.nanoTime();  
        duration = endTime - startTime;  
        System.out.println(duration + " <--LinkedList set"); 
        System.out.println("-------------get------------");  
        // ArrayList get  
        startTime = System.nanoTime();  
      
        for (int i = 0; i < times; i++) {  
            arrayList.get(i);  
        }  
        endTime = System.nanoTime();  
        duration = endTime - startTime;  
        System.out.println(duration + " <--ArrayList get");  
      
        // LinkedList get  
        startTime = System.nanoTime();  
      
        for (int i = 0; i < times; i++) {  
            linkedList.get(i);  
        }  
        endTime = System.nanoTime();  
        duration = endTime - startTime;  
        System.out.println(duration + " <--LinkedList get");  
    }  
}

 执行结果为：

Test times = 10000
-----------add--------------
2509452 <--ArrayList add
3309158 <--LinkedList add
-------------set------------
2000120 <--ArrayList set
50424251 <--LinkedList set
-------------get------------
2275955 <--ArrayList get
46542041 <--LinkedList get

 

 

2、对于添加和删除操作add和remove，LinkedList与ArrayList谁快谁慢要取决于插入的数据的位置和插入数据的大小。

例子：

 

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

/**
 * 测试ArrayList和LinkedList插入的效率，对于添加和删除操作add和remove，LinkedList与ArrayList谁快谁慢要取决于插入的数据的位置和插入数据的大小。
 * 当数据量较小时，测试程序中，大约小于30的时候，两者效率差不多，没有显著区别；
 * 当数据量较大时，大约在容量的1/10处开始，LinkedList的效率就开始没有ArrayList效率高了，
 * 特别到一半以及后半的位置插入时，LinkedList效率明显要低于ArrayList，而且数据量越大，越明显。
 * 
 * @author cdzhujun
 *
 */
public class TestArrayListAndLinkedList2 {

	static List<Integer> array=new ArrayList<Integer>();    
    static List<Integer> linked=new LinkedList<Integer>();    
    
    public static void main(String[] args) {    
    
        //首先分别给两者插入10000条数据  
        for(int i=0;i<10000;i++){    
            array.add(i);    
            linked.add(i);    
        }    
        //获得两者随机访问的时间  
        System.out.println("array GET time:"+getTime(array));    
        System.out.println("linked GET time:"+getTime(linked));    
        //获得两者插入数据的时间  
        System.out.println("array INSERT time:"+insertTime(array));    
        System.out.println("linked INSERT time:"+insertTime(linked));    
    
    }
    //获取数据    
    public static long getTime(List<Integer> list){    
        long time=System.currentTimeMillis();    
        for(int i = 0; i < 10000; i++){    
            int index = Collections.binarySearch(list, list.get(i));    
            if(index != i){    
                System.out.println("ERROR!");    
            }    
        }    
        return System.currentTimeMillis()-time;    
    }    
      
    //插入数据  
    public static long insertTime(List<Integer> list){   
        /* 
         * 插入的数据量和插入的位置是决定两者性能的主要方面， 
         * 我们可以通过修改这两个数据，来测试两者的性能 
         */  
       long num = 5000; //表示要插入的数据量 ，测试值可以为30，5000，10000 
        int index = 1000; //表示从哪个位置插入，1000、5000、9000  
        long time=System.currentTimeMillis();    
        for(int i = 1; i < num; i++){    
            list.add(index, i);       
        }    
        return System.currentTimeMillis()-time;    
            
    }    
}

 

 执行结果为：

在index=1000出插入结果：  
array GET time:4  
linked GET time:240  
array INSERT time:20  
linked INSERT time:18  
  
在index=5000处插入结果：  
array GET time:4  
linked GET time:229  
array INSERT time:13  
linked INSERT time:90  
  
在index=9000处插入结果：  
array GET time:4  
linked GET time:237  
array INSERT time:7  
linked INSERT time:92 

 

 

从运行结果看，LinkedList的效率是越来越差。

总结：

所以当插入的数据量很小时，两者区别不太大。当插入的数据量大时，大约在容量的1/10之前，LinkedList会优于ArrayList，在其后就劣与ArrayList，且越靠近后面越差。所以个人觉得，一般首选用ArrayList，由于LinkedList可以实现栈、队列以及双端队列等数据结构，所以当特定需要时候，使用LinkedList，当然，数据量小的时候，两者差不多，视具体情况去选择使用；当数据量大的时候，如果只需要在靠前的部分插入或删除数据，那也可以选用LinkedList，反之选择ArrayList反而效率更高。

 

或者说，当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。