您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 實現順序存儲線性表（Sequence List）完整代碼與解析

編輯：Java 相關知識

順序存儲線性表是數據結構入門的核心內容，本文提供一個基於泛型、支援動態擴容（模擬）、完整 CRUD 操作的 Java 實現，並對關鍵邏輯進行深度解析，適合教學演示與面試準備。

核心設計決策

泛型支援：`SquenceList` 實現類型安全。
底層數組：`Object[] listArray` 存儲元素，避開泛型數組創建限制。
容量管理：構造函數指定初始容量，簡化版不實現自動擴容（教學常見簡化），超容拋出提示。
索引約定：對外暴露 1-based 索引（符合教材習慣），內部 0-based 操作，轉換集中在公共方法。

完整源碼

package com.ncu.list;

/**
 * 順序存儲線性表（教學演示版）
 * 
 * 特性：泛型、固定容量、1-based 索引對外、基礎 CRUD
 * 
 */
public class SquenceList {

    private int capacity;           // 最大容量
    private Object[] elements;      // 底層數組
    private int size = 0;           // 當前元素個數

    public SquenceList() {
        this(10);                   // 默認容量 10
    }

    public SquenceList(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("Capacity must be positive");
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    // ==================== 核心輔助方法 ====================

    /**
     * 索引合法性檢查（1-based）
     */
    private void checkIndex(int index) {
        if (index < 1 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * 插入位置合法性檢查（1-based，允許 size+1 即尾插）
     */
    private void checkInsertIndex(int index) {
        if (index < 1 || index > size + 1) {
            throw new IndexOutOfBoundsException("Insert index: " + index + ", Size: " + size);
        }
    }

    /**
     * 容量檢查
     */
    private void ensureCapacity() {
        if (size >= capacity) {
            throw new IllegalStateException("List is full, capacity: " + capacity);
        }
    }

    // ==================== 基礎查詢 ====================

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 獲取指定位置元素（1-based）
     */
    @SuppressWarnings("unchecked")
    public T get(int index) {
        checkIndex(index);
        return (T) elements[index - 1];
    }

    // ==================== 插入操作 ====================

    /**
     * 尾部插入
     */
    public void add(T element) {
        ensureCapacity();
        elements[size++] = element;
    }

    /**
     * 指定位置插入（1-based）
     * 將 index 及之後元素向後移動一位
     */
    public void add(T element, int index) {
        checkInsertIndex(index);
        ensureCapacity();

        // 從後向前移動，避免覆蓋
        for (int i = size; i >= index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index - 1] = element;
        size++;
    }

    // ==================== 刪除操作 ====================

    /**
     * 按位置刪除（1-based）
     */
    @SuppressWarnings("unchecked")
    public T remove(int index) {
        checkIndex(index);
        T removed = (T) elements[index - 1];

        // 從前向後移動，覆蓋被刪位置
        for (int i = index; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null; // 幫助 GC
        return removed;
    }

    /**
     * 按元素刪除首次出現
     */
    public boolean removeElement(T element) {
        for (int i = 0; i < size; i++) {
            if (element == null ? elements[i] == null : element.equals(elements[i])) {
                remove(i + 1); // 轉 1-based
                return true;
            }
        }
        return false;
    }

    // ==================== 其他操作 ====================

    /**
     * 刪除最後一個元素
     */
    public void deleteLast() {
        if (isEmpty()) {
            throw new IllegalStateException("List is empty");
        }
        elements[--size] = null;
    }

    /**
     * 清空列表
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 打印所有元素
     */
    public void showList() {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }
        for (int i = 0; i < size; i++) {
            System.out.println("[" + (i + 1) + "] " + elements[i]);
        }
        System.out.println("------------ size=" + size);
    }

    // ==================== 測試入口 ====================
    public static void main(String[] args) {
        SquenceList list = new SquenceList<>(10);

        // 尾插
        list.add(10);
        list.add(20);
        list.add(30);
        System.out.println("After tail insert:");
        list.showList(); // [1]10 [2]20 [3]30

        // 指定位置插入
        list.add(15, 2); // 在位置 2 插入 15
        System.out.println("After insert 15 at pos 2:");
        list.showList(); // [1]10 [2]15 [3]20 [4]30

        // 獲取元素
        System.out.println("Element at pos 3: " + list.get(3)); // 20

        // 按位置刪除
        list.remove(2); // 刪除 15
        System.out.println("After remove pos 2:");
        list.showList(); // [1]10 [2]20 [3]30

        // 按元素刪除
        list.removeElement(30);
        System.out.println("After remove element 30:");
        list.showList(); // [1]10 [2]20

        // 邊界測試
        try {
            list.add(99, 5); // 非法位置
        } catch (IndexOutOfBoundsException e) {
            System.out.println("Expected exception: " + e.getMessage());
        }
    }
}

關鍵邏輯深度解析

1. 插入位置元素後移算法

for (int i = size; i >= index; i--) {
    elements[i] = elements[i - 1];
}

逆序遍歷：從 `size` 遞減到 `index`，避免前序覆蓋導致數據丟失。
索引映射：外部 1-based `index` 對應內部 `index-1`，移動後新元素落在 `elements[index-1]`。
時間複雜度：O(n - index + 1)，最壞 O(n)（頭插）。

2. 刪除位置元素前移算法

for (int i = index; i < size; i++) {
    elements[i - 1] = elements[i];
}
elements[--size] = null;

順序遍歷：從 `index` 到 `size-1`，將後續元素前移一位覆蓋被刪位置。
置 null 幫助 GC：釋放最後一個元素引用，避免對象游離。
時間複雜度：O(size - index)，最壞 O(n)（頭刪）。

3. 1-based vs 0-based 索引轉換策略

教材習慣 1-based，Java 數組 0-based。本實現採用公共方法統一轉換策略：

對外：`get(1)` 返回第一個元素，`add(e, 1)` 頭插。
內部：統一轉為 `index-1` 操作數組。
優勢：封裝性好，調用方無需關心內部索引規則。

擴展方向（生產級增強）

功能	實現思路
動態擴容	`ensureCapacity()` 中 `Arrays.copyOf(elements, newCapacity)`，擴容因子 1.5
實現 List 接口	`implements List`，補全所有接口方法，可直接替換 ArrayList
迭代器支援	實現 `Iterable`，內部類實現 `Iterator`，支援增強 for
序列化	實現 `Serializable`，`elements` 标记 `transient`，自定義 `writeObject/readObject`
並發安全	加 `ReentrantReadWriteLock` 或使用 `CopyOnWriteArrayList` 替代