Java 實現序列列表：基於陣列的動態線性表完整原始碼解析

序列列表是資料結構中最基礎的線性表實作，以陣列為底層儲存，支援動態擴容。本文提供一個泛型 LineList<E> 完整實作，涵蓋增刪改查、擴容策略、索引檢查、子列表截取等核心功能，適合教學與面試準備。

完整原始碼

import java.util.Arrays;

public class LineList<E> {
    private int size;              // 當前元素個數
    private Object[] array;        // 底層陣列
    private static final int DEFAULT_CAPACITY = 16;  // 預設容量

    /** 無參建構子：使用預設容量 */
    public LineList() {
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }

    /** 指定初始容量 */
    public LineList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("非法容量: " + capacity);
        }
        this.array = new Object[capacity];
        this.size = 0;
    }

    /** 指定首個元素與容量 */
    public LineList(E element, int capacity) {
        if (capacity < 1) {
            throw new IllegalArgumentException("容量至少為 1");
        }
        this.array = new Object[capacity];
        this.array[0] = element;
        this.size = 1;
    }

    /** 指定首個元素 (預設容量) */
    public LineList(E element) {
        this.array = new Object[DEFAULT_CAPACITY];
        this.array[0] = element;
        this.size = 1;
    }

    // ==================== 查詢操作 ====================
    
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    
    public boolean contains(E e) { return indexOf(e) != -1; }
    
    public Object[] toArray() { return Arrays.copyOf(array, size); }
    
    @SuppressWarnings("unchecked")
    public E get(int index) {
        checkIndex(index);
        return (E) array[index];
    }
    
    public int indexOf(E e) {
        if (e == null) {
            for (int i = 0; i < size; i++) if (array[i] == null) return i;
        } else {
            for (int i = 0; i < size; i++) if (e.equals(array[i])) return i;
        }
        return -1;
    }
    
    public int lastIndexOf(E e) {
        if (e == null) {
            for (int i = size - 1; i >= 0; i--) if (array[i] == null) return i;
        } else {
            for (int i = size - 1; i >= 0; i--) if (e.equals(array[i])) return i;
        }
        return -1;
    }

    // ==================== 修改操作 ====================
    
    /** 尾部新增 */
    public void add(E e) {
        ensureCapacity(size + 1);
        array[size++] = e;
    }
    
    /** 指定索引插入 */
    public void add(int index, E element) {
        checkIndexForAdd(index);  // 允許 index == size (尾部插入)
        ensureCapacity(size + 1);
        System.arraycopy(array, index, array, index + 1, size - index);
        array[index] = element;
        size++;
    }
    
    /** 替換指定索引元素 */
    @SuppressWarnings("unchecked")
    public E set(int index, E element) {
        checkIndex(index);
        E old = (E) array[index];
        array[index] = element;
        return old;
    }
    
    /** 移除指定索引元素 */
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        checkIndex(index);
        E removed = (E) array[index];
        fastRemove(index);
        return removed;
    }
    
    /** 移除所有符合元素 */
    public void removeAll(E e) {
        if (e == null) {
            for (int i = 0; i < size; i++) {
                if (array[i] == null) fastRemove(i);
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (e.equals(array[i])) fastRemove(i);
            }
        }
    }
    
    /** 清空列表 */
    public void clear() {
        Arrays.fill(array, null);
        size = 0;
    }

    // ==================== 進階操作 ====================
    
    /** 截取子列表 [fromIndex, toIndex] 閉區間 */
    public LineList<E> subList(int fromIndex, int toIndex) {
        if (fromIndex < 0 || fromIndex >= size) {
            throw new IndexOutOfBoundsException("起始索引越界: " + fromIndex);
        }
        if (toIndex < 0 || toIndex >= size) {
            throw new IndexOutOfBoundsException("結束索引越界: " + toIndex);
        }
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException("起始索引不可大於結束索引");
        }
        
        LineList<E> sub = new LineList<>();
        for (int i = fromIndex; i <= toIndex; i++) {
            sub.add((E) array[i]);
        }
        return sub;
    }

    // ==================== 內部輔助方法 ====================
    
    /** 擴容確保最小容量 */
    private void ensureCapacity(int minCapacity) {
        if (minCapacity - array.length > 0) {
            int newCapacity = array.length + (array.length >> 1);  // 1.5 倍擴容
            if (newCapacity < minCapacity) newCapacity = minCapacity;
            if (newCapacity > Integer.MAX_VALUE - 8) newCapacity = Integer.MAX_VALUE;
            array = Arrays.copyOf(array, newCapacity);
        }
    }
    
    /** 快速移除 (內部用，不做索引檢查) */
    private void fastRemove(int index) {
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(array, index + 1, array, index, numMoved);
        }
        array[--size] = null;  // 釋放引用助 GC
    }
    
    /** 索引檢查 (查詢/修改/刪除用，範圍 [0, size-1]) */
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界: " + index + ", size: " + size);
        }
    }
    
    /** 插入索引檢查 (範圍 [0, size]) */
    private void checkIndexForAdd(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("插入索引越界: " + index + ", size: " + size);
        }
    }
}

核心設計亮點解析

關鍵方法時間複雜度

與 JDK ArrayList 差異補充

• 無 Iterator 實作：教學簡化，實際需實作 Iterable<E> 介面
• 無 modCount 機制：多執行緒下迭代不安全，JDK 透過 modCount 實現 fail-fast
• subList 回傳新實例：JDK 回傳 SubList 視圖，共享底層陣列，修改會同步反映
• 未實作 Collection/List 介面：教學專用，生產環境請直接使用 ArrayList
• 擴容上限處理：Integer.MAX_VALUE - 8 為 JVM 陣列最大長度保留空間

測試驗證範例

public static void main(String[] args) {
    LineList<String> list = new LineList<>();
    list.add("A"); list.add("B"); list.add("C");
    list.add(1, "X");  // [A, X, B, C]
    System.out.println(Arrays.toString(list.toArray()));
    
    list.remove(2);    // 移除 B -> [A, X, C]
    list.set(0, "Z");  // [Z, X, C]
    System.out.println("索引 1: " + list.get(1));  // X
    System.out.println("長度: " + list.size());    // 3
    System.out.println("包含 X: " + list.contains("X"));  // true
    System.out.println("X 索引: " + list.indexOf("X"));   // 1
    
    LineList<String> sub = list.subList(0, 1);  // [Z, X]
    System.out.println("子列表: " + Arrays.toString(sub.toArray()));
}

1. 上一篇文章： Java 隨機字串產生器：支援字母、數字、符號任意組合的靈活工具類
2. 下一篇文章： Java 爬蟲實戰：采集京東收貨地址行政區劃資料 (省/市/區/街道四級)

Java 程式設計入門

再論 Java Swing 執行緒模型

不正確的 Swing 執行緒是導致 Swing 應用運行緩慢

Java 並發容器深度解析：同步容器 vs 並發容器、ConcurrentHashMap 核心原理與鎖分段技術

同步容器 vs 並發容器：核心差異 維度同步容器並發容器

Ant 構建工具入門：環境配置、build.xml 編寫與專案構建圖文教程

Ant 是什麼？ 基於 Java 的構建工具，用 XML (

Java IO 流與檔案操作完全指南：從位元組流到字元流

Java IO 流與檔案操作完全指南：從位元組流到字元流 j