Java 手寫 ArrayList：順序表 (Sequence List) 完整實作

資料結構基礎：順序表

順序表 (Sequence List) 以**連續記憶體空間** (陣列) 儲存元素，邏輯順序與物理順序一致。特點：

• ✅ 隨機存取 O(1) — get(index) 極快
• ❌ 插入/刪除 O(n) — 需搬移元素
• ❌ 容量固定/擴容昂貴 — 需手動管理擴容策略

Java ArrayList 即是順序表的工業級實作。本文從零手寫一個簡化版 LineList<E>，掌握核心機制。

完整原始碼 (支援泛型、自動擴容、完整 CRUD)

import java.util.Arrays;

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

    // ---- 建構子 ----
    public LineList() { this(DEFAULT_CAPACITY); }
    public LineList(int capacity) {
        if (capacity < 0) throw new IllegalArgumentException("Capacity: " + capacity);
        array = new Object[capacity];
    }
    public LineList(E element) { this(element, DEFAULT_CAPACITY); }
    public LineList(E element, int capacity) {
        this(capacity);
        add(element);
    }

    // ---- 核心擴容邏輯 ----
    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);
        }
    }

    // ---- 基本操作 ----
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }

    public boolean add(E e) {
        ensureCapacity(size + 1);
        array[size++] = e;
        return true;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);
        System.arraycopy(array, index, array, index + 1, size - index);
        array[index] = element;
        size++;
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        rangeCheck(index);
        return (E) array[index];
    }

    @SuppressWarnings("unchecked")
    public E set(int index, E element) {
        rangeCheck(index);
        E old = (E) array[index];
        array[index] = element;
        return old;
    }

    @SuppressWarnings("unchecked")
    public E remove(int index) {
        rangeCheck(index);
        E old = (E) array[index];
        fastRemove(index);
        return old;
    }

    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
    }

    public boolean removeAll(E e) {
        boolean modified = false;
        for (int i = 0; i < size; ) {
            if (eq(e, array[i])) {
                fastRemove(i);
                modified = true;
            } else {
                i++;
            }
        }
        return modified;
    }

    public void clear() {
        Arrays.fill(array, 0, size, null);
        size = 0;
    }

    // ---- 查詢操作 ----
    public int indexOf(E e) {
        for (int i = 0; i < size; i++)
            if (eq(e, array[i])) return i;
        return -1;
    }

    public int lastIndexOf(E e) {
        for (int i = size - 1; i >= 0; i--)
            if (eq(e, array[i])) return i;
        return -1;
    }

    public boolean contains(E e) { return indexOf(e) >= 0; }

    // ---- 切片 ----
    @SuppressWarnings("unchecked")
    public LineList<E> subList(int from, int to) {
        if (from < 0 || to >= size || from > to)
            throw new IndexOutOfBoundsException();
        LineList<E> sub = new LineList<>(to - from + 1);
        for (int i = from; i <= to; i++) sub.add((E) array[i]);
        return sub;
    }

    public Object[] toArray() { return Arrays.copyOf(array, size); }

    // ---- 工具方法 ----
    private boolean eq(Object a, Object b) {
        return a == null ? b == null : a.equals(b);
    }
    private void rangeCheck(int index) {
        if (index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
}

關鍵設計解析

1. 泛型擦除與轉型：底層用 Object[]，取出時 @SuppressWarnings("unchecked") 強轉 (E)，這正是 JDK 集合的標準做法。
2. 擴容策略 1.5 倍：newCapacity = old + (old >> 1)，平衡記憶體浪費與擴容頻率。
3. System.arraycopy 原生搬移：JVM 內部優化，比手寫迴圈快數倍，插入/刪除/擴容全靠它。
4. 釋放引用：clear()、fastRemove() 將舊位置設 null，避免記憶體洩漏 (Obsolete Reference)。
5. 索引檢查分離：rangeCheck 用於存取，rangeCheckForAdd 允許 index == size (尾插)。

效能對照 (百萬級資料)

總結

手寫順序表能深入理解 ArrayList 核心：陣列 + 擴容 + 搬移 + 索引檢查。掌握這些細節，面試手寫集合、排查生產效能問題都將得心應手。