陣列與線性結構
陣列
陣列是存放一組同型別元素最簡單的方式：一整塊連續記憶體把它們一個挨一個排好，就像一排編號為 0、1、2…… 的相同信箱。因為每個元素大小相同又緊鄰，電腦可以直接跳到第 i 個元素——它的位址就是這塊記憶體的起始位置加上 i 乘以單個元素的大小，既不用搜尋，也不用逐個走過前面的元素。
這一點正是陣列的看家本領：讀寫 array[i] 都是 O(1) 時間，無論陣列多大、i 落在哪裡。代價則出現在別處。陣列的大小通常在建立時就固定了，想擴充就得另開一塊新記憶體再把資料全部複製過去；在中間插入或刪除元素，則要把後面的所有元素整體搬移以維持連續，最壞情況是 O(n)。
幾乎所有其他結構都建立在陣列之上——字串、動態陣列、堆疊、佇列、雜湊表與堆積底層都用到陣列。當你需要按索引快速存取、又大致知道有多少元素時，樸素的陣列很難被超越。
int a[5] = {10, 20, 30, 40, 50};
// index: 0 1 2 3 4
// +----+----+----+----+----+
// | 10 | 20 | 30 | 40 | 50 |
// +----+----+----+----+----+
int x = a[3]; // O(1): jump straight to slot 3 -> 40
a[1] = 99; // O(1) write
// inserting before index 1 would shift 20,30,40,50 right: O(n)按索引存取是 O(1)；其佈局就是一整塊扁平記憶體。
大多數語言的陣列從 0 開始計數，所以長度為 n 的陣列索引是 0 到 n-1。越界讀取是經典又危險的錯誤。
又稱
另見