陣列：你的第一個資料結構

一排格子，並肩排開

[[dsa-array|陣列]]把它的各項存放在連續記憶體裡——一整塊連綿的記憶體，每一項佔一個大小相等的格子，格子之間沒有空隙。想像沿著牆螺接在一起的一排一模一樣的信箱，從 0 開始編號。因為每個箱子大小相同、又緊挨著彼此，第 *i* 個箱子的地址就是一道簡單的算術：*起始位址 + i ×（一個箱子的大小）*。電腦不去搜尋第 5 個箱子；它直接*算出*它在哪兒，一步走到。

index:     0     1     2     3     4
         +-----+-----+-----+-----+-----+
array:   |  17 |  42 |   8 |  99 |   5 |
         +-----+-----+-----+-----+-----+
          base  +1    +2    +3    +4   slots  (each the same size)

  v[3]?  address = base + 3 * slot_size  ->  go straight there  (O(1))

索引從 0 開始。因為格子大小相等又相鄰，任意索引的位址都是一次計算——所以讀取 v[3] 是 O(1)，無論陣列多大。

這就是陣列的超能力：O(1) 的隨機存取。無論陣列裝 10 項還是一千萬項，取出某個已知索引處的項，所花的功都是同樣微小而固定的——它的[[time-complexity|時間複雜度]]不隨大小增長。正是這一條性質，讓陣列坐落在你將學到的幾乎所有其他資料結構的底層。

代價：往中間插入是 O(n)

正是那讓讀取瞬時的東西——沒有空隙——讓插入變得痛苦。假設你想把一個新值塞進中間。那裡沒有空格；下一項正緊緊頂著它。所以為了騰地方，從那一點到末尾的每一項都得往後挪一格。最壞情況下（插在最前面）你要挪動*全部 n* 項。從中間刪除則是鏡像：空洞之後的一切都往前挪，把縫隙合上。兩者都是 O(n)——工作量隨陣列大小增長。

insert 7 at index 2:

before:  [ 17 | 42 |  8 | 99 |  5 |    ]
                       ^ everyone from here rightward must move
step:    [ 17 | 42 |    |  8 | 99 |  5 ]   shift 8,99,5 right
after:   [ 17 | 42 |  7 |  8 | 99 |  5 ]   now drop 7 into the gap

  -> up to n items shifted  ->  O(n)

要在中間插入，後面的每一項都要順移一格。插在最前面要挪動全部 n 項——這就是中間/開頭的插入與刪除是 O(n) 的原因。

固定陣列 vs. 可增長的 std::vector

一個普通的 C++ 陣列有固定的大小，你必須事先定好：`int a[5];` 永遠恰好是五格。要是來了第六個值，就沒地方放了。當你事先知道數量時，這沒問題，可真實的程式常常並不知道。解決辦法是[[dynamic-array|動態陣列]]：一個填滿時能*增長*的陣列。在 C++ 裡就是 `std::vector`，它是你會不斷伸手去拿的主力。

#include <vector>

int a[5] = {17, 42, 8, 99, 5};   // fixed: exactly 5 slots, no growing
int x = a[3];                     // O(1) read -> 99

std::vector<int> v = {17, 42, 8}; // dynamic: starts at 3, can grow
v.push_back(99);                  // append at the end (usually cheap)
v.push_back(5);                   // now {17, 42, 8, 99, 5}
int y = v[3];                     // O(1) read, same as the plain array

固定陣列不能增長；std::vector 能。兩者都提供 O(1) 的索引存取——vector 保住了陣列的超能力，同時讓你隨意 push_back。

它是怎麼增長的？當一個 vector 填滿時，它會悄悄抓一塊更大的記憶體（通常是原來的兩倍），把各項複製過去。這次複製聽上去昂貴——偶爾也確實如此——但因為大小每次都*翻倍*，那些昂貴的時刻既稀少又被攤得很薄。在許許多多次 `push_back` 上平均下來，追加表現得彷彿就是 O(1)。你現在還不需要完整的帳目；只需相信 `std::vector` 給了你一個可增長的陣列，又沒放棄瞬時的 O(1) 讀取。