您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

Java 集合深度剖析（二）：List 介面與 ArrayList、LinkedList 實作原理

編輯：Java 綜合教學

List 介面與抽象骨架

List 繼承 Collection，定義有序集合操作，支援指定位置插入。反編譯 List.java 可見完整契約：

public interface java.util.List<E> extends java.util.Collection<E> {
    int size(); boolean isEmpty(); boolean contains(Object o);
    Iterator<E> iterator(); Object[] toArray(); <T> T[] toArray(T[] a);
    boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c); boolean addAll(int, Collection<? extends E> c);
    boolean removeAll(Collection<?> c); boolean retainAll(Collection<?> c);
    void replaceAll(UnaryOperator<E> op); void sort(Comparator<? super E> c);
    void clear(); boolean equals(Object o); int hashCode();
    E get(int index); E set(int index, E element);
    void add(int index, E element); E remove(int index);
    int indexOf(Object o); int lastIndexOf(Object o);
    ListIterator<E> listIterator(); ListIterator<E> listIterator(int index);
    List<E> subList(int from, int to);
    Spliterator<E> spliterator();
}

JDK 8 新增 default 方法（sort、replaceAll、spliterator）。List 提供隨機存取方法（get(int)），但不保證效率。為此引入標記介面 RandomAccess（無方法），ArrayList 實作之，用於執行期檢測：

if (list instanceof RandomAccess) { /* 隨機存取演算法 */ }
else { /* 循序存取演算法 */ }

常規方法在 AbstractList 實作（isEmpty、contains 等），隨機存取類別優先繼承此類。AbstractList 關鍵欄位 modCount 追蹤結構性修改次數（增刪改變長度），供迭代器檢測並發修改。

AbstractSequentialList 針對循序存取優化（如 LinkedList），實作部分介面方法。

鏈結串列：LinkedList 深度解析

結構設計

雙向鏈結串列，每節點含前驅、後繼引用。三核心欄位：

transient int size;
transient Node<E> first;
transient Node<E> last;

靜態內部類 Node<E>：

private static class Node<E> {
    E item;
    Node<E> next, prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element; this.next = next; this.prev = prev;
    }
}

兩構造器：無參建空串列，帶 Collection 參數依集合元素建構。

六大核心鏈表操作（私有工具方法）

所有結構性修改均基於此六方法，均更新 size 與 modCount：

linkFirst(E)：頭部插入
linkLast(E)：尾部插入
linkBefore(E, Node<E>)：指定節點前插入
unlinkFirst(Node<E>)：刪除頭節點並回傳值
unlinkLast(Node<E>)：刪除尾節點並回傳值
unlink(Node<E>)：刪除指定節點

原始碼實作展示標準鏈表指針操作（含 GC 輔助置空）。

列表迭代器：ListIterator 介面與 ListItr 實作

ListIterator 繼承 Iterator，新增雙向遍歷與修改方法：

interface ListIterator<E> extends Iterator<E> {
    void add(E e); boolean hasPrevious(); E previous();
    int nextIndex(); int previousIndex(); void remove(); void set(E e);
}

LinkedList.listIterator() 回傳內部類 ListItr 實例。迭代器概念上位於元素間（n 元素有 n+1 位置），以游標模型操作。

ListItr 關鍵欄位：

nextIndex：下次 next() 回傳元素索引
expectedModCount：快照 modCount，checkForComodification() 比對，不一致拋 ConcurrentModificationException
lastReturned、next：追蹤上次回傳與下一節點

next()/previous() 移動游標並更新索引與節點引用。add()/remove() 修改結構並更新 expectedModCount；set() 僅替換值不影響結構。remove() 執行後將 lastReturned=null，故連續呼叫會拋 IllegalStateException，必須交替呼叫 next()/previous()。

隨機存取效能陷阱

LinkedList 不支援快速隨機存取，get(n) 需從較近端（頭/尾）遍歷。嚴禁使用索引迴圈遍歷：

for (int i=0; i<list.size(); i++) { doSomething(list.get(i)); } // 極低效，每次從頭搜尋

應使用迭代器或增強型 for 迴圈。

綜合範例

List<String> a = new LinkedList<>();
a.add("A"); a.add("C"); a.add("E");
List<String> b = new LinkedList<>();
b.add("B"); b.add("D"); b.add("F"); b.add("G");

ListIterator<String> aIter = a.listIterator();
Iterator<String> bIter = b.iterator();
while (bIter.hasNext()) {
    if (aIter.hasNext()) aIter.next();
    aIter.add(bIter.next()); // 交織合併
}
System.out.println(a); // [A, B, C, D, E, F, G]

bIter = b.iterator();
while (bIter.hasNext()) {
    bIter.next();
    if (bIter.hasNext()) { bIter.next(); bIter.remove(); } // 每隔一刪除
}
System.out.println(b); // [B, D, F]

a.removeAll(b);
System.out.println(a); // [A, C, E, G]

動態陣列：ArrayList

封裝動態重新配置的物件陣列。對比 Vector（所有方法同步），ArrayList 非同步，單線程環境效能更優。實作 RandomAccess，支援高效隨機存取。擴容機制：預設初始容量 10，擴容 1.5 倍（newCapacity = oldCapacity + (oldCapacity >> 1)）。核心方法（add、get、set、remove）均直接操作底層陣列，remove 需 System.arraycopy 位移後續元素。

詳細實作與擴容策略將於後續專文深入分析。