陣列 (Array)，又稱數組，為一資料結構 (Data Structure)，
是用來儲存一群『相同資料型態 [註1] 的元素 (element)』之串列。
通常 佔用 連續的 (consecutive) 記憶體位置 (memory location)。
 
每個元素，會有一類似編號的東西，
與之循序對映 (sequential mapping)，稱為 索引 (index)。
 

 
[註1]: 相同資料型態，又稱為 同質的 homogeneous [͵homəˋdʒinɪəs]。
 

---

 

隨機存取 (Random Access)

不同於 循序存取 (sequential access) 的 鏈結串列 (Linked List)：

『 (單向) 鏈結串列 』其元素通常散落於不連續記憶體位置，
且 A 元素 只認識 B 元素，B 元素 只認識 C 元素…，
要找到 Z 元素便只能一一尋訪 (A->B->C…>Z)，
時間複雜度: O(n) 。

 
而 陣列 (Array) 是置於 連續的 記憶體位置，
藉由其 索引們 (indices) 的計算，可得出任一元素的所在位址 (address)，
以達成 隨機存取 (Random Access)，使其 存取元素的時間複雜度為 O(1)！！
(當然，也支援 循序存取)
 
例:
一個儲存『顏色』的陣列，將其命名為 a:

 
 
其儲存於『連續的記憶體位置』中 (假設每個 Color 大小為 4 bytes)：
 

 
 
藉由計算『索引 (Index)』來存取元素，而不需一個一個地尋訪。
想取得 『Red』，只要透過索引值 『1』即可:

 
 

存取原理

已知 a[0] 位址為 0x7FAA0，
則 a[1] 為 0x7FAA0 + 4 = 0x7FAA4 (假設每個 Color 大小為 4 bytes)，
透過該位址，即可取得該元素。
 
由此可知，
計算陣列的記憶體位址 (address) 尤其重要，將於後幾節提及。
我們常說的 RAM (隨機存取記憶體 Random Access Memory) 即是類似的概念。
 
 
許多人認為 索引 很不直覺，
為何第 一 個元素的 索引 ，
為 『0』，而不是 『1』?
 

索引 (Index)，可想成是陣列的 偏移量/差量 (offset)，
『第一個元素』自然沒有偏移囉!
這也是為何，索引 通常皆為無號整數 (非負整數)。

 

---

 

插入 & 刪除 (Insertion & Deletion)

然而，相較於其他資結 (e.g., 鏈結串列)，
陣列 若想插入、刪除一個元素，較不方便。
因為需挪移其他元素，插入/刪除 時間複雜度為 O(n)。
 
例如，欲插入 (Insert) 一元素 『綠色』至 a[1]。
 
得把『紅色』、『黃色』往後移動，還得考慮是否已超過陣列大小，
否則，可能會導致 陣列索引值超出範圍例外 (Array Index Out Of Bounds Exception)。
 
反之，若想刪除某元素，得把其他元素往前挪動:

 

---

 

一維陣列 (One-dimensional Array)

陣列，可以是一維、二維…多維 (維度 Dimension) 陣列，
維度，是指定某點 (物) 所需的最小座標數，
也就是我們常說的『點』、『線』、『面』啦~
分別對應 零維、一維、二維。
 
上述範例中，如『顏色』陣列般的線性資料，即是 一維陣列 囉！
 
 

位址計算

前面提及了，計算陣列記憶體位址的重要性，
一維陣列的計算公式如下:

一陣列 A( L : μ ) ，有 n 個元素，
其初始索引為 L [註2]，
陣列的基底位址為 L₀，每個元素大小為 d，
則 A[i] 之位址 = L₀ + ( i – L ) * d，
其中，n = μ – L + 1 。

 

 

---

 
例:

有一 int 陣列 A，有 200 個元素，
其初始索引為 10 ，
基底位址為 9007，每個元素大小為 4 bytes，
求 A[130] 之位址?

 
Ans:
A[130] 之位址 = 9007 + (130 – 10) * 4 = 9487 #
 
 
[註2]:
考題不一定會給 初始索引，
且有些預設為 『0』，有些為『1』，需多加注意!
 

---

 

二維陣列 (Two-dimensional Array)

二維陣列 ，即是藉由行與列 [註3] 的方式，
將資料循序存取到連續記憶體中。
 
由於多了一個維度，
其需用兩個索引值，來對映一個元素，
這也使得相較於 一維，二維陣列 能夠處理更多『面向』的問題。
 
ex:
某一維陣列 a，存有班上三位同學的成績:

 
 
若有 3 個班級呢?
 
 
二維陣列就派上用場啦！
欲存取 乙班、1 號 同學的成績，即可透過 a["乙班"] [1] 的方式!

 
 
[註3]:
因翻譯問題、書寫習慣…，
台灣的 『行』與『列』 容易產生混淆，
『直行橫列』還是『橫行直列』各說各話。
 
為避免誤會:
Row ，以下稱為 『列』，方向為 『一』;
Column ， 以下稱為『行』，方向為『 | 』，
索引的用法，如同矩陣 (matrix) 的概念，
第 i 列 、第 j 行的元素，表示為 a[i] [j]。
 
 
 
例:
一個儲存『動物』的二維陣列，將其命名為 a:
 
想存取 小雞雞，可以使用 a[1] [1]，
想存取 小豬豬，可以使用 a[2] [0]。
 

 
 

位址計算

計算二維 (多維) 陣列位址，普遍的兩種方式:

1. 以列為主 (Row-major)
2. 以行為主 (Column-major)

其實，皆只是將二維陣列 轉換為 一維陣列的方式，
C、C++、C#… 等程式語言主要 (沒有一定) 採用 Row-major 的對應方式 ，
Fortran、OpenGL… 等，多採用 Column-major。
 
 

Row-major

以 Row-major 為例，顧名思義，
透過一列一列的方式，將二維陣列循序存入記憶體中，
Column-major 反之，不再累述。
 

一陣列 A( L₁ : μ₁ ， L₂ : μ₂ ) ，有 m 列、n行，
陣列的基底位址為 L₀，每個元素大小為 d，
則 A[i] [j]之位址 = L₀ + ( i – L₁ ) * (n * d) + ( j – L₂ ) * d ，
其中，m = μ₁ – L₁ + 1 ，n = μ₂ – L₂ + 1 。

 
( i – L₁ ) 用來算出所有的列數 ( A[i] [j] 此列 不算)，
( n * d ) = n 行 * d (bytes) ，也就是此二維陣列 中，一列的 bytes 大小，
( j – L₂ ) 算出 A[i] [j] 此元素 以左的行數。
 

 
 
但是，為何要轉為一維陣列呢?
 
如上述圖示:

我們可將 記憶體 視為一個很大的 一維 位元組 (bytes) 陣列！
每一位元組，皆有其 位址 (address)，稱為 byte addressing。

 
當二維陣列放入記憶體，
便需要計算其位址，以供存取陣列元素啦 😆。
 

---

 

Java 沒有多維陣列！

至於 Java 提供的二維陣列，是使用 Row-major 還是 Column-major 呢?

兩者皆非

 
∵ Java 並沒有二維 (多維) 陣列！
 
你可能會認為:「蛤 下方不就是標準的 Java 二維陣列嗎 😑 ?」
 
Java 宣告二維陣列:

int[][] a = {
    {3, 3, 0},
    {9, 5, 2, 7}
};

 
對不起 我標題殺人 😂，一般來說，這的確稱二維陣列。
 
然而，嚴格來看，Java 只有一維陣列 無誤！
 
事實上不只 Java，許多語言的 二維 (多維) 陣列，
並非『連續』的記憶體位置，而是『陣列中的陣列』之概念。
 
也就是:

由多個 一維陣列 所組成

 
例:
下圖範例中，一 Java 二維陣列，命名為 a，
a[0] 存有指向 一維陣列 {3, 3, 0} 的參照 (reference)，
a[1] 存有指向 一維陣列 {9, 5, 2, 7} 的參照。

 
有趣的是，Java 這樣的宣告方式，允許子陣列的長度不相等:
一維陣列 {3, 3, 0} 長度為 3 ;
一維陣列 {9, 5, 2, 7} 長度為 4。
 
透過索引:
a[0][0] 可取得 3， a[0][1] 可取得 3， a[0][2] 可取得 0，
a[0][3] 將拋出 陣列索引值超出範圍例外 (Array Index Out Of Bounds Exception)。
 
 
這在 C 語言中 (以下的宣告方式)，並不被允許，
其嚴格的規範 子陣列的長度 (當然，也能自行實踐 陣列in陣列)。
 
ex:
C 宣告二維陣列:

int a[2][4] = {
    {3, 3, 0},
    {9, 5, 2, 7}
};

 
由於子陣列的長度會固定，
透過索引 a[0][3] 將會取得 預設值 0，而非拋出例外。
 
 
許多人認為:『連續的記憶體』只是 陣列 最常見的作法，
(因此，本文最上方介紹『連續』時，用了 通常 二字)
並不能說 『陣列的陣列』就不是多維陣列。
 
其實，平常溝通聽得懂就 ok 啦！
若要嚴格討論實作方式，才加以區別 😃。
 

---

 

總結

陣列 可說是最簡單、也最重要的資料結構，
它可用來表示方程式、矩陣…，
也時常做為其他資結的構成基礎 (e.g., 堆疊、佇列、完整二元樹)。
 
礙於篇幅，本篇不進一步探討，
未來再補充 陣列的使用與實作 😀。
 
最後，附上 bigocheatsheet 的複雜度分析表！