實現 List 的類 - 優點和缺點

Created: November-22, 2018

該 List 介面是由不同的類實現的。他們每個人都有自己的方式來實施不同的策略，並提供不同的利弊。

實現 List 的類

這些是 Java SE 8 中實現 java.util.List 介面的所有 public 類：

抽象類：
- AbstractList 中
- AbstractSequentialList
具體類：
- 陣列列表
- AttributeList
- CopyOnWriteArrayList
- 連結串列
- RoleList
- RoleUnresolvedList
- 堆
- 向量

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList 是 List 介面的可調整大小的陣列實現。將列表儲存到陣列中， ArrayList 提供了用於運算元組大小的方法（除了實現 List 介面的方法）。

List<Integer> myList = new ArrayList<Integer>(100); // Constructs an empty list with the specified initial capacity.

size，isEmpty， get ， set ，iterator 和 listIterator 操作以恆定時間執行。因此獲取和設定 List 的每個元素具有相同的時間成本 ：

int e1 = myList.get(0);  //   \
int e2 = myList.get(10); //    | => All the same constant cost => O(1)
myList.set(2,10);        //   /

使用陣列（靜態結構）實現在陣列大小上新增元素的成本很高，因為需要為所有陣列進行新的分配。但是，從文件：

新增操作以分攤的常量時間執行，即新增 n 個元素需要 O(n) 時間

刪除元素需要 O(n) 時間。

來了

來了

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList 由雙向連結串列實現，連結串列資料結構由一組稱為節點的順序連結記錄組成。

List<Integer> myList = new LinkedList<Integer>(); // Constructs an empty list.

在列表的前面或末尾新增或刪除元素具有恆定的時間。

myList.add(10);  // \
myList.add(0,2); //  | => constant time => O(1)
myList.remove(); // /

- CONS： 來自文件：

索引到列表中的操作將從開頭或結尾遍歷列表，以較接近指定索引為準。

操作如：

myList.get(10);    // \
myList.add(11,25); //  | => worst case done in O(n/2)
myList.set(15,35); // /

來了

來了

來了

來了