Java 數據結構基石：線性表的順序與鏈式實現全解析

線性表 ADT 定義

public interface IList<T> {
    boolean isEmpty();
    int length();
    T get(int i);
    void set(int i, T x);
    void append(T x);
    T remove(int i);
    void removeAll();
    T search(T key);
    void insert(int i, T x);
    void insert(T x);      // 有序插入
    void remove(T x);      // 有序刪除
}

順序表（動態數組）

內部結構

private Object[] elements; // 底層數組
private int size;          // 當前長度

• 構造時分配初始容量 (如 10)
• 擴容策略：滿時創建 2倍 數組，System.arraycopy 遷移

關鍵操作

• 插入：i 及之後元素**向後移動**，再賦值 elements[i]=x，size++
• 刪除：i+1 及之後元素**向前移動**，size--
• get/set：O(1) 直接索引

效率分析

結論：**靜態查詢快，動態增刪慢**，適合「讀多寫少」場景。

單鏈表

節點定義

class Node<T> {
    T data;
    Node<T> next;
    Node(T d, Node<T> n) { data=d; next=n; }
}

帶**頭節點**簡化邊界處理：head.next 指向首元素。

核心操作

• 長度：遍歷計數 O(n)
• get(i)：從頭節點走 i+1 步 O(n)
• insert(i, x)：找到第 i-1 個節點 p，p.next = new Node(x, p.next) O(1) (不含查找)
• remove(i)：找到第 i-1 個節點 p，p.next = p.next.next O(1) (不含查找)
• append(x)：insert(MAX_VALUE, x) 利用循環終止條件自然插到尾部

有序單鏈表

• 元素實現 Comparable<T>
• 有序插入：尋找首個 p.next.data >= x 的前驅 p，插入其後
• 有序刪除：尋找 p.next.data == x 的前驅 p，刪除 p.next

雙向鏈表 / 循環雙鏈表

節點增強

class DNode<T> {
    T data;
    DNode<T> prev, next;
}

循環雙鏈表特性

• 空表時 head.next == head && head.prev == head
• 插入/刪除需同時維護 prev 和 next 兩個方向
• 操作邏輯與單鏈表對稱，代碼量約 2 倍

效率對比總結

實戰啟示

• ArrayList 底層即順序表，LinkedList 為雙向鏈表
• 高頻隨機讀 → ArrayList；高頻首尾增刪/中間迭代器操作 → LinkedList
• 理解底層結構是閱讀 JDK 集合源碼、優化性能的前提