SDK提供了有序集合接口java.util.List的幾種實(shí)現(xiàn)，其中三種最為人們熟知的是Vector、ArrayList和LinkedList。有關(guān)這些List類的性能差別是一個(gè)經(jīng)常被問及的問題。在這篇文章中，我要探討的就是LinkedList和Vector/ArrayList之間的性能差異。

為全面分析這些類之間的性能差異，我們必須知道它們的實(shí)現(xiàn)方法。因此，接下來我首先從性能的角度出發(fā)，簡要介紹這些類的實(shí)現(xiàn)特點(diǎn)。

一、Vector和ArrayList的實(shí)現(xiàn)
Vector和ArrayList都帶有一個(gè)底層的Object[]數(shù)組，這個(gè)Object[]數(shù)組用來保存元素。通過索引訪問元素時(shí)，只需簡單地通過索引訪問內(nèi)部數(shù)組的元素：
public Object get(int index)
{ //首先檢查index是否合法...此處不顯示這部分代碼 return
elementData[index]; }

內(nèi)部數(shù)組可以大于Vector/ArrayList對象擁有元素的數(shù)量，兩者的差值作為剩余空間，以便實(shí)現(xiàn)快速添加新元素。有了剩余空間，添加元素變得非常簡單，只需把新的元素保存到內(nèi)部數(shù)組中的一個(gè)空余的位置，然后為新的空余位置增加索引值：
public boolean add(Object o)
{ ensureCapacity(size 1); //稍后介紹 elementData[size ] = o; return true;
//List.add(Object) 的返回值 }

把元素插入集合中任意指定的位置（而不是集合的末尾）略微復(fù)雜一點(diǎn)：插入點(diǎn)之上的所有數(shù)組元素都必須向前移動一個(gè)位置，然后才能進(jìn)行賦值：
public void add(int index, Object element) {
//首先檢查index是否合法...此處不顯示這部分代碼
ensureCapacity(size 1);
System.arraycopy(elementData, index, elementData, index 1,
size - index);
elementData[index] = element;
size ;
}

剩余空間被用光時(shí)，如果需要加入更多的元素，Vector/ArrayList對象必須用一個(gè)更大的新數(shù)組替換其內(nèi)部Object[]數(shù)組，把所有的數(shù)組元素復(fù)制到新的數(shù)組。根據(jù)SDK版本的不同，新的數(shù)組要比原來的大50%或者100%（下面顯示的代碼把數(shù)組擴(kuò)大100%）：
public void ensureCapacity(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = Math.max(oldCapacity * 2, minCapacity);
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}

Vector類和ArrayList類的主要不同之處在于同步。除了兩個(gè)只用于串行化的方法，沒有一個(gè)ArrayList的方法具有同步執(zhí)行的能力；相反，Vector的大多數(shù)方法具有同步能力，或直接或間接。因此，Vector是線程安全的，但ArrayList不是。這使得ArrayList要比Vector快速。對于一些最新的JVM，兩個(gè)類在速度上的差異可以忽略不計(jì)：嚴(yán)格地說，對于這些JVM，這兩個(gè)類在速度上的差異小于比較這些類性能的測試所顯示的時(shí)間差異。

通過索引訪問和更新元素時(shí)，Vector和ArrayList的實(shí)現(xiàn)有著卓越的性能，因?yàn)椴淮嬖诔秶鷻z查之外的其他開銷。除非內(nèi)部數(shù)組空間耗盡必須進(jìn)行擴(kuò)展，否則，向列表的末尾添加元素或者從列表的末尾刪除元素時(shí)，都同樣有著優(yōu)秀的性能。插入元素和刪除元素總是要進(jìn)行數(shù)組復(fù)制（當(dāng)數(shù)組先必須進(jìn)行擴(kuò)展時(shí)，需要兩次復(fù)制）。被復(fù)制元素的數(shù)量和[size-index]成比例，即和插入/刪除點(diǎn)到集合中最后索引位置之間的距離成比例。對于插入操作，把元素插入到集合最前面（索引0）時(shí)性能最差，插入到集合最后面時(shí)（最后一個(gè)現(xiàn)有元素之后）時(shí)性能最好。隨著集合規(guī)模的增大，數(shù)組復(fù)制的開銷也迅速增加，因?yàn)槊看尾迦氩僮鞅仨殢?fù)制的元素?cái)?shù)量增加了。

二、LinkedList的實(shí)現(xiàn)
LinkedList通過一個(gè)雙向鏈接的節(jié)點(diǎn)列表實(shí)現(xiàn)。要通過索引訪問元素，你必須查找所有節(jié)點(diǎn)，直至找到目標(biāo)節(jié)點(diǎn)：
public Object get(intindex) {
//首先檢查index是否合法...此處不顯示這部分代碼
Entry e = header; //開始節(jié)點(diǎn)
//向前或者向后查找，具體由哪一個(gè)方向距離較
//近決定
if (index < size/2) {
for (int i = 0; i <= index; i )
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}

把元素插入列表很簡單：找到指定索引的節(jié)點(diǎn)，然后緊靠該節(jié)點(diǎn)之前插入一個(gè)新節(jié)點(diǎn)：
public void add(int index, Object element) {
//首先檢查index是否合法...此處不顯示這部分代碼
Entry e = header; //starting node
//向前或者向后查找，具體由哪一個(gè)方向距離較
//近決定
if (index < size/2) {
for (int i = 0; i <= index; i )
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
Entry newEntry = new Entry(element, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size ;
}

線程安全的LinkedList和其他集合
如果要從Java SDK得到一個(gè)線程安全的LinkedList，你可以利用一個(gè)同步封裝器從Collections.synchronizedList(List)得到一個(gè)。然而，使用同步封裝器相當(dāng)于加入了一個(gè)間接層，它會帶來昂貴的性能代價(jià)。當(dāng)封裝器把調(diào)用傳遞給被封裝的方法時(shí)，每一個(gè)方法都需要增加一次額外的方法調(diào)用，經(jīng)過同步封裝器封裝的方法會比未經(jīng)封裝的方法慢二到三倍。對于象搜索之類的復(fù)雜操作，這種間接調(diào)用所帶來的開銷不是很突出；但對于比較簡單的方法，比如訪問功能或者更新功能，這種開銷可能對性能造成嚴(yán)重的影響。

這意味著，和Vector相比，經(jīng)過同步封裝的LinkedList在性能上處于顯著的劣勢，因?yàn)閂ector不需要為了線程安全而進(jìn)行任何額外的間接調(diào)用。如果你想要有一個(gè)線程安全的LinkedList，你可以復(fù)制LinkedList類并讓幾個(gè)必要的方法同步，這樣你可以得到一個(gè)速度更快的實(shí)現(xiàn)。對于所有其它集合類，這一點(diǎn)都同樣有效：只有List和Map具有高效的線程安全實(shí)現(xiàn)（分別是Vector和Hashtable類）。有趣的是，這兩個(gè)高效的線程安全類的存在只是為了向后兼容，而不是出于性能上的考慮。

對于通過索引訪問和更新元素，LinkedList實(shí)現(xiàn)的性能開銷略大一點(diǎn)，因?yàn)樵L問任意一個(gè)索引都要求跨越多個(gè)節(jié)點(diǎn)。插入元素時(shí)除了有跨越多個(gè)節(jié)點(diǎn)的性能開銷之外，還要有另外一個(gè)開銷，即創(chuàng)建節(jié)點(diǎn)對象的開銷。在優(yōu)勢方面，LinkedList實(shí)現(xiàn)的插入和刪除操作沒有其他開銷，因此，插入-刪除開銷幾乎完全依賴于插入-刪除點(diǎn)離集合末尾的遠(yuǎn)近。

ArrayList和Vector通常比LinkedList和同步封裝之后的LinkedList有著更好的性能。即使在你認(rèn)為LinkedList可能提供更高性能的情況下，你也可以通過修改元素加入的方式從ArrayList爭取更好的性能，例如翻轉(zhuǎn)集合元素的次序。

有些情況下LinkedList會有更好的性能，例如，當(dāng)大量元素需要同時(shí)加入到大型集合的開頭和末尾時(shí)。但一般而言，我建議你優(yōu)先使用ArrayList/Vector類，只有當(dāng)它們存在明顯的性能問題而LinkedList能夠改進(jìn)性能時(shí)，才使用LinkedList。