為什么說數(shù)據(jù)結(jié)構(gòu)很重要2

3.插入

往數(shù)組里插入一個(gè)新元素的速度，取決于你想把它插入到哪個(gè)位置上。

假設(shè)我們想要在購物清單的末尾插入"figs"。那么只需一步。因?yàn)橹罢f過了，計(jì)算機(jī)知道數(shù)組開頭的內(nèi)存地址，也知道數(shù)組包含多少個(gè)元素，所以可以算出要插入的內(nèi)存地址，然后一步跳到那里插入就行了。圖示如下。

但在數(shù)組開頭或中間插入，就另當(dāng)別論了。這種情況下，我們需要移動(dòng)其他元素以騰出空間，于是得花費(fèi)額外的步數(shù)。

例如往索引2 處插入"figs"，如下所示。

為了達(dá)到目的，我們必須先把"cucumbers"、"dates"和"elderberries"往右移，以便空出索引2。而這也不是一步就能移好，因?yàn)槲覀兪紫纫獙?elderberries"右移一格，以空出位置給"dates"，然后再將"dates"右移，以空出位置給"cucumbers"，下面來演示這個(gè)過程。

第1 步："elderberries"右移。

第2 步："date"右移。

第3 步："cucembers"右移。

第4 步：至此，可以在索引2 處插入"figs"了。

如上所示，整個(gè)過程有4 步，開始3 步都是在移動(dòng)數(shù)據(jù)，剩下1 步才是真正的插入數(shù)據(jù)。

最低效（花費(fèi)最多步數(shù)）的插入是插入在數(shù)組開頭。因?yàn)檫@時(shí)候需要把數(shù)組所有的元素都往右移。于是，一個(gè)含有N 個(gè)元素的數(shù)組，其插入數(shù)據(jù)的最壞情況會(huì)花費(fèi)N + 1 步。即插入在數(shù)組開頭，導(dǎo)致N 次移動(dòng)，加上一次插入。

最后要說的“刪除”，則相當(dāng)于插入的反向操作。

4.刪除

數(shù)組的刪除就是消掉其某個(gè)索引上的數(shù)據(jù)。

我們找回最開始的那個(gè)數(shù)組，刪除索引2 上的值，即"cucumbers"。

第1 步：刪除"cucumbers"。

雖然刪除"cucumbers"好像一步就搞定了，但這帶來了新的問題：數(shù)組中間空出了一個(gè)格子。因?yàn)閿?shù)組中間是不應(yīng)該有空格的，所以，我們得把"dates"和"elderberries"往左移。

第2 步：將"dates"左移。

第3 步：將"elderberries"左移。

結(jié)果，整個(gè)刪除操作花了3 步。其中第1 步是真正的刪除，剩下的2 步是移數(shù)據(jù)去填空格。

所以，刪除本身只需要1 步，但接下來需要額外的步驟將數(shù)據(jù)左移以填補(bǔ)刪除所帶來的空隙。

跟插入一樣，刪除的最壞情況就是刪掉數(shù)組的第一個(gè)元素。因?yàn)閿?shù)組不允許空元素，當(dāng)索引0 空出，那么剩下的所有元素都要往左移去填空。

對(duì)于含有5 個(gè)元素的數(shù)組，刪除第一個(gè)元素需要1 步，左移剩余的元素需要4 步。而對(duì)于500個(gè)元素的數(shù)組，刪除第一個(gè)元素需要1 步，左移剩余的元素需要499 步?？梢酝瞥觯瑢?duì)于含有N個(gè)元素的數(shù)組，刪除操作最多需要N 步。

既然學(xué)會(huì)了如何分析數(shù)據(jù)結(jié)構(gòu)的時(shí)間復(fù)雜度，那就可以開始探索各種數(shù)據(jù)結(jié)構(gòu)的性能差異了。了解這些非常重要，因?yàn)閿?shù)據(jù)結(jié)構(gòu)的性能差異會(huì)直接造成程序的性能差異。

下一個(gè)要介紹的數(shù)據(jù)結(jié)構(gòu)是集合，它跟數(shù)組似乎很像，甚至讓人以為就是同一種東西。然而，我們將會(huì)看到它跟數(shù)組在性能上是有區(qū)別的。

集合：一條規(guī)則決定性能

來看看另一種數(shù)據(jù)結(jié)構(gòu)：集合。它是一種不允許元素重復(fù)的數(shù)據(jù)結(jié)構(gòu)。

其實(shí)集合是有不同形式的，但現(xiàn)在我們只討論基于數(shù)組的那種。這種集合跟數(shù)組差不多，都是一個(gè)普通的元素列表，唯一的區(qū)別在于，集合不允許插入重復(fù)的值。

要是你想往集合["a", "b", "c"]再插入一個(gè)"b"，計(jì)算機(jī)是不會(huì)允許的，因?yàn)榧现幸呀?jīng)有"b"了。

集合就是用于確保數(shù)據(jù)不重復(fù)。

如果你要?jiǎng)?chuàng)建一個(gè)線上電話本，你應(yīng)該不會(huì)希望相同的號(hào)碼出現(xiàn)兩次吧。事實(shí)上，現(xiàn)在我的本地電話本就有這種狀況：我家的電話號(hào)碼不單指向我這里，還錯(cuò)誤地指向了一個(gè)叫Zirkind 的家庭（這是真的）。接聽那些要找Zirkind 的電話或留言真的挺煩的。

不過，估計(jì)Zirkind 一家也在納悶為什么總是接不到電話。而當(dāng)我想要打電話告訴Zirkind 號(hào)碼錯(cuò)了的時(shí)候，我妻子就會(huì)去接電話了，因?yàn)槲覔艿木褪俏壹姨?hào)碼（好吧，這是開玩笑）。如果這個(gè)電話本程序用集合來處理，那就不會(huì)搞出這種麻煩了。

總之，集合就是一個(gè)帶有“不允許重復(fù)”這種簡單限制的數(shù)組。而該限制也導(dǎo)致它在4 種基本操作中有1 種與數(shù)組性能不同。

下面就來分析讀取、查找、插入和刪除在基于數(shù)組的集合上表現(xiàn)如何。

集合的讀取跟數(shù)組的讀取完全一樣，計(jì)算機(jī)只要一步就能獲取指定索引上的值。如之前解釋的那樣，這是因?yàn)橛?jì)算機(jī)知道集合開頭的內(nèi)存地址，所以能夠一步跳到集合的任意索引。

集合的查找也跟數(shù)組的查找無異，需要N 步去檢查某個(gè)值在不在集合當(dāng)中。刪除也是，總共需要N 步去刪除和左移填空。

但插入就不同了。先看看在集合末尾的插入。對(duì)于數(shù)組來說，末尾插入是最高效的，它只需要1 步。

而對(duì)于集合，計(jì)算機(jī)得先確定要插入的值不存在于其中——因?yàn)檫@就是集合：不允許重復(fù)值。

于是每次插入都要先來一次查找。

假設(shè)我們的購物清單是一個(gè)集合——用集合還是不錯(cuò)的，畢竟你不會(huì)想買重復(fù)的東西。如果當(dāng)前集合是["apples", "bananas", "cucumbers", "dates", "elderberries"]，然后想插入"figs"，那么就需要做一次如下的查找。

第1 步：檢查索引0 有沒有"figs"。

沒有，不過說不定其他索引會(huì)有。為了在真正插入前確保它不存在于任何索引上，我們繼續(xù)。

第2 步：檢查索引1。

第3 步：檢查索引2。

第4 步：檢查索引3。

第5 步：檢查索引4。

直到檢查完整個(gè)集合，才能確定插入"figs"是安全的。于是，到最后一步。

第6 步：在集合末尾插入"figs"。

在集合的末尾插入也屬于最好的情況，不過對(duì)于一個(gè)含有5 個(gè)元素的集合，你仍然要花6 步。因?yàn)?，在最終插入的那一步之前，要把5 個(gè)元素都檢查一遍。

換句話說，在N 個(gè)元素的集合中進(jìn)行插入的最好情況需要N + 1 步——N 步去確認(rèn)被插入的值不在集合中，加上最后插入的1 步。

最壞的情況則是在集合的開頭插入，這時(shí)計(jì)算機(jī)得檢查N 個(gè)格子以保證集合不包含那個(gè)值，然后用N 步來把所有值右移，最后再用1 步來插入新值?？偣?N + 1 步。

這是否意味著因?yàn)樗牟迦氡纫话愕臄?shù)組慢，所以就不要用了呢？當(dāng)然不是。在需要保證數(shù)據(jù)不重復(fù)的場(chǎng)景中，集合是非常重要的（真希望有一天我的電話本能恢復(fù)正常）。但如果沒有這種需求，那么選擇插入比集合快的數(shù)組會(huì)更好一些。具體哪種數(shù)據(jù)結(jié)構(gòu)更合適，當(dāng)然要根據(jù)你的實(shí)際應(yīng)用場(chǎng)景而定。

總結(jié)

理解數(shù)據(jù)結(jié)構(gòu)的性能，關(guān)鍵在于分析操作所需的步數(shù)。采取哪種數(shù)據(jù)結(jié)構(gòu)將決定你的程序是能夠承受住壓力，還是崩潰。本文特別講解了如何通過步數(shù)分析來判斷某種應(yīng)用該選擇數(shù)組還是集合。