陣列的定義#

陣列（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 標記清除垃圾回收演算法的核心思想。

陣列越界問題#

// 註：Kotlin 的陣列會自動做邊界檢查，越界會拋 ArrayIndexOutOfBoundsException，
// 不會像 C 那樣覆寫到相鄰變數的記憶體。以下用 C 的等價語意示意越界寫入。
val arr = IntArray(3)
for (i in 0..3) {       // 錯誤：應該是 0 until 3
    arr[i] = 0          // i == 3 時越界，Kotlin 會直接拋 ArrayIndexOutOfBoundsException
    println("hello world")
}

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

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

陣列 vs 容器（ArrayList）#

ArrayList 優勢#

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

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

// 推薦做法：已知大小時，預先指定容量，避免反覆擴容搬移
val users = ArrayList<User>(10000)   // 一次配置足夠容量
for (i in 0 until 10000) {
    users.add(...)
}

何時選擇陣列#

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

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

稀疏矩陣與三元組表示法#

當一個 M×N 的二維陣列絕大多數元素都是 0（稱為稀疏），用完整的二維陣列來儲存就極度浪費——你花了大量空間去存「沒有內容」這件事。

更務實的做法是**三元組（triplet）**列表：只記錄那些非零元素，每個非零元素存成 (行號, 列號, 值)。

// 只儲存非零元素：每筆是 (row, col, value)
val triplets = listOf(
    Triple(0, 2, 5),    // a[0][2] = 5
    Triple(3, 0, 8),    // a[3][0] = 8
    Triple(7, 6, -2),   // a[7][6] = -2
)

稀疏的程度往往超乎想像。語言中 20 萬個詞的同現矩陣有 400 億個元素（用完整陣列得佔數十 GB），但非零比例不到 1%；網頁之間的連結矩陣更稀疏，非零比例可低到億分之一。三元組能把空間壓縮數十倍到上億倍——這正是大規模圖計算（例如網頁排名）能在現實硬體上跑起來的前提。

編碼效率：用對的型別省空間#

同一份資料，選對表示法就能省下數倍空間。

舉例：要儲存一個人的年齡。如果用三個字元的字串 "030" 來存，需要 3 bytes；但年齡的範圍其實一個 8-bit 無號整數（0 ～ 255）就綽綽有餘，只要 1 byte——直接省下 2/3 的空間。

「選擇資料的表示方式」本身就是一種優化。把資料壓進更精簡的型別，不只省記憶體，也讓更多資料能塞進 CPU 快取、提升存取效率。這種思維在 位元運算 章節會被推到極致——用單一整數的每個位元去編碼一組布林狀態。

字串串接的隱藏陷阱#

用 + 反覆串接字串，是字串題最常見的效能地雷。

假設要把 n 個長度為 x 的字串接起來。每次 result = result + s 都會複製整個已累積的字串到新的記憶體：第 1 次複製 x 個字元、第 2 次 2x、第 3 次 3x……總成本是 x + 2x + ... + nx，即 O(x·n²)。

// ❌ 反覆 + 串接：O(x·n²)，每次都複製整個累積字串
var result = ""
for (s in parts) {
    result = result + s
}

// ✅ 用 StringBuilder 累積，最後一次 toString()：O(x·n)
val sb = StringBuilder()
for (s in parts) {
    sb.append(s)
}
result = sb.toString()

正解的關鍵是用一個可動態擴容的緩衝（的 StringBuilder，append 均攤 O(1)），最後才一次性 toString() 轉成字串，整體降到 O(x·n)。其他語言也有對應工具（如 Java 的 StringBuilder、Python 的 "".join()、C++ 的 std::string::append），原理相同。在迴圈裡用 + 拼字串，是面試與實務都容易被抓出來的反模式。

小結#