知識星球（給ImportNew加星標，提高Java技能）
來自：唐尤華
https://dzone.com/articles/arraylist-or-linkedlist
本文旨在為 Java 開發這擇合適的順序資料結構提供指導。
Arraylist 和 LinkedList 是 Java 集合框架中用來儲存物件取用串列的兩個類。Arraylist 和 LinkedList 都實現 List 介面。首先，讓我們瞭解一下它們最重要的父介面——List。
1. List 介面
串列（list）是元素的有序集合，也稱為序列。它提供了基於元素位置的操作，有助於快速訪問、新增和刪除串列中特定索引位置的元素。List 介面實現了 Collection 和 Iterable 作為父介面。它允許儲存重覆值和空值，支援透過索引訪問元素。
2. 用法
下麵是使用 List 介面宣告 ArrayList 和 LinkedList 的程式碼片段。
import java.util.*;
public class MyClass {
// 非同步或非執行緒安全
List
Vector 與 ArrayList 類似，只是它們支援自動同步，這也使得 Vector 執行緒安全，但同時會帶來一些效能損耗。
3. 內部實現
3.1 LinkedList 內部實現
Linkedlist 資料結構包含一組有序的資料元素，稱為節點。每個元素都包含對其後續元素，即下一個元素的連結或取用。 序列的最後一個元素（尾部）指向空元素。鏈表本身包含對連結串列第一個元素的取用，該元素稱為 head 元素。Java 中的 LinkedList 是 List 介面的雙向連結串列。在雙向連結串列中，每個節點都指向它的上一個節點和下一個節點。此外，它還實現了其他介面，比如 Serializable、 Cloneable 和 Deque（實現 Queue 作為父介面）。
3.2 ArrayList 內部實現
Arraylist 是可調整大小的陣列，實現了 List 介面。 它的內部是一個物件陣列，可以根據需要擴容支援在集合中加入更多元素。可以透過建構式 ArrayList(int initialCapacity)指定 ArrayList 的初始容量，然後在必要時使用 void ensureCapacity(int minCapacity) 增加容量，確保至少可以容納初始化時最小容量引數指定數量的元素。
它還提供一個方法 void trimToSize()，可以減少現有元素的大小。
// 呼叫建構式 ArrayList(initialCapacity)
List arr = new ArrayList(10);
預設情況下，ArrayList 建立初始容量為10的串列，而 LinkedList 只構造一個沒有設定任何初始容量的空串列。 Linkedlist 不實現 RandomAccess 介面，而 ArrayList 實現了 RandomAccess 介面（而非 Deque 介面）。
4. 各種操作的時空複雜性
5. 小貼士
考慮下麵遍歷 LinkedList 的示例程式碼。在這段程式碼中遍歷會非常慢，因為 LinkedList 不支援隨機訪問，因此每次遍歷都會帶來巨大的開銷。
LinkedList ll = new LinkedList();
…
…
Object o = null;
for (int i = 0; i < list.size(); i++)
{
o = list.get(i);
…
}
一個更好的方法可提高效能，像下麵這段程式碼。
LinkedList ll = new LinkedList();
…
…
Object o = null;
ListIterator li = list.listIterator(0);
while (li.hasNext()){
o = ll.next();
…
}
6. 總結
相比較而言 Arraylist 更快而且更好，因為它支援對其元素的隨機訪問。 遍歷連結串列或在中間插入新元素開銷很大，因為必須遍歷每個元素而且很可能遇到快取失敗。 如果需要在一次迭代中對串列中的多個專案執行處理，那麼 LinkedList 的開銷比 Arraylist 使用時多次複製陣列元素的開銷要小。
歡迎分享你對這個話題的經驗與見解，請在文章的評論區中提出你的想法。
看完本文有收穫？請轉發分享給更多人
關註「ImportNew」，提升Java技能
喜歡就點「好看」唄~
