什麼是數組？

今天要介紹的主角就是-數組，數組也是數據呈線性排列的一種數據結構。與前一節中的

數組

如上就是數組的概念圖，Blue、Yellow、Red 作為數據存儲在數組中，其中 a 是數組的名字，後面 [] 中的數字表示該數據是數組中的第幾個數據，該數字也就是**數組下標，下標從 0 開始計數**，比如 Red 就是數組 a 的第 2 個數據。

那麼為什麼許多編程語言中的數組都從 0 開始編號的呢？先別急，可以先自己思考下，將會在文末進行講解。

從圖中可以看出來，數組的數據是按順序存儲在內存的連續空間內的。

由於數據是存儲在連續空間內的，所以每個數據的內存地址（在內存上的位置）都可以通過數組下標算出，我們也就可以藉此直接訪問目標數據，也就是隨機訪問。

比如現在我們想要訪問 Red，如果是鏈表的話，只能使用指針就只能從頭開始查找，但在數組中，只需要指定 a[2]，便能直接訪問 Red。

但是，如果想在任意位置上添加或者刪除數據，數組的操作就要比鏈表複雜多了。這裡我們嘗試將 Green 添加到第 2 個位置上。

首先，在數組的末尾確保需要增加的存儲空間。

為了給新數據 Green 騰出位置，要把已有數據一個個移開，首先把 Red 往後移。

然後把 Yellow 往後移。

最後在空出來的位置上寫入 Green。

添加數據的操作就完成了。

反過來，如果想要刪除 Green 呢？

首先，刪掉目標數據 Green。

然後把後面的數據一個個往空位移，先把 Yellow 往前移。

接下來移動 Red。

最後再刪掉多餘的空間，這樣一來 Green 便被刪掉了。

補充

這裡講解一下對數組操作所花費的運行時間，假設數組中有 n 個數據，由於訪問數據時使用的是隨機訪問（通過下標可計算出內存地址），所以需要的運行時間僅為恆定的 O（1）。

通過數組下標計算出內存地址的尋址公式如下：

<code>a[i]_address = base_address + i * data_type_size/<code>

其中 baseaddress 為內存塊的首地址，datatype_size 表示數組中每個元素的大小。

但另一方面，想要向數組中添加新數據時，必須把目標位置後面的數據一個個移開。所以，如果在數組頭部添加數據，就需要 O（n） 的時間，刪除操作同理。

在鏈表和數組中，數據都是線性地排成一列。在鏈表中訪問數據較為複雜，添加和刪除數據較為簡單；而在數組中訪問數據比較簡單，添加和刪除數據卻比較複雜。

我們可以根據哪種操作較為頻繁來決定使用哪種數據結構。

最後，讓我們一起來思考下剛開始提到的問題：為什麼很多編程語言中數組都從 0 開始編號？

解惑

從數組存儲的內存模型上來看，“下標”最確切的定義應該是“偏移（offset）”。如果用 a 來表示數組的首地址，a[0] 就是偏移為 0 的位置，也就是首地址，a[k] 就表示偏移 k 個 type_size 的位置，所以計算 a[k] 的內存地址只需要用這個公式：

<code>a[k]_address = base_address + k * type_size/<code>

但是，如果數組從 1 開始計數，那我們計算數組元素 a[k] 的內存地址就會變為：

<code>a[k]_address = base_address + (k-1)*type_size/<code>

對比兩個公式，可以發現，從 1 開始編號，每次隨機訪問數組元素都多了一次減法運算，對於 CPU 來說，就是多了一次減法指令。

數組作為非常基礎的數據結構，通過下標隨機訪問數組元素又是其非常基礎的編程操作，效率的優化就要儘可能做到極致。所以為了減少一次減法操作，數組選擇了從 0 開始編號，而不是從 1 開始。

除此之外還有歷史原因，C 語言設計者用 0 開始計數數組下標，之後的 Java、JavaScript 等高級語言都效仿了 C 語言，或者說，為了在一定程度上減少 C 語言程序員學習 Java 的學習成本，因此繼續沿用了從 0 開始計數的習慣。實際上，很多語言中數組也並不是從 0 開始計數的，比如 Matlab。甚至還有一些語言支持負數下標，比如 Python。

總結

這篇文章主要介紹了數據結構中常用的數組，數組用一塊連續的內存空間，來存儲相同類型的一組數據，最大的特點就是支持隨機訪問，但插入、刪除操作也因此變得比較低效，平均情況時間複雜度為 O(n)。有一種高效的查找算法是二分查找法，就是利用了數組隨機訪問的特性。

總得來說，數組適用於多操作多、寫操作少的場景，和我們上一篇文章中的鏈表正好相反。

參考

《我的第一本算法書》

數據結構與算法之美

閱讀更多 武培軒 的文章

關鍵字: 數據結構 算法 文章