數(shù)組在任何一種編程語言中，都是一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。大家提到數(shù)組，都不會感到陌生，甚至會拍拍胸脯自信地說：這很簡單啊。

大家有沒有想過：數(shù)組為什么從 0 開始編號呢，為什么不從 1 開始呢？希望你帶著這個疑問去看接下去的文章。

文中會涉及到時間復雜度的分析，不懂的朋友可以先看看這篇。
復雜度分析

什么是數(shù)組？

數(shù)組(Array)是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同數(shù)據(jù)類型的數(shù)據(jù)。

這句話里有幾個關(guān)鍵詞，下面我就來給你解讀一下。

1. 線性表（Linear List)。顧名思義，線性表就是數(shù)據(jù)排成一條線一樣的結(jié)構(gòu)。鏈表、隊列、棧等數(shù)據(jù)結(jié)構(gòu)也是線性表結(jié)構(gòu)，我會在后文中一一講解，敬請關(guān)注哦。而堆、樹、圖等則是非線性的，即數(shù)據(jù)間不是簡單的前后關(guān)系。

2. 連續(xù)的內(nèi)存空間，相同的數(shù)據(jù)類型。正是由于數(shù)組的這個殺手锏特性，數(shù)組可以實現(xiàn)隨機訪問，但是任何一種數(shù)據(jù)結(jié)構(gòu)都是有其適用場合的，有利有弊的。數(shù)據(jù)的插入和刪除操作，為了保證連續(xù)性，需要做大量的工作。

而數(shù)組的隨機訪問由尋址方式實現(xiàn)：

a[i]_address = base_address + i * data_type_size

data_type_size 為數(shù)組中每個元素的大小，如果數(shù)組中存儲 int 類型數(shù)據(jù)， data_type_size 為 4 個字節(jié)。

舉個例子：現(xiàn)在我們創(chuàng)建一個長度為 5 的 int 類型的數(shù)組，int[] a = new int[5]; 計算機會在內(nèi)存中給數(shù)組 a[5] 分配一塊連續(xù)的內(nèi)存，我們設(shè)內(nèi)存塊的首地址為 base_address 為 1000，即

當計算機需要訪問元素 a[1] 時，它會根據(jù)上面的尋址公式，即：

a[i]_address = base_address + i * data_type_size

來計算出 a[1] 的內(nèi)存地址，從而實現(xiàn)隨機訪問，根據(jù)下標訪問時間復雜度為 O(1)。

另外在面試中面試官經(jīng)常會問數(shù)組和鏈表的區(qū)別，我們可以這樣回答：
鏈表適合插入、刪除，時間復雜度為 O(1)；數(shù)組適合查找，但是查找的時間復雜度并不為 O(1)，即使是排好序的數(shù)組，你用二分查找，時間復雜度也是 O(logn)。

數(shù)組支持隨機訪問，根據(jù)下標隨機訪問的時間復雜度為 O(1)。

數(shù)組的插入和刪除操作

我們先來看插入操作。

如果我們在數(shù)組的末尾插入數(shù)據(jù)，我們不需要移動數(shù)據(jù)，時間復雜度為 O(1)。我們在數(shù)組的開頭插入數(shù)據(jù)，需要移動 n 個數(shù)據(jù)，時間復雜度為 O(n)。假設(shè)我們在數(shù)組的任何位置插入數(shù)據(jù)的概率是相同的，則平均時間復雜度為 （1+2+3+···+n) / n = O(n)。

我們再來看刪除操作，和插入類似，刪除數(shù)組最后一個數(shù)據(jù)，時間復雜度為 O(1)。刪除開頭第一個數(shù)據(jù)，需要移動 n 個數(shù)據(jù)，時間復雜度為 O(n)。平均時間復雜度為 （1+2+3+···+n) / n = O(n)。

我們看到數(shù)組的插入和刪除操作都是比較低效的，而這都是數(shù)組的連續(xù)性帶來的。實際上，在某些特殊場景里，我們不一定會去追求數(shù)組中數(shù)據(jù)的連續(xù)性，如果我們可以將多次的刪除集中在一起執(zhí)行呢？如果這樣做的話，執(zhí)行效率是不是高了很多呢？

我們繼續(xù)延用上面的例子給你解釋：
假設(shè)數(shù)組 a[5] 存儲了 5 個元素：1， 2， 3， 4， 5?，F(xiàn)在，我們要依次刪除 1， 2， 3 三個元素。我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)，每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是刪除記錄數(shù)據(jù)。當數(shù)組沒有更多空間存儲數(shù)據(jù)時，我們觸發(fā)一次真正的刪除操作，這樣執(zhí)行效率大大增加。

假如你了解 JVM 的垃圾回收算法，你會發(fā)現(xiàn)這就是它的核心思想。
數(shù)據(jù)結(jié)構(gòu)與算法的最大魅力莫過于此，我們可以在很多地方發(fā)現(xiàn)他的影子，是程序的靈魂，也會有很多我們意想不到的「騷操作」。

容器能否代替數(shù)組

我們知道很多語言都提供了容器類，由于筆者比較熟悉 Java，這里我拿 Java 舉例，java 中的 ArrayList 作為 Java 工程師幾乎天天都在使用。我們知道 ArrayList 封裝了很多數(shù)組操作的細節(jié)，改用方法代替，還有就是支持動態(tài)擴容，我們完全不用擔心底層邏輯，當我們的空間不夠用時，ArrayList 會自動幫我們將空間擴容成 1.5 倍。

但是 ArrayList 是無法存儲基本類型的，如 int、long，需要封裝成 Integer、Long 類，另外對于數(shù)據(jù)大小我們事先已知，數(shù)據(jù)操作較為簡單，我們可以優(yōu)先考慮數(shù)組，畢竟我們不需要用到 ArrayList 提供的大多數(shù)方法。

最后，我來回答大家這個問題：數(shù)組為什么從 0 開始編號呢，為什么不從 1 開始呢？

答曰：歷史原因，因為 C 語言的設(shè)計者設(shè)計數(shù)組時是從 0 開始的，后來 Java 等高級語言都效仿 C 語言，再說，也讓 C 語言學習者轉(zhuǎn)入其他高級語言的學習減少了成本。怪不得，學校老師總是要求大家好好學 C 語言呢？

今天數(shù)組的學習就到這里了，我留個小問題，請你思考一下，二維數(shù)組的尋址是怎樣的呢？

歡迎留言與我分享！

System.out.println("點個喜歡！歡迎關(guān)注我！");