1 概述

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

線性表（Linear List）：顧名思義，線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個(gè)線性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向。其實(shí)除了數(shù)組，鏈表、隊(duì)列、棧等也是線性表結(jié)構(gòu)。

image

連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)：正是因?yàn)檫@兩個(gè)限制，它才有了一個(gè)堪稱“殺手锏”的特性：“隨機(jī)訪問”。

說到數(shù)據(jù)的訪問，那你知道數(shù)組是如何實(shí)現(xiàn)根據(jù)下標(biāo)隨機(jī)訪問數(shù)組元素的嗎。

我們拿一個(gè)長度為 10 的 int 類型的數(shù)組 int[] a = new int[10] 來舉例。在我畫的這個(gè)圖中，計(jì)算機(jī)給數(shù)組 a[10]，分配了一塊連續(xù)內(nèi)存空間 1000～1039，其中，內(nèi)存塊的首地址為 base_address = 1000

image

我們知道，計(jì)算機(jī)會(huì)給每個(gè)內(nèi)存單元分配一個(gè)地址，計(jì)算機(jī)通過地址來訪問內(nèi)存中的數(shù)據(jù)。當(dāng)計(jì)算機(jī)需要隨機(jī)訪問數(shù)組中的某個(gè)元素時(shí)，它會(huì)首先通過下面的尋址公式，計(jì)算出該元素存儲的內(nèi)存地址：

/** 計(jì)算k元素在內(nèi)存中的偏移 **/// base_address 表示數(shù)組首個(gè)元素在內(nèi)存中偏移// type_size 表示數(shù)組元素中每個(gè)元素的大小a[k]_address=base_address+k*type_size。

但有利就有弊，這兩個(gè)限制也讓數(shù)組的很多操作變得非常低效，比如要想在數(shù)組中刪除、插入一個(gè)數(shù)據(jù)，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作。

2 基本操作

數(shù)組為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，會(huì)導(dǎo)致插入、刪除這兩個(gè)操作比較低效。

插入操作

假設(shè)數(shù)組的長度為 n，現(xiàn)在，如果我們需要將一個(gè)數(shù)據(jù)插入到數(shù)組中的第 k 個(gè)位置。為了把第 k 個(gè)位置騰出來，給新來的數(shù)據(jù)，我們需要將第 k～n 這部分的元素都順序地往后挪一位。

如果在數(shù)組的末尾插入元素，那就不需要移動(dòng)數(shù)據(jù)了，這時(shí)的時(shí)間復(fù)雜度為 O(1)。但如果在數(shù)組的開頭插入元素，那所有的數(shù)據(jù)都需要依次往后移動(dòng)一位，所以最壞時(shí)間復(fù)雜度是 O(n)。 因?yàn)槲覀冊诿總€(gè)位置插入元素的概率是一樣的，所以平均情況時(shí)間復(fù)雜度為 (1+2+…n)/n=O(n)。

插入優(yōu)化

如果數(shù)組中的數(shù)據(jù)是有序的，我們在某個(gè)位置插入一個(gè)新的元素時(shí)，就必須按照剛才的方法搬移 k之后的數(shù)據(jù)。但是，如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當(dāng)作一個(gè)存儲數(shù)據(jù)的集合。在這種情況下，如果要將某個(gè)數(shù)組插入到第 k 個(gè)位置，為了避免大規(guī)模的數(shù)據(jù)搬移，我們還有一個(gè)簡單的辦法就是，直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個(gè)位置。

為了更好地理解，我們舉一個(gè)例子。假設(shè)數(shù)組 a[10] 中存儲了如下 5 個(gè)元素：a，b，c，d，e。

我們現(xiàn)在需要將元素 x 插入到第 3 個(gè)位置。我們只需要將 c 放入到 a[5]，將 a[2] 賦值為 x 即可。最后，數(shù)組中的元素如下： a，b，x，d，e，c。

image

刪除操作

跟插入數(shù)據(jù)類似，如果我們要?jiǎng)h除第 k 個(gè)位置的數(shù)據(jù)，為了內(nèi)存的連續(xù)性，也需要搬移數(shù)據(jù)，不然中間就會(huì)出現(xiàn)空洞，內(nèi)存就不連續(xù)了。

和插入類似，如果刪除數(shù)組末尾的數(shù)據(jù)，則最好情況時(shí)間復(fù)雜度為 O(1)；如果刪除開頭的數(shù)據(jù)，則最壞情況時(shí)間復(fù)雜度為 O(n)；平均情況時(shí)間復(fù)雜度也為 O(n)。

插入刪除

實(shí)際上，在某些特殊場景下，我們并不一定非得追求數(shù)組中數(shù)據(jù)的連續(xù)性。如果我們將多次刪除操作集中在一起執(zhí)行，刪除的效率是不是會(huì)提高很多呢？

我們繼續(xù)來看例子。數(shù)組 a[10] 中存儲了 8 個(gè)元素：a，b，c，d，e，f，g，h?，F(xiàn)在，我們要依次刪除 a，b，c 三個(gè)元素。

image

為了避免 d，e，f，g，h 這幾個(gè)數(shù)據(jù)會(huì)被搬移三次，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒有更多空間存儲數(shù)據(jù)時(shí)，我們再觸發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。

如果你了解 JVM，你會(huì)發(fā)現(xiàn)，這不就是 JVM 標(biāo)記清除垃圾回收算法的核心思想嗎？沒錯(cuò)，數(shù)據(jù)結(jié)構(gòu)和算法的魅力就在于此，很多時(shí)候我們并不是要去死記硬背某個(gè)數(shù)據(jù)結(jié)構(gòu)或者算法，而是要學(xué)習(xí)它背后的思想和處理技巧，這些東西才是最有價(jià)值的。如果你細(xì)心留意，不管是在軟件開發(fā)還是架構(gòu)設(shè)計(jì)中，總能找到某些算法和數(shù)據(jù)結(jié)構(gòu)的影子。

擴(kuò)容

數(shù)組本身在定義的時(shí)候需要預(yù)先指定大小，因?yàn)樾枰峙溥B續(xù)的內(nèi)存空間。如果我們申請了大小為 10 的數(shù)組，當(dāng)?shù)?11 個(gè)數(shù)據(jù)需要存儲到數(shù)組中時(shí)，我們就需要重新分配一塊更大的空間，將原來的數(shù)據(jù)復(fù)制過去，然后再將新的數(shù)據(jù)插入。

容器 VS 數(shù)組

針對數(shù)組類型，很多語言都提供了容器類，比如 Java 中的 ArrayList

ArrayList 最大的優(yōu)勢就是可以將很多數(shù)組操作的細(xì)節(jié)封裝起來。比如前面提到的數(shù)組插入、刪除數(shù)據(jù)時(shí)需要搬移其他數(shù)據(jù)等。另外，它還有一個(gè)優(yōu)勢，就是支持動(dòng)態(tài)擴(kuò)容。

使用 ArrayList，我們就完全不需要關(guān)心底層的擴(kuò)容邏輯，ArrayList 已經(jīng)幫我們實(shí)現(xiàn)好了。每次存儲空間不夠的時(shí)候，它都會(huì)將空間自動(dòng)擴(kuò)容為 1.5 倍大小。

不過，這里需要注意一點(diǎn)，因?yàn)閿U(kuò)容操作涉及內(nèi)存申請和數(shù)據(jù)搬移，是比較耗時(shí)的。所以，如果事先能確定需要存儲的數(shù)據(jù)大小，最好在創(chuàng)建 ArrayList 的時(shí)候事先指定數(shù)據(jù)大小。

作者：貪睡的企鵝

鏈接：http://www.itdecent.cn/p/fd90916d3fe8

來源：簡書

著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。