算法與資料結構（三）數組與連結清單

這次來說說數組與連結清單。在說數組與連結清單之前，先來介紹一下線性表和非線性表。

線性表 LinearList

顧名思義，線性表的結構是線性的。就像圖書館書架上的書一樣，每一行的書都是整齊的排列在直直的書闆上。高樓在垂直方向上也可以說是線性的，每一層樓都可以看作是一個機關，依次上下排列。

說到線性表的本質，就是每個元素之間，隻有前後關系。

書架上的書，相鄰的兩本書，其中一本必然在另一本的前邊或者後邊（不考慮上下層）。相鄰的兩層樓，其中一層必然在另一層的上邊或者下邊。

由此看來，數組、連結清單都屬于線性表，另外棧、隊列也屬于此類。

非線性表

與線性表對應的就是非線性表。

非線性表的每個元素之間關系更加多元，不隻是有前後關系。

一棵樹，樹幹長出樹枝，樹枝又可以分叉，最後長出樹葉。那樹枝之間有父子關系、兄弟關系。一張地圖，主要地點之間的關系則更加複雜。

資料結構中的樹、圖等都是非線性結構。

數組與連結清單

先來看一張圖。

這是一個抽屜櫃。但這也能夠反應硬碟空間的結構。抽象來看，硬碟本質上就是一個一維的、每個元素相等大小緊密排列的結構，雖然硬碟我們看到是一個 3D 實物，但最終總能夠映射成一維的空間。

數組則完全是硬碟結構的映射，使用連續的記憶體空間存儲資料。可以說數組這種資料結構在使用記憶體上非常直接，申請一塊連續的記憶體空間，然後存儲資料即可。就好像 a、b、c 三人的房屋在一條街上各自相鄰，去完 a 家，往右走兩步就是 b 家，再走兩步就是 c 家。

但是這也帶來了一個核心問題——如果記憶體中沒有一塊連續的記憶體空間可供使用怎麼辦。在記憶體中我們運作着作業系統和衆多軟體。軟體運作會加載到記憶體中，結束時會釋放掉。經過反複的這個過程，我們的記憶體空間會變得十分零碎。很可能空餘的空間有 100 個空位，但是這 100 個空位是不連續的、被其他正在使用中的記憶體分割開的，那我們申請 100 個空間的數組時也會失敗。

這也導緻了連結清單的産生。

連結清單為了解決數組強制要求配置設定連續空間的問題，通過在目前元素中記錄下一個元素位址的方式，将多個分散在記憶體空間中的元素聯系起來。就好像 a、b、c 三人的房屋并不是相連，而是隔了很遠，但是 a 知道 b 家的位址，b 又知道 c 家的位址，這樣我們隻要知道 a 的位址，總能找到 b、c 的位置。

天下沒有免費的午餐，

連結清單雖然不需要連續的記憶體空間，但是每個元素需要記憶下一個元素的位置，這增加了連結清單單個元素的空間占用。相當于連結清單通過單個元素的空間占用來解綁整體記憶體空間連續的強制要求。

算法與資料結構中充滿了這種 Trade-Off。

總結一下，數組要求記憶體空間連續，但是隻要通過簡單的

base_address + k * size

的方式，就能夠馬上通路第 k 個元素，即具有 O(1) 随機通路的能力。連結清單不要求記憶體空間連續，但是需要從頭開始，一個個依次通路元素之後才能夠找到第 k 個元素。

對比

不管是數組還是連結清單，我們對其進行操作一般包括：插入資料、删除資料、查找資料。接下來我們通過這三個操作來對比一下兩者。而分析的時候必然會涉及到時間複雜度，我們先來簡單說說時間複雜度如何分析。

時間複雜度

我們一般會使用大 O 表示法來作為時間複雜度分析的工具，或者說表示方式。

我們在進行時間複雜度分析時，并不關注算法的實際執行時間，而是關注代碼執行時間在資料規模增長時的變化趨勢。簡單來說，我們分析的是在資料規模 n 下，代碼的執行次數。最後用大 O 表示法表示。

結合如下僞代碼，介紹一下其分析方法：

1. 隻關注循環執行次數最多的代碼，忽略其常量、低階、系數;
2. 加法法則：一段代碼的總複雜度，等于量級最大的那段代碼的複雜度；
3. 乘法法則：嵌套代碼的複雜度等于内外代碼複雜度的乘積。

complexity(int n) {
    int[] array = new int[n];

    // 1: O(1)
    int a = array[0];
    int b = array[1];

    // 2: O(n)
    for (int i = 0; i < n; i++) {
        print(array[i]);
        print(array[i]);
    }

    // 3: o(n^2)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            print(array[i] * array[j]);
        }
    }
}
           

這裡我們的資料量為 n。

首先我們看注釋 1 處，雖然這裡通路了兩次 array，但是我們忽略其常量，是以這段代碼複雜度為 O(1)。

我們再看注釋 2 處，這裡通過循環對數組進行列印了兩次，通路了數組的所有元素，是以其代碼複雜度為 O(2n)，但是我們會忽略系數，是以這段代碼時間複雜度為 O(n)。

我們最後看注釋 3 處，通過兩層循環嵌套，每個循環均通路了資料所有元素，列印數組元素的乘積，每層循環的時間複雜度為 O(n)，根據乘法法則，這段代碼的時間複雜度為 O(n) * O(n)，即 O(n^2)。

那整體來看，這個函數的時間複雜度是多少呢？根據加法法則，同時我們會忽略低階、常量的時間複雜度，最終我們的時間複雜度為 O(n^2)。

空間複雜度的分析方式和時間複雜度類似，隻不過是把代碼執行次數換成空間占用。

常見的時間複雜度有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n!)。

接下來我們繼續對比數組和連結清單。

插入資料

數組的插入資料分為兩種，一種是有序數組插入後仍要保持數組元素有序，另一種是無序數組插入資料。先來看看第一種，為了保證數組的有序，是以我們需要将插入位置之後的資料往後搬移位置，最優情況是插入數組尾部，無需搬移資料，時間複雜度為 O(1)，最壞的情況是插入頭部，需要搬移所有的資料，時間複雜度為 O(n)。平均下來時間複雜度為 O(n)，其平均時間複雜度可以通過權重的方式計算，在此不再詳述。對于第二種無需數組則比較簡單，假如我們插入的位置為 k，隻需将第 k 個元素移到尾部，然後插入資料即可，時間複雜度為 O(1)。

連結清單的插入就比較簡單，直接操作一下元素的指針指向即可，在 O(1) 時間複雜度即可完成。當然這裡說的是已經知道插入位置的情況，不包含查找插入位置的過程。

删除資料

數組删除資料時，為了保證占用空間的連續，删除後需要搬移後續資料，是以其時間複雜度為 O(n)。當然這裡可以做一下優化，即删除資料後不要馬上搬移資料，而是先記錄下來，空間不夠時再進行一次搬移資料的操作。這個就是 Java 虛拟機垃圾回收機制中

标記清除算法

的核心思想。

連結清單删除資料也比較簡單，直接操作元素的指針指向即可，時間複雜度為 O(1)。

通路資料

假設我們現在要通路第 k 個元素，數組因為空間連續的特性，通過上述位址計算公式直接拿到第 k 個元素的位址，直接通路即可，時間複雜度為 O(1)。連結清單則比較麻煩，因為其空間不連續，我們需要從頭開始，一個一個的依次拿到後續元素的位址，直到第 k 個。是以其時間複雜度為 O(n)。

綜上所述，我們可以得到下表。

數組	連結清單
随機讀取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

總結

最後我們可以得出結論，數組與連結清單的主要差別在于記憶體空間是否連續。數組要求記憶體空間連續，是以配置設定記憶體時條件更加苛刻，但是這讓數組能夠 O(1) 随機通路元素。連結清單無需記憶體空間連續，配置設定記憶體的條件比較寬松，但是這導緻連結清單占用空間更大，通路元素時間複雜度較高。

最後推薦一下我正在編寫的小程式

VirtualLearning

，它能夠可視化一些算法與資料結構，讓你更直覺的學習。目前支援了主要的排序算法，更多内容擴充中，敬請期待。

微信掃碼即可體驗，或者搜尋

VirtualLearning

。

掃碼關注微信公衆号