深入了解ArrayList 和 LinkedList 差別

ArrayList的内部實作是基于數組，是以，它使用get方法通路清單中的任意一個元素時，它的速度要比LinkedList快。LinkedList的内部實作是基于連結清單的，LinkedList中的get方法是按順序從清單的一端到另一端。對LinkedList而言，隻有這種查找方法。

Bruca Eckel描述如下：

Java程式設計思想對List的描述（4版P233）：

• 基本的ArrayList，它長于随機通路，但是在List的中間插入和一處速度較慢。

• LinkedList，它通過代價較低的在List中間進行插入和删除操作，提供了優化的順序通路，LinkedList在随機通路方面相對較慢，但是它的特性較ArrayList更大。

實作分析：

• 問題：假設一個很大的清單，其中元素已經排序（在靜态代碼塊中實作），這個清單可能是ArrayList類型的也可能是LinkedList類型的，現在我們對這個清單來進行二分查找(binary search)，比較ArrayList和LinkedList時的查詢速度。然後在比較插入/删除的速度。

• 測試結果

  N=1000時，在前段1/10,1/5處兩者幾乎無差别，可忽略。

  N=10000時，在前段1/5處或更前面的位置，LinkedList的效率更高，

  N=100000時，在前段1/10處或更前面的位置，LinkedList的效率更高

代碼如下，第一，保證ArrayList和Linked先被建立出來，排除ArratList自動擴容的問題。

package demo;

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

public class Test3 {  

    public static final int N = ;   
    public static List values;   

    //保證在靜态代碼塊中先生成List，排除擴容問題
    static{   
        Integer vals[] = new Integer[N];   
        Random r = new Random();   

        for(int i= ,currval = ;i < N;i++){ 
         //Integer數組  vals[]的每一個元素 初始化都為0
            vals[i] = new Integer(currval);  
            currval += r.nextInt() + ;  //currval=currval+r.nextInt(100)+1; 
        }   
        //數組生成集合List
        values = Arrays.asList(vals);   
    }

    static long getTime(List lst){   
        long start = System.currentTimeMillis();   //目前時間
        for(int i=;i<N;i++){   
            int index = Collections.binarySearch(lst, values.get(i));   //二分法
            if(index!=i) 
             System.out.println("***錯誤***");   
        }   

        return System.currentTimeMillis() - start;   
    } 

    public static long insertTime(List list){  
        long time = System.currentTimeMillis();
        //控制在List插入删除的位置
        int index = N/;
        for(int i=;i<N;i++){  
            //在下标index出插入
            list.add(index,i);  //N=100000,1/10處之後 LinkedList就開始變慢了

            //将下标index處的删除
            list.remove(index); 
            //remove掉之前添加的對象 執行次數是（index-100）次
            if(i == index)  
                break;
        }  
        return System.currentTimeMillis()-time;  
    }  

    public static void main(String[] args) {
        System.out.println("linked time:"+getTime(new LinkedList(values)));  
        System.out.println("array time:"+getTime(new ArrayList(values)));  
        System.out.println("linked insert time:"+insertTime(new LinkedList(values))); 
        System.out.println("array insert time:"+insertTime(new ArrayList(values)));  
    }
}  

結果：
N=時，index=N/時
linked time:
array time:
linked insert time:
array insert time:
如果插入到/後段

結果：
N=時，index=N/時
linked time:
array time:
linked insert time:
array insert time:

結果：
N=時，index=N/或者index=N/兩者幾乎無差别
linked time:
array time:
linked insert time:
array insert time:
           

讨論：

集合元素很多時，當需要插入資料的時候，如果是在集合的前段（大概集合容量的前1/10）處插入資料時，linkedlist性能明顯（記憶體開銷、時間）優于arraylist，但是！！！！當在集合的中部甚至靠後的位置插入大量資料時，arraylist的性能反而遠遠優于linkedlist，是以，linkedlist相較于arraylist的優勢在于集合前段的資料的插入和記憶體的開銷。

對于ArraList，對清單中間插入和删除LinkedList是廉價操作，但是對于ArrayList，這可是代價高昂的操作。因為對記憶體的開銷很大，是數組複制的原因。

ArrayList源碼

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see )
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }  
           

Arrays.copyOf()，顯然在資料很大時，任然需要數組複制，必然對記憶體的開銷增大。

LinkedList源碼：

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == )
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }
           

在LinkedList中有一個私有的内部類

private static class Entry {   
         Object element;   
         Entry next;   
         Entry previous;   
     }
           

• 每個Entry對象reference清單中的一個元素，同時還有在LinkedList中它的上一個元素和下一個元素。一個有1000個元素的LinkedList對象将有1000個連結在一起的Entry對象，每個對象都對應于清單中的一個元素。這樣的話，在一個LinkedList結構中将有一個很大的空間開銷，因為它要存儲這1000個Entity對象的相關資訊。

  ArrayList使用一個内置的數組來存儲元素，這個數組的起始容量是10.當數組需要增長時，新的容量按如下公式獲得：新容量=(舊容量*3)/2+1，也就是說每一次容量大概會增長50%。這就意味着，如果你有一個包含大量元素的ArrayList對象，那麼最終将有很大的空間會被浪費掉，這個浪費是由ArrayList的工作方式本身造成的。如果沒有足夠的空間來存放新的元素，數組将不得不被重新進行配置設定以便能夠增加新的元素。對數組進行重新配置設定，将會導緻性能急劇下降。如果我們知道一個ArrayList将會有多少個元素，我們可以通過構造方法來指定容量。我們還可以通過trimToSize方法在ArrayList配置設定完畢之後去掉浪費掉的空間。

• LinkedList是基于連結清單來操作的，LinkedList儲存了前後元素的資訊，LinkedList在随機通路方面相對較慢，但是它的特性較ArrayList更大，系統不單也要考慮速度，對記憶體的開銷也要考慮。

總結

• ArrayList和LinkedList在性能上各有優缺點，都有各自所适用的地方，總的說來可以描述如下：

  1．對ArrayList和LinkedList而言，在清單末尾增加一個元素所花的開銷都是固定的。對ArrayList而言，主要是在内部數組中增加一項，指向所添加的元素，偶爾可能會導緻對數組重新進行配置設定；而對LinkedList而言，這個開銷是統一的，配置設定一個内部Entry對象。

2．在ArrayList的中間插入或删除一個元素意味着這個清單中剩餘的元素都會被移動；而在LinkedList的中間插入或删除一個元素的開銷是固定的。

3．LinkedList無法進行高效的元素通路。

4．ArrayList的空間浪費主要展現在在list清單的結尾預留一定的容量空間，而LinkedList的空間花費是它的每一個元素都需要消耗相當的空間來儲存前後元素的位置。

在一列資料(無論資料是大是少)的後面部分添加/删除資料—不是在前面或中間；或者任何時候需要通路List元素時,使用ArrayList更好；在一列資料(無論資料量很大)的前面或中間部分添加/删除資料,就應該使用LinkedList了。 總體而言，ArrayList實際開發中用的更多。