一、Vector和ArrayList的實現
Vector和ArrayList都帶有一個底層的Object[]數組，這個Object[]數組用來保存元素。通過索引訪問元素時，只需簡單地通過索引訪問內部數組的元素：
public?Object?get(int?index)
{?//首先檢查index是否合法...此處不顯示這部分代碼?return
elementData[index];?}
?
內部數組可以大于Vector/ArrayList對象擁有元素的數量，兩者的差值作為剩余空間，以便實現快速添加新元素。有了剩余空間，添加元素變得非常簡單，只需把新的元素保存到內部數組中的一個空余的位置，然后為新的空余位置增加索引值：
public?boolean?add(Object?o)
{?ensureCapacity(size?+?1);?//稍后介紹?elementData[size++]?=?o;?return?true;
//List.add(Object)?的返回值?}
?
把元素插入集合中任意指定的位置（而不是集合的末尾）略微復雜一點：插入點之上的所有數組元素都必須向前移動一個位置，然后才能進行賦值：
public?void?add(int?index,?Object?element)?{
//首先檢查index是否合法...此處不顯示這部分代碼
ensureCapacity(size+1);
System.arraycopy(elementData,?index,?elementData,?index?+?1,
size?-?index);
elementData[index]?=?element;
size++;
}
?
剩余空間被用光時，如果需要加入更多的元素，Vector/ArrayList對象必須用一個更大的新數組替換其內部Object[]數組，把所有的數組元素復制到新的數組。根據SDK版本的不同，新的數組要比原來的大50%或者100%（下面顯示的代碼把數組擴大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類的主要不同之處在于同步。除了兩個只用于串行化的方法，沒有一個ArrayList的方法具有同步執行的能力；相反，Vector的大多數方法具有同步能力，或直接或間接。因此，Vector是線程安全的，但ArrayList不是。這使得ArrayList要比Vector快速。對于一些最新的JVM，兩個類在速度上的差異可以忽略不計：嚴格地說，對于這些JVM，這兩個類在速度上的差異小于比較這些類性能的測試所顯示的時間差異。
通過索引訪問和更新元素時，Vector和ArrayList的實現有著卓越的性能，因為不存在除范圍檢查之外的其他開銷。除非內部數組空間耗盡必須進行擴展，否則，向列表的末尾添加元素或者從列表的末尾刪除元素時，都同樣有著優秀的性能。插入元素和刪除元素總是要進行數組復制（當數組先必須進行擴展時，需要兩次復制）。被復制元素的數量和[size-index]成比例，即和插入/刪除點到集合中最后索引位置之間的距離成比例。對于插入操作，把元素插入到集合最前面（索引0）時性能最差，插入到集合最后面時（最后一個現有元素之后）時性能最好。隨著集合規模的增大，數組復制的開銷也迅速增加，因為每次插入操作必須復制的元素數量增加了。
二、LinkedList的實現
LinkedList通過一個雙向鏈接的節點列表實現。要通過索引訪問元素，你必須查找所有節點，直至找到目標節點：
public?Object?get(intindex)?{
//首先檢查index是否合法...此處不顯示這部分代碼
Entry?e?=?header;?//開始節點
//向前或者向后查找，具體由哪一個方向距離較
//近決定
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;
}
?
把元素插入列表很簡單：找到指定索引的節點，然后緊靠該節點之前插入一個新節點：
public?void?add(int?index,?Object?element)?{
//首先檢查index是否合法...此處不顯示這部分代碼
Entry?e?=?header;?//starting?node
//向前或者向后查找，具體由哪一個方向距離較
//近決定
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得到一個線程安全的LinkedList，你可以利用一個同步封裝器從Collections.synchronizedList(List)得到一個。然而，使用同步封裝器相當于加入了一個間接層，它會帶來昂貴的性能代價。當封裝器把調用傳遞給被封裝的方法時，每一個方法都需要增加一次額外的方法調用，經過同步封裝器封裝的方法會比未經封裝的方法慢二到三倍。對于象搜索之類的復雜操作，這種間接調用所帶來的開銷不是很突出；但對于比較簡單的方法，比如訪問功能或者更新功能，這種開銷可能對性能造成嚴重的影響。
這意味著，和Vector相比，經過同步封裝的LinkedList在性能上處于顯著的劣勢，因為Vector不需要為了線程安全而進行任何額外的間接調用。如果你想要有一個線程安全的LinkedList，你可以復制LinkedList類并讓幾個必要的方法同步，這樣你可以得到一個速度更快的實現。對于所有其它集合類，這一點都同樣有效：只有List和Map具有高效的線程安全實現（分別是Vector和Hashtable類）。有趣的是，這兩個高效的線程安全類的存在只是為了向后兼容，而不是出于性能上的考慮。
對于通過索引訪問和更新元素，LinkedList實現的性能開銷略大一點，因為訪問任意一個索引都要求跨越多個節點。插入元素時除了有跨越多個節點的性能開銷之外，還要有另外一個開銷，即創建節點對象的開銷。在優勢方面，LinkedList實現的插入和刪除操作沒有其他開銷，因此，插入-刪除開銷幾乎完全依賴于插入-刪除點離集合末尾的遠近。
三、性能測試
這些類有許多不同的功能可以進行測試。LinkedList應用比較頻繁，因為人們認為它在隨機插入和刪除操作時具有較好的性能。所以，下面我分析的重點將是插入操作的性能，即，構造集合。我測試并比較了LinkedList和ArrayList，因為這兩者都是非同步的。
插入操作的速度主要由集合的大小和元素插入的位置決定。當插入點的位置在集合的兩端和中間時，最差的插入性能和最好的插入性能都有機會出現。因此，我選擇了三個插入位置（集合的開頭、末尾和中間），三種典型的集合大小：中等（100個元素），大型（10,000個元素），超大型（1,000,000個元素）。
在本文的測試中，我使用的是JAVA?SDK?1.2.0和1.3.0系列的SUN?JVM。此外，我還用HOTSPOT?JVM?2.0進行了測試，這個版本可以在1.3.0?SDK找到。在下面的表格中，各個測量得到的時間都以其中一次SDK?1.2?VM上的測試時間（表格中顯示為100%的單元）為基準顯示。測試期間使用了默認的JVM配置，即啟用了JIT編譯，因此對于所有JVM，堆空間都必須進行擴展，以避免內存溢出錯誤。表格中記錄的時間是多次測試的平均時間。為了避免垃圾收集的影響，在各次測試之間我強制進行了完全的內存清理（參見測試源代碼了解詳情）。磁盤監測確保磁盤分頁不會在測試過程中出現（任何測試，如果它顯示出嚴重的磁盤分頁操作，則被丟棄）。所有顯示出數秒應答時間的速度太慢的測試都重復進行，直至記錄到一個明顯合理的時間。
表1：構造一個中等大小的集合（100個元素）。括號中的數字針對預先確定大小的集合。?
?1.2?JVM?1.3?JVM?HotSpot?2.0?JVM?
總是插入到ArrayList的開頭?100%?(48.0%)?184.9%?(152.0%)?108.0%?(66.7%)?
總是插入到LinkedList的開頭?135.5%?109.1%?85.3%?
總是插入到ArrayList的中間?130.0%?(40.6%)?187.4%?(158.0%)?84.7%?(46.0%)?
總是插入到LinkedList的中間?174.0%?135.0%?102.3%?
總是插入到ArrayList的末尾?63.3%?(20.7%)?65.9%?(25.0%)?60.3%?(29.3%)?
總是插入到LinkedList的末尾?106.7%?86.3%?80.3%?
對于規模較小的集合，ArrayList和LinkedList的性能很接近。當元素插入到集合的末尾時，即追加元素時，ArrayList的性能出現了突變。然而，追加元素是ArrayList特別為其優化的一個操作：如果你只想要一個固定大小的靜態集合，Java數組（例如Object[]）比任何集合對象都具有更好的性能。除了追加操作，測量得到的時間數據差別不是很大，它們反映了各個JVM的優化程度，而不是其他什么東西。
例如，對于把元素插入到集合的開始位置來說（表1的前兩行），HotSpot?2.0?JVM加LinkedList具有最好的性能（85.3%），處于第二位的是?1.2?JVM加ArrayList（100%）。這兩個結果顯示出，1.2中簡單的JIT編譯器在執行迭代和復制數組等簡單的操作時具有很高的效率。在HotSpot中復雜的JVM加上優化的編譯器能夠改進復雜操作的性能，比如對象創建（創建LinkedList節點），并能夠利用代碼內嵌（code-inlining）的優勢。1.3?JVM的結果似乎顯示出，在簡單操作方面它的性能有著很大的不足，這一點很可能在以后的JVM版本中得到改進。
在這里我特別進行測試的是ArrayList相對于LinkedList的另一個優點，即預先確定集合大小的能力。具體地說，創建ArrayList的時候允許指定一個具體的大小（例如，在測試中ArrayList可以創建為擁有100個元素的容量），從而避免所有隨著元素增多而增加集合規模的開銷。表1括號中的數字顯示了預先確定集合大小時性能的提高程度。LinkedList（直到?SDK?1.3）不能預先確定大小。
此外，ArrayList只生成少量的需要進行垃圾收集的對象，即，用來保存元素的內部數組對象，以及每次ArrayList容量不足需要進行擴展時創建的附加內部數組對象。LinkedList不管可能出現的任何刪除操作，都為每一個插入操作生成一個節點對象。因此，LinkedList會給垃圾收集器帶來相當多的工作。考慮到這些因素，對于任何中小規模的集合，我會選擇使用ArrayList而不是LinkedList。
表2：構造一個大型集合（10,000個元素）?
?1.2?JVM?1.3?JVM?HotSpot?2.0?JVM?
總是插入到ArrayList的開頭?7773%?7537%?7500%?
總是插入到LinkedList的開頭?100%?90.34%?65.6%?
總是插入到ArrayList的中間?3318%?3412%?3121%?
總是插入到LinkedList的中間?26264%?14315%?14209%?
總是插入到ArrayList的末尾?41.4%?41.2%?37.5%?
總是插入到LinkedList的末尾?66.4%?73.9%?61.7%?
表2顯示了大規模集合的測試結果。可以看到，在出現大規模插入操作的時候，我們開始遭遇嚴厲的性能懲罰。正如我們前面分析類的實現所得到的結果，對于LinkedList來說最差的情形出現在把元素插入到集合中間時。另外我們還可以看到，與使用ArrayList時把元素插入到集合開頭的最差性能相比，使用LinkedList時把元素插入到集合中間的性能更差一些。和這兩種性能最差的情況相比，把元素插入到ArrayList中間的性能顯然要好得多。
總地看來，ArrayList再一次在大多數情形下表現出更好的性能，包括根據索引把元素插入到隨機位置的情形。如果你總是要把元素插入到集合中靠前的位置，LinkedList具有更好的性能；然而，此時你可以利用一個反向的ArrayList得到更好的性能，即，使用一個專用的實現，或者通過[size?-index]映射翻轉索引在集合中的位置。
表3：構造一個超大集合（1,000,000個元素）?
?1.2?JVM?1.3?JVM?HotSpot?2.0?JVM?
總是插入到ArrayList的開頭?太長?太長?太長?
總是插入到LinkedList的開頭?100%?179.5%?144.1%?
總是插入到ArrayList的中間?太長?太長?太長?
總是插入到LinkedList的中間?太長?太長?太長?
總是插入到ArrayList的末尾?38.3%?47.7%?42.9%?
總是插入到LinkedList的末尾?65.1%?161.5%?139.9%?
表3顯示了超大集合的測試結果，從該表可以得出的結論與表2非常相似。然而，表3強調的是，超大集合要求數據、集合類型、數據處理算法之間的恰到好處的配合；否則，你將得到事實上不可接受的性能表現。至于性能優化，你可以構造一個針對該問題的專用集合類。對于超大集合來說，為了獲得可接受的性能，構造專用集合類往往是很有必要的。
四、查詢的性能
在類的內部實現查詢時查詢的性能最高。對于查詢這些列表來說，迭代所有元素所需要的時間是一個限制因素。ArrayList/Vector類中實現的查詢將對類的元素進行迭代。下面的例子計算空元素的總數量：
int?count?=?0;
for?(int?i?=?0;?i?<?size;?i++)
if(elementData[i]?==?null)
count++;
LinkedList類中實現的查詢將搜索所有的節點。下面的例子計算所有空元素的總數量：
node?=?header.next;
count?=?0;
for?(int?i?=?0;?i?<?repeat;?i++,?node?=?node.next)
if?(node.element?==?null)
count++;
?
表4顯示出，ArrayList的性能顯著地超過了LinkedList，它再一次顯示出ArrayList應該是我們首選的類。表5顯示了利用從List.listIterator(int)獲得的ListIterator對象迭代所有元素所需要的時間，如果查詢機制不能在List內部實現，這些迭代器是必需的。ArrayList再一次顯示出了較高的性能，但這次性能的差異程度不象表4顯示的那樣不可思議。注意，表5所顯示的絕對時間相當于表4顯示絕對時間的10倍，即，ArrayList內部遍歷大約比ArrayList利用ListIterator迭代要快10倍。
表4：通過內部訪問迭代集合中的所有元素?
?1.2?JVM?1.3?JVM?HotSpot?2.0?JVM?
ArrayList內部搜索?100%?106%?197%?
LinkedList內部搜索?470%?493%?448%?
表5：通過ListIterator遍歷集合中的所有元素?
?1.2?JVM?1.3?JVM?HotSpot?2.0?JVM?
利用ListIterator迭代ArrayList?100%?118%?75.2%?
利用ListIterator迭代ListedList?117%?186%?156%?
■?結束語
實際測量和我們所考慮的其他因素都清楚地顯示出，ArrayList和Vector通常比LinkedList和同步封裝之后的LinkedList有著更好的性能。即使在你認為LinkedList可能提供更高性能的情況下，你也可以通過修改元素加入的方式從ArrayList爭取更好的性能，例如翻轉集合元素的次序。
有些情況下LinkedList會有更好的性能，例如，當大量元素需要同時加入到大型集合的開頭和末尾時。但一般而言，我建議你優先使用ArrayList/Vector類，只有當它們存在明顯的性能問題而LinkedList能夠改進性能時，才使用LinkedList。