數(shù)據(jù)結(jié)構(gòu)——鏈表

鏈表也是一種數(shù)據(jù)結(jié)構(gòu)，相比較于數(shù)組，略顯復(fù)雜。鏈表和數(shù)組都是非?；A(chǔ)、非常常用的數(shù)據(jù)結(jié)構(gòu)。

1. 數(shù)組與鏈表的區(qū)別
   從底層的存儲結(jié)構(gòu)上看，二者申請的內(nèi)存空間不一樣：

數(shù)組需要一塊連續(xù)的內(nèi)存空間來存儲，對內(nèi)存要求較高。

鏈表不需要一塊連續(xù)的內(nèi)存空間，它通過"指針"將一組零散的內(nèi)存塊串聯(lián)起來。

例如，當我們申請一個100MB大小的數(shù)組，當內(nèi)存空間中沒有連續(xù)的、足夠大的存儲空間時，即便內(nèi)存的剩余總可用空間大于100MB，仍然會申請失敗。但如果我們申請的是100MB大小的鏈表時，就可以申請成功。

2. 三種常見的鏈表結(jié)構(gòu)
   鏈表結(jié)構(gòu)有很多種，但最常見的主要有如下三種：

單鏈表

雙向鏈表

循環(huán)鏈表

2.1 單鏈表
鏈表通過指針將一組零散的內(nèi)存塊串聯(lián)在一起，我們將內(nèi)存塊稱為鏈表的“結(jié)點”。為了將所有的結(jié)點串聯(lián)在一起，每個鏈表的結(jié)點除了要存儲數(shù)據(jù)之外，還需要記錄鏈上的下一個結(jié)點的地址，這個結(jié)點地址的指針叫作“后繼指針next”。

單鏈表中有兩個結(jié)點比較特殊，分別是第一個結(jié)點和最后一個結(jié)點。我們習(xí)慣性的把第一個結(jié)點叫作頭結(jié)點，最后一個結(jié)點叫作尾結(jié)點。

頭結(jié)點用來記錄鏈表中的基地址，可以根據(jù)頭結(jié)點遍歷得到整個鏈表。

尾結(jié)點的指針不是指向下一個結(jié)點，而是指向一個空地址NULL，表示這是鏈表上最后一個結(jié)點。

在鏈表中進行數(shù)據(jù)的插入和刪除操作要比數(shù)組中高效。因為在數(shù)組中進行插入、刪除操作時，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，需要做大量的數(shù)據(jù)移動，時間復(fù)雜度是O(n)。而在鏈表中存儲空間本身就不是連續(xù)的，不需要為了保持內(nèi)存的連續(xù)性而移動大量的數(shù)據(jù)。

在鏈表的插入和刪除操作中，我們只需要考慮相鄰結(jié)點的指針改變，所以對應(yīng)的時間復(fù)雜度是O(1)。

鏈表中數(shù)據(jù)的插入和刪除比數(shù)組高效，但當需要隨機訪問第k個數(shù)據(jù)時，就沒有數(shù)組高效。因為鏈表中的數(shù)據(jù)不是連續(xù)存儲的，無法像數(shù)組那樣，根據(jù)首地址和下標，通過尋址公式直接計算出對應(yīng)的內(nèi)存地址，而是需要根據(jù)指針一個結(jié)點一個結(jié)點依次遍歷，直到找到對應(yīng)的結(jié)點。

2.2 循環(huán)鏈表
循環(huán)鏈表的本質(zhì)是一種特殊的單鏈表，與單鏈表的區(qū)別就是在尾結(jié)點。單鏈表中的尾結(jié)點指針指向空地址，表示這就是最后的結(jié)點。而循環(huán)鏈表的尾結(jié)點指針指向鏈表的頭結(jié)點。
與單鏈表相比，循環(huán)鏈表的優(yōu)點是從鏈尾到鏈頭比較方便。當需要處理的數(shù)據(jù)具有環(huán)形結(jié)構(gòu)特點時，就適合用循環(huán)鏈表處理。比如著名的“約瑟夫問題”。

2.3 雙向鏈表
單鏈表中只有一個方向，結(jié)點只有一個后繼指針next指向后面的結(jié)點。而雙向鏈表中，有兩個方向，每個結(jié)點不僅有一個后繼指針指向后面的結(jié)點，還有一個前驅(qū)指針prev指向前面的結(jié)點。

雙向鏈表需要額外的兩個空間來存儲后繼結(jié)點和前驅(qū)結(jié)點的地址。所以當存儲同樣多的數(shù)據(jù)時，雙向鏈表要比單鏈表占用更多的內(nèi)存空間。

雖然雙向鏈表中有兩個指針比較浪費存儲空間，但可以支持雙向遍歷，這樣也帶來了雙向鏈表操作的靈活性。

從雙向鏈表從結(jié)構(gòu)上看，可以支持O(1)時間復(fù)雜度的情況下找到前驅(qū)結(jié)點，因此在某些情況下，雙向鏈表的插入、刪除操作比單鏈表更簡單、高效。其實，前面說的單鏈表的插入、刪除操作的時間復(fù)雜度是O(1)是有先決條件的。

2.4 單鏈表與雙向鏈表刪除、插入操作比較
刪除操作

從鏈表中刪除一個數(shù)據(jù)，一般都是如下兩個情況：

刪除結(jié)點中“值等于某個給定值”的結(jié)點

刪除給定指針指向的結(jié)點

第一種情況中：

我們需要先找到值等于給定值的結(jié)點，找到結(jié)點后，再做刪除操作。

這種情況下，單鏈表或雙向鏈表都需要從頭結(jié)點開始一個一個依次的遍歷對比，直到找到值等于給定值的結(jié)點。此時單鏈表和雙向鏈表查找的時間復(fù)雜度均是O(n)，刪除的時間復(fù)雜度是均O(1)，根據(jù)時間復(fù)雜度分析中的加法法則，刪除值等于給定值的結(jié)點的對應(yīng)的鏈表操作總的時間復(fù)雜度是O(n)。且這種情況下單鏈表與雙向鏈表是同等高效。

第二種情況中：

雖然我們可以根據(jù)指針直接找到要刪除的結(jié)點，但刪除某個結(jié)點q需要知道它的前驅(qū)結(jié)點，而單鏈表中并不支持直接獲取前驅(qū)結(jié)點，此時為了找到前驅(qū)結(jié)點，我們還需要從頭結(jié)點開始遍歷單鏈表，直到p–>next=q，才說明p是q的前驅(qū)結(jié)點。

但在這種情況下，雙向鏈表就有優(yōu)勢了，因為雙向鏈表中的結(jié)點已經(jīng)保存了前驅(qū)結(jié)點的指針，不需要像單鏈表那樣再從頭遍歷一遍。所以這種情況下，單鏈表刪除操作的時間復(fù)雜度是O(n)，而雙向鏈表的時間復(fù)雜度是O(1)。

插入操作

同理，在插入操作中，按照刪除操作的分析思路，可以知道雙向鏈表的時間復(fù)雜度是O(1)；單向鏈表的時間復(fù)雜度是O(n)。

雙向鏈表除了刪除、插入操作上有優(yōu)勢上外，還有對于一個有序鏈表。雙向鏈表的按值查詢效率也比單鏈表高一些。

因為在雙向鏈表中，可以記錄上次查找的位置p，后面每次查找時，可以根據(jù)要查找的值與p位置對應(yīng)值的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。

java中LinkedHashMap底層用到的就是雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)。

在我們平時開發(fā)的過程中有“用空間換時間”和“用時間換空間”的設(shè)計思想：

當內(nèi)存空間充足時，如果追求代碼的執(zhí)行速度，就會選擇空間復(fù)雜度相對較高，時間復(fù)雜度相對較低的算法或數(shù)據(jù)結(jié)構(gòu)。

如果內(nèi)存緊缺，就會選擇空間復(fù)雜度相對較低，時間復(fù)雜度相對較高的算法或數(shù)據(jù)結(jié)構(gòu)。

如果整合循環(huán)鏈表和雙向鏈表，那就組合成了“雙向循環(huán)鏈表”。

3. 數(shù)組與鏈表性能比較
   通過前面的學(xué)習(xí)知道，數(shù)組與鏈表的內(nèi)存存儲有區(qū)別，因此二者的插入、刪除、隨機訪問操作的時間復(fù)雜度正好相反。

當然，不能僅用時間復(fù)雜度的高低去決定使用數(shù)組還是鏈表，還要看情況而定。

數(shù)組簡單易用，申請的是連續(xù)內(nèi)存空間，可以借助CPU的緩存機制，預(yù)讀數(shù)組中的數(shù)據(jù)，這樣隨機訪問的效率會更高。而鏈表中的內(nèi)存空間不是連續(xù)的，因此不能使用CPU緩存機制，沒辦法有效預(yù)讀。

數(shù)組最大的缺點就是大小固定，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間，如果申請的內(nèi)存空間過大，當系統(tǒng)沒有足夠大的連續(xù)內(nèi)存空間時，就會導(dǎo)致內(nèi)存不足(out of memory)。如果聲明的數(shù)組過小，則可能出現(xiàn)不夠用的情況。這時則需要去申請一個更大的內(nèi)存空間，將原數(shù)組中的數(shù)據(jù)拷貝過去，非常耗時。鏈表本身沒有大小的限制，支持動態(tài)擴容。這也是數(shù)組與鏈表之間最大的區(qū)別。

如果代碼對內(nèi)存的使用要求非常高，那建議用數(shù)組。因為鏈表中的每個結(jié)點都需要消耗額外的存儲空間去存儲一份指向下一個結(jié)點的指針，所以內(nèi)存消耗會翻倍。而且，對鏈表進行頻繁的插入、刪除操作，會導(dǎo)致頻繁的內(nèi)存申請和釋放，容易造成內(nèi)存碎片。如果是在java中，就有可能回導(dǎo)致頻繁的GC。

所以在實際開發(fā)過程中，針對不同類型的項目，要根據(jù)具體情況，權(quán)衡是用數(shù)組還是鏈表。

4. 寫鏈表代碼的技巧
   前面講了鏈表的基本知識，但要寫好鏈表代碼并不是那么簡單的事，下面講幾點寫鏈表代碼的技巧。如果能熟練掌握這幾個技巧，然后多練習(xí)，相信以后也能很輕松的寫出鏈表代碼。

4.1 理解指針或引用的意義
有些語言中有“指針”的概念，比如C語言、C++；有些語言中沒有指針，取而代之的是“引用”，比如java、Python。其實，不管是“指針”還是“引用”它們的意思都是一樣的，都是存儲所指對象的內(nèi)存地址。

對于指針或引用可以理解為：將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針?；蛘哒f：指針中存儲了這個變量的內(nèi)存地址，指向了這個變量，通過指針就能找到這個變量。

例如鏈表代碼一：

p->next = q

這行代碼的意思是：p結(jié)點中的next指針存儲了q結(jié)點的內(nèi)存地址。

鏈表代碼二：

p->next=p->next->next

表示：p結(jié)點的next指針存儲了p結(jié)點的下下一個結(jié)點的內(nèi)存地址。

掌握指針或引用的概念是看懂鏈表代碼的前提。

4.2 利用哨兵簡化實現(xiàn)難度
在上面單鏈表的結(jié)點p后面插入一個新的結(jié)點，只需要下面兩行代碼就行了：

new_node->next = p->next
p->next = new_node

但當我們向一個空鏈表中插入一個結(jié)點時，光上面的兩行代碼就不行了，需要先進行特殊處理下：

if (head == null) {
head = new_node;
}

其中，head表示鏈表的頭結(jié)點。因此可以發(fā)現(xiàn)對于單鏈表的插入操作，第一個結(jié)點和其他結(jié)點的插入邏輯是不一樣的。

再看下單鏈表結(jié)點的刪除操作。如果要刪除結(jié)點p的后繼結(jié)點，那么一行代碼就行了：

p->next = p->next->next;

但如果要刪除的是鏈表中的最后一個結(jié)點，前面的刪除代碼就不行了，同樣需要先進行特殊處理：

if (head->next == null) {
head = null;
}

從上面的分析可知，針對鏈表的插入、刪除操作，需要對插入第一個結(jié)點和刪除最后一個結(jié)點的情況進行特別處理。這樣在代碼實現(xiàn)的時候不僅會顯得繁瑣，還容易出錯。此時如果我們引入哨兵結(jié)點，那么在任何時候，不管鏈表是不是空，head指針都會一直指向這個哨兵結(jié)點。我們將有哨兵結(jié)點的鏈表叫作“帶頭鏈表”，沒有哨兵結(jié)點的鏈表叫作“不帶頭鏈表”。

哨兵結(jié)點是不存儲數(shù)據(jù)的。因為哨兵結(jié)點一直存在，所以插入第一個結(jié)點和插入其他結(jié)點，刪除最后一個結(jié)點和刪除其他結(jié)點，都可以用相同的代碼實現(xiàn)邏輯。

使用這種哨兵簡化了編程難度。在插入排序、歸并排序和動態(tài)規(guī)劃中都有運用。

為了加深理解，舉一個C語言代碼的例子：

代碼一：

// 在數(shù)組 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示數(shù)組 a 的長度
int find(char* a, int n, char key) {
// 邊界條件處理，如果 a 為空，或者 n<=0，說明數(shù)組中沒有數(shù)據(jù)，就不用 while 循環(huán)比較了
if(a == null || n <= 0) {
return -1;
}

int i = 0;
// 這里有兩個比較操作：i<n 和 a[i]==key.
while (i < n) {
if (a[i] == key) {
return i;
}
++i;
}

return -1;
}

代碼二：

// 在數(shù)組 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示數(shù)組 a 的長度
// 我舉 2 個例子，你可以拿例子走一下代碼
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
int find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}

// 這里因為要將 a[n-1] 的值替換成 key，所以要特殊處理這個值
if (a[n-1] == key) {
return n-1;
}

// 把 a[n-1] 的值臨時保存在變量 tmp 中，以便之后恢復(fù)。tmp=6。
// 之所以這樣做的目的是：希望 find() 代碼不要改變 a 數(shù)組中的內(nèi)容
char tmp = a[n-1];
// 把 key 的值放到 a[n-1] 中，此時 a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;

int i = 0;
// while 循環(huán)比起代碼一，少了 i<n 這個比較操作
while (a[i] != key) {
++i;
}

// 恢復(fù) a[n-1] 原來的值, 此時 a= {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;

if (i == n-1) {
// 如果 i == n-1 說明，在 0...n-2 之間都沒有 key，所以返回 -1
return -1;
} else {
// 否則，返回 i，就是等于 key 值的元素的下標
return i;
}
}

對比上面的兩段代碼，在字符串a(chǎn)很長的時候，代碼二運行會更快一點，因為在兩段代碼中執(zhí)行次數(shù)最多的就是while循環(huán)部分。而在第二段代碼中，我們通過一個哨兵a[n-1]=key，成功的省掉了一個比較語句i<n，當累積執(zhí)行幾萬次、幾十萬次時，累積的時間就會很明顯了。當然這里只是為了舉例說明哨兵的作用，才會寫代碼二，正常情況下都是寫代碼一，因為代碼二可閱讀性太差，大多數(shù)情況下，我們也沒必要去追求極致的性能。

4.3 重點留意邊界條件處理
在寫鏈表代碼中，在邊界條件下也很容易出現(xiàn)bug，平時我們可以從如下幾個方面去檢查鏈表代碼邊界條件是否正確：

如果鏈表為空時，代碼是否還能正常工作？

如果鏈表只包含了一個結(jié)點，代碼是否還能正常工作？

如果鏈表中只包含兩個結(jié)點，代碼是否能正常工作？

代碼邏輯在處理頭結(jié)點和尾結(jié)點時，是否還能正常工作？

在寫完鏈表代碼后，可以從如上幾點去考慮下那些邊界條件。這樣才能更好的保證代碼的健壯性。