陣列的定義#

陣列（Array）是一種線性表資料結構，用一組連續的記憶體空間，來儲存一組具有相同類型的資料。

兩個關鍵特性：

1. 連續的記憶體空間
2. 相同類型的資料

這兩個限制讓陣列有了「殺手鐧」特性：隨機存取。但也讓插入、刪除操作變得低效。

隨機存取的原理#

假設陣列 int[] a = new int[10]，記憶體分配了 1000 ～ 1039 的連續空間，首地址 base_address = 1000。

尋址公式：

a[i]_address = base_address + i * data_type_size

對於 int 類型，data_type_size = 4，所以：

• a[0] 的地址 = 1000 + 0 × 4 = 1000
• a[5] 的地址 = 1000 + 5 × 4 = 1020

很多人說「陣列適合查找，查找時間複雜度為 O(1)」——這是不準確的。正確說法是：陣列支援隨機存取，根據下標隨機存取的時間複雜度為 O(1)。即使是排序好的陣列，二分查找的時間複雜度也是 O(log n)。

為什麼陣列從 0 開始編號？#

從尋址公式來看，「下標」本質上是「偏移（offset）」：

• a[0] = 偏移 0 個位置 = 首地址
• a[k] = 偏移 k 個位置

如果從 1 開始編號，公式變成：

a[k]_address = base_address + (k-1) * type_size

每次存取都多一次減法運算。為了效能極致優化，選擇從 0 開始。

更主要的原因可能是歷史因素——C 語言設計者這樣做，後續語言沿用了這個習慣。實際上，Matlab 從 1 開始，Python 還支援負數下標。

插入與刪除操作#

插入操作#

在第 k 個位置插入元素，需要將 k ～ n 的元素都往後移動一位。

如果陣列資料沒有順序要求，可以直接把第 k 位的資料移到末尾，新元素放入第 k 位，時間複雜度降為 O(1)。這個技巧在快速排序中會用到。

刪除操作#

刪除第 k 個位置的資料，同樣需要搬移資料。

可以先標記刪除，等陣列空間不足時再一次性真正刪除。這正是 JVM 標記清除垃圾回收演算法的核心思想。

陣列越界問題#

int main() {
    int i = 0;
    int arr[3] = {0};
    for (; i <= 3; i++) {  // 錯誤：應該是 i < 3
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

這段 C 程式碼會無限列印 “hello world”，因為 arr[3] 越界存取到了變數 i 的記憶體地址，arr[3] = 0 相當於 i = 0。

C 語言不會自動檢查陣列越界，這是常見的安全漏洞來源。Java 等語言會拋出 ArrayIndexOutOfBoundsException。

陣列 vs 容器（ArrayList）#

ArrayList 優勢#

1. 封裝操作細節：插入、刪除時的資料搬移自動處理
2. 支援動態擴容：空間不足時自動擴容為 1.5 倍

擴容涉及記憶體申請和資料搬移，比較耗時。如果事先知道資料大小，建議在建立 ArrayList 時指定容量。

// 推薦做法
ArrayList<User> users = new ArrayList<>(10000);
for (int i = 0; i < 10000; ++i) {
    users.add(xxx);
}

何時選擇陣列#

1. 效能敏感：ArrayList 無法存儲基本類型（int、long），需要封裝為 Integer、Long，有 Autoboxing/Unboxing 開銷
2. 資料大小已知：且操作簡單，用不到 ArrayList 大部分方法
3. 多維陣列：Object[][] array 比 ArrayList<ArrayList<Object>> 更直觀

業務開發直接用容器；底層開發（如網路框架）追求極致效能時用陣列。

小結#