(有關於 Latex 公式顯示問題，因為 iThome 的編輯器沒有支援所以沒辦法，建議可以貼到 obsidian 或是 notion 的工具來看會比較清楚)

Array 是一種 Static Data Structure 或稱為 Dense List，它是一種將有序串列的資料結構使用 Contiguous Allocation 來儲存，意味著儲存的元素必須是相同類型，且靜態資料結構的記憶體配置是在編譯時，就必須配置給相關的變數，因此在創建時必須先宣告空間大小。

常見的 Array 類型 (N-Dimensional Array)

Array 應該是有無限多維，基本上到了 3 維除了圖片外就很少看到，4 維含以上我沒見過，也有可能是我才疏學淺，所以這裡就代表性的介紹 1 ~ 3 維的 Array

One-Dimensional Array

One-Dimensional Array 是一個在記憶體中連續配置 (contiguously allocated) 的元素序列，所有元素型態一致、大小相同，可透過固定大小的偏移量 element_size 在 O(1) 時間計算任意元素的位址。簡單來說，只要給定起始的位置跟每個空間的大小，就能夠直接算出任意元素的位址，位址公式如下:

$$
\text{LOC}(A[i]) = \text{Base}(A) + (i - L) \times w
$$

其中:

• $\text{LOC}(A[i])$: 表示陣列中第 i 個元素的記憶體位址。
• $\text{Base}(A)$: 陣列的起始位址。
• $i$: 要找的索引位置。
• $L$: 陣列的下標起點 (lower bound)，在大多數語言 (Python, Java, C++)，$L = 0$。
• $(i - L)$: 表示從起點偏移了幾個元素。
• $w$: 每個元素的大小 (word size)，以位元組 (bytes) 為單位。

接下來直接帶入實例計算，假設 $\text{Base}(A) = 1000$、$L = 0$、陣列 ints[5]，型別是 int (4 bytes)，求 A[3] 的位址:

$$
\text{LOC}(A[3]) = 1000 + (3 - 0) \times 4 = 1012
$$

Two-Dimensional Array

Two-Dimensional Array 是一個在記憶體中連續配置的矩形資料表，所有元素型態一致、大小相同，使用二維索引尋址，底層實際儲存為一塊連續記憶體，索引轉換為位移運算後直接定位到值本身(注意: 真二維陣列是無法有鋸齒狀結構，一般如 Java 的 int[][] 等都不是真二維陣列)。

所以 Two-Dimensional Array 跟 One-Dimensional Array 一樣，也可以計算位址，但是必須先瞭解 Row-major 與 Column-major 的差異，假設要將一組資料 [1, 2, 3, 4] 存入 2x2 的陣列中，其差異如下:

• Row-major (代表語言 Python, Java, C++ ...): 記憶體順序會是 [1, 2, 3, 4]，也就是 [[1, 2], [3, 4]]
• Column-major (代表語言 MATLAB, R ...): 記憶體順序會是 [1, 3, 2, 4]，也就是 [[1, 3], [2, 4]]

依照主流的程式語言來說，Row-major 是最常見的，所以位址公式就會以 Row-major 為例，位址公式如下:

$$
\text{LOC}(A[i][j]) = \text{Base}(A) + \Big((i - L_r) \times n + (j - L_c)\Big) \times w
$$

其中:

• $n$: 就是「每一列的元素個數」(欄數)

方程式中的其他代號跟 One-Dimensional Array 大同小異就不多做說明，接下來直接帶入實例計算，假設 $\text{Base}(A) = 1000$、$L = 0$、陣列 ints[4][4]，型別是 int (4 bytes)，求 A[2][3] 的位址:

$$
\text{LOC}(A[i][j]) = 1000 + \Big((2 - 0) \times 4 + (3 - 0)\Big) \times 4 = 1044
$$

Three-Dimensional Array

不管是 Three-Dimensional Array 還是 N-Dimensional Array，其實都是 Two-Dimensional Array，所以它們的定義都是一樣的，直接來看位址公式如下:

$$
\text{LOC}(A[i][j][k]) = \text{Base}(A) + \Big( (i - L_x)\times(y \times z) + (j - L_y)\times z + (k - L_z) \Big) \times w
$$

接下來直接帶入實例計算，假設 $\text{Base}(A) = 1000$、$L = 0$、陣列 ints[4][4][4]，型別是 int (4 bytes)，求 A[2][3][0] 的位址:

$$
\text{LOC}(A[i][j][k]) = 1000 + \Big( (2 - 0)\times(4 \times 4) + (3 - 0)\times 4 + (0 - 0) \Big) \times 4 = 1176
$$

所以其實這些計算還蠻簡單的，一般來說，除非像我是學校要考試，沒辦法必須背，不然其實看看就好了，正常狀況也不可能叫你算這東西。

常見的 Array 操作

基本上，資料結構的操作可以分為以下 4 大類 (BigO 到後續的演算法分析會在介紹):

創建 Array

Array 常見的操作可以從前述的 4 大類進行延伸出，因為 Python 並不像 Java 或 C++ 有內建 Array，必須要使用 array 或是 numpy 這些函式庫來實現，以下就使用 Python 的 array 函式庫為例:

import array

arr = array.array('i', [1, 2, 3, 4, 5])
print(arr)  # array('i', [1, 2, 3, 4, 5])

添加元素

因為 Python 的 Array 的本質上就是定型別的可變長動態陣列，所以單就 Python 來說有提供 append() 直接添加的方法，但是這樣學資料結構是不健康的，先假設 Python 跟 Java 一樣是沒有提供這些方法。

還記得前面的定義，Array 的 size 是固定的，所以假設沒有空間下，要添加元素，必須用擴容的方式，就是先新增一個新的 Array 再把資料放進去，操作如下:

import array

# 假設要在 array 的末端添加 6 的元素 (array 每次擴容只擴剛好的空間)
arr = array.array('i', [1, 2, 3, 4, 5])
new_arr = array.array('i', [0] * (len(arr) + 1))

# 把 arr 的值搬到 new_arr
for i in range(len(arr)):
	new_arr[i] = arr[i]

new_arr[-1] = 6 # 把要新增的資料放到 array 末端 
print(new_arr)  # array('i', [1, 2, 3, 4, 5, 6])

雖然這個程式有點蠢，但是可以讓讀者體會一下， Array 速度很快，但是操作起來有點麻煩。

註: 聽說在業界真的要操作 Array，假設原始 array 的 size = 6，把資料放到位置 5 了，會一次擴容到 size = 12，這樣可以避免一次擴容太多導致佔用過多的記憶體，也可以避免一直要頻繁地做擴容。

訪問元素

Array 的訪問元素就簡單很多了，因為 Array 是在一個連續空間，所以可以直接用 index 來取回值，後續介紹更多的資料結構後，讀者就能發現有些資料結構是不能透過 index 直接取回值，其他的後續再談，Array 的操作如下:

import array

arr = array.array('i', [1, 2, 3, 4, 5])

print(arr[3])  # 4

修改元素

Array 的修改元素，就是直接把指定位置的值直接替換而已，操作如下:

import array

arr = array.array('i', [1, 2, 3, 4, 5])

arr[3] = 9

print(arr[3])  # 9
print(arr)  # array('i', [1, 2, 3, 9, 5])

刪除元素

Array 的刪除元素操作就相對麻煩很多，先回憶 Array 的特徵: 元素型態一致、大小相同，所以 Array 是固定的怎麼刪除? 看到這邊，其實讀者可能第一個想法，我在開一個新的 Array 把舊的 Array 資料搬過去，排除要刪除的元素就好，沒錯這是一個思路，但是一般不會這樣做。

假設 Array = [1, 2, 3, 4, 5]，要將值為 2 的元素刪除，Array 會變成 [1, 3, 4, 5, 5]，一般的操作方式就是把要刪除的元素之後的元素都往前一格，操作如下:

import array

arr = array.array('i', [1, 2, 3, 4, 5])

target = 2 # 要刪除值為 2 的元素

j = 0
for i in range(len(arr)):
    if (arr[i] != target):
        arr[j] = arr[i]
        j += 1

print(arr)  # array('i', [1, 3, 4, 5, 5])

到這邊可能會有疑惑說，那最後一個元素不是錯的嗎? 其實沒關係，要回傳的時候可以做 Slice 或是把它替換成 0，在整個回傳就好，這部分就要看當下要怎麼處理。

遍歷 Array

這個就很簡單，我們前面都看過了，就是用 for loop 走一輪而已，操作如下:

import array

arr = array.array('i', [1, 2, 3, 4, 5])

for i in range(len(arr)):
	print(arr[i], end=' ')

查找元素

查找跟訪問不太一樣，訪問是透過 index 把值取回來；而查找透過值把 index 取回來，最簡單的方式就是遍歷 Array，用 for loop 走一輪就知道，但是還有其他方法可以更快，所以這邊大家先知道最基礎的方式就好，等到後續的演算法部分應該會再說明這種 Search 有什麼寫法可以更快。

Array 的長度

import array

arr = array.array('i', [1, 2, 3, 4, 5])

print(len(arr))  # 5

Array 的排序

排序也是，在這邊先留個伏筆，等到後續的演算法部分應該會再說明這種 Sort 有什麼寫法可以處理。

LeetCode

因為專門再說明 LeetCode 解法的網站與影片真的太多，這邊就由讀者自行學習，以下題目是跟 Array 有相關:

• LeetCode 485. Max Consecutive Ones
• LeetCode 283. Move Zeroes
• LeetCode 27. Remove Element

結語

今天我們從 Array 的定義、記憶體配置 談起，延伸到一維、二維、三維陣列的位址計算，再到常見的操作 (訪問、查找、插入、刪除、遍歷)。雖然在日常開發中，我們幾乎不需要自己計算記憶體位址，但理解這些原理能幫助我們知道為什麼 Array 的訪問是 $O(1)$，而插入與刪除是 $O(n)$。

這些知識會是後續所有資料結構的基石，因為鏈表、堆疊、佇列乃至樹與圖，最後都會回歸到陣列或指標的實作。