List概括

先來回顧一下List在Collection中的的框架圖：

從圖中我們可以看出：

1. List是一個接口，它繼承與Collection接口，代表有序的隊列。

2. AbstractList是一個抽象類，它繼承與AbstractCollection。AbstractList實現了List接口中除了size()、get(int location)之外的方法。

3. AbstractSequentialList是一個抽象類，它繼承與AbstrctList。AbstractSequentialList實現了“鏈表中，根據index索引值操作鏈表的全部方法”。

4. ArrayList、LinkedList、Vector和Stack是List的四個實現類，其中Vector是基于JDK1.0，雖然實現了同步，但是效率低，已經不用了，Stack繼承與Vector，所以不再贅述。

5. LinkedList是個雙向鏈表，它同樣可以被當作棧、隊列或雙端隊列來使用。

ArrayList和LinkedList區別

我們知道，通常情況下，ArrayList和LinkedList的區別有以下幾點：

1. ArrayList是實現了基于動態數組的數據結構，而LinkedList是基于鏈表的數據結構；

2. 對于隨機訪問get和set，ArrayList要優于LinkedList，因為LinkedList要移動指針；

3. 對于添加和刪除操作add和remove，一般大家都會說LinkedList要比ArrayList快，因為ArrayList要移動數據。但是實際情況并非這樣，對于添加或刪除，LinkedList和ArrayList并不能明確說明誰快誰慢，下面會詳細分析。

我們結合之前分析的源碼，來看看為什么是這樣的：

ArrayList中的隨機訪問、添加和刪除部分源碼如下：

//獲取index位置的元素值  
public E get(int index) {  
    rangeCheck(index); //首先判斷index的范圍是否合法  
  
    return elementData(index);  
}  
  
//將index位置的值設為element，并返回原來的值  
public E set(int index, E element) {  
    rangeCheck(index);  
  
    E oldValue = elementData(index);  
    elementData[index] = element;  
    return oldValue;  
}  
  
//將element添加到ArrayList的指定位置  
public void add(int index, E element) {  
    rangeCheckForAdd(index);  
  
    ensureCapacityInternal(size + 1);  // Increments modCount!!  
    //將index以及index之后的數據復制到index+1的位置往后，即從index開始向后挪了一位  
    System.arraycopy(elementData, index, elementData, index + 1,  
                     size - index);   
    elementData[index] = element; //然后在index處插入element  
    size++;  
}  
  
//刪除ArrayList指定位置的元素  
public E remove(int index) {  
    rangeCheck(index);  
  
    modCount++;  
    E oldValue = elementData(index);  
  
    int numMoved = size - index - 1;  
    if (numMoved > 0)  
        //向左挪一位，index位置原來的數據已經被覆蓋了  
        System.arraycopy(elementData, index+1, elementData, index,  
                         numMoved);  
    //多出來的最后一位刪掉  
    elementData[--size] = null; // clear to let GC do its work  
  
    return oldValue;  
}

LinkedList中的隨機訪問、添加和刪除部分源碼如下：

//獲得第index個節點的值  
public E get(int index) {  
    checkElementIndex(index);  
    return node(index).item;  
}  
  
//設置第index元素的值  
public E set(int index, E element) {  
    checkElementIndex(index);  
    Node<E> x = node(index);  
    E oldVal = x.item;  
    x.item = element;  
    return oldVal;  
}  
  
//在index個節點之前添加新的節點  
public void add(int index, E element) {  
    checkPositionIndex(index);  
  
    if (index == size)  
        linkLast(element);  
    else  
        linkBefore(element, node(index));  
}  
  
//刪除第index個節點  
public E remove(int index) {  
    checkElementIndex(index);  
    return unlink(node(index));  
}  
  
//定位index處的節點  
Node<E> node(int index) {  
    // assert isElementIndex(index);  
    //index<size/2時，從頭開始找  
    if (index < (size >> 1)) {  
        Node<E> x = first;  
        for (int i = 0; i < index; i++)  
            x = x.next;  
        return x;  
    } else { //index>=size/2時，從尾開始找  
        Node<E> x = last;  
        for (int i = size - 1; i > index; i--)  
            x = x.prev;  
        return x;  
    }  
}

從源碼可以看出，ArrayList想要get(int index)元素時，直接返回index位置上的元素，而LinkedList需要通過for循環進行查找，雖然LinkedList已經在查找方法上做了優化，比如index < size / 2，則從左邊開始查找，反之從右邊開始查找，但是還是比ArrayList要慢。這點是毋庸置疑的。
ArrayList想要在指定位置插入或刪除元素時，主要耗時的是System.arraycopy動作，會移動index后面所有的元素；LinkedList主耗時的是要先通過for循環找到index，然后直接插入或刪除。這就導致了兩者并非一定誰快誰慢，下面通過一個測試程序來測試一下兩者插入的速度：

import java.util.ArrayList;    
import java.util.Collections;    
import java.util.LinkedList;    
import java.util.List;    
/* 
 * @description 測試ArrayList和LinkedList插入的效率 
 * @eson_15      
 */  
public class ArrayOrLinked {    
    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 time:"+getTime(array));    
        System.out.println("linked 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 = 10000; //表示要插入的數據量  
        int index = 1000; //表示從哪個位置插入  
        long time=System.currentTimeMillis();    
        for(int i = 1; i < num; i++){    
            list.add(index, i);       
        }    
        return System.currentTimeMillis()-time;    
            
    }    
    
}

主要有兩個因素決定他們的效率，插入的數據量和插入的位置。我們可以在程序里改變這兩個因素來測試它們的效率。

當數據量較小時，測試程序中，大約小于30的時候，兩者效率差不多，沒有顯著區別；當數據量較大時，大約在容量的1/10處開始，LinkedList的效率就開始沒有ArrayList效率高了，特別到一半以及后半的位置插入時，LinkedList效率明顯要低于ArrayList，而且數據量越大，越明顯。比如我測試了一種情況，在index=1000的位置(容量的1/10)插入10000條數據和在index=5000的位置以及在index=9000的位置插入10000條數據的運行時間如下：

在index=1000出插入結果：  
array time:4  
linked time:240  
array insert time:20  
linked insert time:18  
  
在index=5000處插入結果：  
array time:4  
linked time:229  
array insert time:13  
linked insert time:90  
  
在index=9000處插入結果：  
array time:4  
linked time:237  
array insert time:7  
linked insert time:92

從運行結果看，LinkedList的效率是越來越差。

所以當插入的數據量很小時，兩者區別不太大，當插入的數據量大時，大約在容量的1/10之前，LinkedList會優于ArrayList，在其后就劣與ArrayList，且越靠近后面越差。所以個人覺得，一般首選用ArrayList，由于LinkedList可以實現棧、隊列以及雙端隊列等數據結構，所以當特定需要時候，使用LinkedList，當然咯，數據量小的時候，兩者差不多，視具體情況去選擇使用；當數據量大的時候，如果只需要在靠前的部分插入或刪除數據，那也可以選用LinkedList，反之選擇ArrayList反而效率更高。

文章列表