陣列 (Array) 簡介

陣列 (Array)，又稱數組，為一資料結構 (Data Structure)，
是用來儲存一群『相同資料型態 [註1] 的元素 (element)』之串列。
通常佔用連續的 (consecutive) 記憶體位置 (memory location)。

每個元素，會有一類似編號的東西，
與之循序對映 (sequential mapping)，稱為索引 (index)。

Windows of the plattenbau building — Photo by Roman Drits

[註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 是指可在近似固定時間讀寫任一記憶體位址；陣列的 O(1) 索引則是利用連續配置與位址計算。兩者相關，但不是同一件事。

許多人認為索引很不直覺，
為何第一個元素的索引，
為『0』，而不是『1』?

索引 (Index)，可想成是陣列的偏移量/差量 (offset)，
『第一個元素』自然沒有偏移囉!
在數學模型中，索引常以非負整數表示；但程式語言的索引型別不一定是 unsigned，有些語言甚至支援負索引代表從尾端計算。實際可用範圍應以該語言與容器 API 為準。

插入 & 刪除 (Insertion & Deletion)
然而，相較於其他資結（例如鏈結串列），陣列若在中間插入或刪除元素，通常必須搬移後續元素，最壞情況為 O(n)。但尾端操作、預留容量的 dynamic array，或特定語言的容器可能有不同成本，不能把所有插入／刪除都概括成 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)
二維陣列以兩個索引值定位元素。若實作採用緊密的矩形配置，元素會依 row-major 或 column-major 線性排入連續記憶體；但陣列中的陣列、jagged array 等實作不必連續。它適合表達表格、棋盤或班級成績這類雙維度資料。

ex:
某一維陣列 a，存有班上三位同學的成績:

若有 3 個班級呢?

二維陣列就派上用場啦！
若先將班級編成索引，例如乙班為 1，便可透過 a[1][1] 取得乙班、1 號同學的成績；字串索引屬於 map／dictionary 的常見用法，不是一般陣列的前提。

[註3]:
因翻譯問題、書寫習慣…，
台灣的『行』與『列』容易產生混淆，
『直行橫列』還是『橫行直列』各說各話。

為避免誤會:
Row ，以下稱為『列』，方向為『一』;
Column ，以下稱為『行』，方向為『 | 』，
索引的用法，如同矩陣 (matrix) 的概念，
第 i 列、第 j 行的元素，表示為 a[i] [j]。

例:
一個儲存『動物』的二維陣列，將其命名為 a:

想存取小雞雞，可以使用 a[1] [1]，
想存取小豬豬，可以使用 a[2] [0]。

位址計算
計算二維 (多維) 陣列位址，普遍的兩種方式:
以列為主 (Row-major)
以行為主 (Column-major)
其實，皆只是將二維陣列轉換為一維陣列的方式，
C／C++ 的連續多維陣列採 row-major；Fortran 的陣列採 column-major。OpenGL 常以 column-major 的矩陣慣例解讀資料，但那是 API／數學慣例，不能直接當作所有語言的記憶體配置規則。

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 的複雜度分析表！

分享此文：
X
Facebook
More