Java 數據結構：線性表順序存儲結構完整實現

Java 數據結構：線性表順序存儲結構完整實現

線性表是最基礎、最常用的數據結構之一。本文詳細講解線性表的順序存儲結構（動態數組實現），並提供功能完整、代碼規範的 Java 泛型實現，涵蓋增刪改查、擴容、遍歷等核心操作。

線性表基本特徵

• 有限序列：元素個數有限（n ≥ 0）。
• 有序性：元素之間存在順序關係，第一個元素無前驅，最後一個無後繼，其餘元素有且僅有一個前驅和後繼。
• 順序存儲：用一組地址連續的存儲單元依次存儲數據元素，邏輯鄰近物理鄰近。

SequenceList 類設計要點

• 泛型支持：SequenceList<T> 適配任意引用類型。
• 動態擴容：默認初始容量 2，不足時按 1.5~2 倍擴容（Arrays.copyOf）。
• 下標檢查：所有訪問操作均進行邊界驗證，拋出 IndexOutOfBoundsException。
• 核心字段：Object[] elementData 存儲數據，int size 記錄當前元素數，int capacity 記錄數組容量。

核心方法實現節選

插入元素 insert(T element, int index)

public void insert(T element, int index) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("數組越界異常");
    }
    ensureCapacity(size + 1);
    // 將 index 及之後元素後移一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

刪除元素 delete(int index)

public void delete(int index) {
    if (index < 0 || index > size - 1) {
        throw new IndexOutOfBoundsException("數組越界異常");
    }
    // 將 index 之後元素前移一位
    System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
    size--;
    elementData[size] = null; // 幫助 GC 回收
}

動態擴容 ensureCapacity(int minCapacity)

private void ensureCapacity(int minCapacity) {
    if (minCapacity > capacity) {
        capacity = minCapacity + 2; // 留餘量減少擴容頻率
        elementData = Arrays.copyOf(elementData, capacity);
    }
}

測試用例與運行結果

public static void main(String[] args) {
    SequenceList<String> list = new SequenceList<>();
    System.out.println("isEmpty: " + list.isEmpty()); // true

    list.add("3");
    list.insert("7", 0); // 頭部插入
    System.out.println("length: " + list.length()); // 2
    System.out.println("priorElem(1): " + list.priorElem(1)); // 7
    System.out.println("nextElem(0): " + list.nextElem(0)); // 3

    list.delete(1); // 刪除 "3"
    list.clear();   // 清空
}

運行結果截圖：

優化建議與擴展方向

1. 實現 Iterable<T> 接口，支持增強 for 循環遍歷。
2. 添加 indexOf/lastIndexOf 查找功能。
3. 引入縮容機制：元素數低於容量 25% 時縮減數組，釋放內存。
4. 線程安全版本：使用 ReentrantReadWriteLock 或 CopyOnWriteArrayList 思路實現併發安全。
5. 序列化支持：實現 Serializable 便於持久化與網絡傳輸。

總結

順序存儲結構隨機訪問 O(1)、內存局部性好、適合頻繁讀取、尾部增刪場景；但中間插刪需移動元素 O(n)、容量固定需擴容。掌握其實現細節是理解 ArrayList、Vector 等集合源碼的基石。