面試指北：算法與數(shù)據(jù)結(jié)構(gòu)（三）數(shù)組與鏈表

這次來說說數(shù)組與鏈表。在說數(shù)組與鏈表之前，先來介紹一下線性表和非線性表。

線性表 LinearList

顧名思義，線性表的結(jié)構(gòu)是線性的。就像圖書館書架上的書一樣，每一行的書都是整齊的排列在直直的書板上。高樓在垂直方向上也可以說是線性的，每一層樓都可以看作是一個單位，依次上下排列。

說到線性表的本質(zhì)，就是每個元素之間，只有前后關(guān)系。書架上的書，相鄰的兩本書，其中一本必然在另一本的前邊或者后邊（不考慮上下層）。相鄰的兩層樓，其中一層必然在另一層的上邊或者下邊。

由此看來，數(shù)組、鏈表都屬于線性表，另外棧、隊列也屬于此類。

非線性表

與線性表對應(yīng)的就是非線性表。非線性表的每個元素之間關(guān)系更加多元，不只是有前后關(guān)系。

一棵樹，樹干長出樹枝，樹枝又可以分叉，最后長出樹葉。那樹枝之間有父子關(guān)系、兄弟關(guān)系。一張地圖，主要地點之間的關(guān)系則更加復(fù)雜。

數(shù)據(jù)結(jié)構(gòu)中的樹、圖等都是非線性結(jié)構(gòu)。

數(shù)組與鏈表

先來看一張圖。

這是一個抽屜柜。但這也能夠反應(yīng)硬盤空間的結(jié)構(gòu)。抽象來看，硬盤本質(zhì)上就是一個一維的、每個元素相等大小緊密排列的結(jié)構(gòu)，雖然硬盤我們看到是一個 3D 實物，但最終總能夠映射成一維的空間。

數(shù)組則完全是硬盤結(jié)構(gòu)的映射，使用連續(xù)的內(nèi)存空間存儲數(shù)據(jù)?？梢哉f數(shù)組這種數(shù)據(jù)結(jié)構(gòu)在使用內(nèi)存上非常直接，申請一塊連續(xù)的內(nèi)存空間，然后存儲數(shù)據(jù)即可。就好像 a、b、c 三人的房屋在一條街上各自相鄰，去完 a 家，往右走兩步就是 b 家，再走兩步就是 c 家。

但是這也帶來了一個核心問題——如果內(nèi)存中沒有一塊連續(xù)的內(nèi)存空間可供使用怎么辦。在內(nèi)存中我們運行著操作系統(tǒng)和眾多軟件。軟件運行會加載到內(nèi)存中，結(jié)束時會釋放掉。經(jīng)過反復(fù)的這個過程，我們的內(nèi)存空間會變得十分零碎。很可能空余的空間有 100 個空位，但是這 100 個空位是不連續(xù)的、被其他正在使用中的內(nèi)存分割開的，那我們申請 100 個空間的數(shù)組時也會失敗。

這也導(dǎo)致了鏈表的產(chǎn)生。

鏈表為了解決數(shù)組強制要求分配連續(xù)空間的問題，通過在當前元素中記錄下一個元素地址的方式，將多個分散在內(nèi)存空間中的元素聯(lián)系起來。就好像 a、b、c 三人的房屋并不是相連，而是隔了很遠，但是 a 知道 b 家的地址，b 又知道 c 家的地址，這樣我們只要知道 a 的地址，總能找到 b、c 的位置。

天下沒有免費的午餐，鏈表雖然不需要連續(xù)的內(nèi)存空間，但是每個元素需要記憶下一個元素的位置，這增加了鏈表單個元素的空間占用。相當于鏈表通過單個元素的空間占用來解綁整體內(nèi)存空間連續(xù)的強制要求。算法與數(shù)據(jù)結(jié)構(gòu)中充滿了這種 Trade-Off。

總結(jié)一下，數(shù)組要求內(nèi)存空間連續(xù)，但是只要通過簡單的 base_address + k * size 的方式，就能夠馬上訪問第 k 個元素，即具有 O(1) 隨機訪問的能力。鏈表不要求內(nèi)存空間連續(xù)，但是需要從頭開始，一個個依次訪問元素之后才能夠找到第 k 個元素。

對比

不管是數(shù)組還是鏈表，我們對其進行操作一般包括：插入數(shù)據(jù)、刪除數(shù)據(jù)、查找數(shù)據(jù)。接下來我們通過這三個操作來對比一下兩者。而分析的時候必然會涉及到時間復(fù)雜度，我們先來簡單說說時間復(fù)雜度如何分析。

時間復(fù)雜度

我們一般會使用大 O 表示法來作為時間復(fù)雜度分析的工具，或者說表示方式。我們在進行時間復(fù)雜度分析時，并不關(guān)注算法的實際執(zhí)行時間，而是關(guān)注代碼執(zhí)行時間在數(shù)據(jù)規(guī)模增長時的變化趨勢。簡單來說，我們分析的是在數(shù)據(jù)規(guī)模 n 下，代碼的執(zhí)行次數(shù)。最后用大 O 表示法表示。 結(jié)合如下偽代碼，介紹一下其分析方法：

1.只關(guān)注循環(huán)執(zhí)行次數(shù)最多的代碼，忽略其常量、低階、系數(shù);2.加法法則：一段代碼的總復(fù)雜度，等于量級最大的那段代碼的復(fù)雜度；3.乘法法則：嵌套代碼的復(fù)雜度等于內(nèi)外代碼復(fù)雜度的乘積。

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[n]);        print(array[n]);    }
    // 3: o(n^2)    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            print(array[i] * array[j]);        }    }}

這里我們的數(shù)據(jù)量為 n。

首先我們看注釋 1 處，雖然這里訪問了兩次 array，但是我們忽略其常量，所以這段代碼復(fù)雜度為 O(1)。

我們再看注釋 2 處，這里通過循環(huán)對數(shù)組進行打印了兩次，訪問了數(shù)組的所有元素，所以其代碼復(fù)雜度為 O(2n)，但是我們會忽略系數(shù)，所以這段代碼時間復(fù)雜度為 O(n)。

我們最后看注釋 3 處，通過兩層循環(huán)嵌套，每個循環(huán)均訪問了數(shù)據(jù)所有元素，打印數(shù)組元素的乘積，每層循環(huán)的時間復(fù)雜度為 O(n)，根據(jù)乘法法則，這段代碼的時間復(fù)雜度為 O(n) * O(n)，即 O(n^2)。

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

空間復(fù)雜度的分析方式和時間復(fù)雜度類似，只不過是把代碼執(zhí)行次數(shù)換成空間占用。

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

接下來我們繼續(xù)對比數(shù)組和鏈表。

插入數(shù)據(jù)

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

鏈表的插入就比較簡單，直接操作一下元素的指針指向即可，在 O(1) 時間復(fù)雜度即可完成。當然這里說的是已經(jīng)知道插入位置的情況，不包含查找插入位置的過程。

刪除數(shù)據(jù)

數(shù)組刪除數(shù)據(jù)時，為了保證占用空間的連續(xù)，刪除后需要搬移后續(xù)數(shù)據(jù)，所以其時間復(fù)雜度為 O(n)。當然這里可以做一下優(yōu)化，即刪除數(shù)據(jù)后不要馬上搬移數(shù)據(jù)，而是先記錄下來，空間不夠時再進行一次搬移數(shù)據(jù)的操作。這個就是 Java 虛擬機垃圾回收機制中 標記清除算法 的核心思想。

鏈表刪除數(shù)據(jù)也比較簡單，直接操作元素的指針指向即可，時間復(fù)雜度為 O(1)。

訪問數(shù)據(jù)

假設(shè)我們現(xiàn)在要訪問第 k 個元素，數(shù)組因為空間連續(xù)的特性，通過上述地址計算公式直接拿到第 k 個元素的地址，直接訪問即可，時間復(fù)雜度為 O(1)。鏈表則比較麻煩，因為其空間不連續(xù)，我們需要從頭開始，一個一個的依次拿到后續(xù)元素的地址，直到第 k 個。所以其時間復(fù)雜度為 O(n)。

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

總結(jié)

最后我們可以得出結(jié)論，數(shù)組與鏈表的主要區(qū)別在于內(nèi)存空間是否連續(xù)。數(shù)組要求內(nèi)存空間連續(xù)，所以分配內(nèi)存時條件更加苛刻，但是這讓數(shù)組能夠 O(1) 隨機訪問元素。鏈表無需內(nèi)存空間連續(xù)，分配內(nèi)存的條件比較寬松，但是這導(dǎo)致鏈表占用空間更大，訪問元素時間復(fù)雜度較高。

最后推薦一下我正在編寫的小程序 VirtualLearning，它能夠可視化一些算法與數(shù)據(jù)結(jié)構(gòu)，讓你更直觀的學(xué)習(xí)。目前支持了主要的排序算法，更多內(nèi)容擴充中，敬請期待。