數據結構——鏈表

鏈表也是一種數據結構，相比較于數組，略顯復雜。鏈表和數組都是非常基礎、非常常用的數據結構。

1. 數組與鏈表的區別
   從底層的存儲結構上看，二者申請的內存空間不一樣：

數組需要一塊連續的內存空間來存儲，對內存要求較高。

鏈表不需要一塊連續的內存空間，它通過"指針"將一組零散的內存塊串聯起來。

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

2. 三種常見的鏈表結構
   鏈表結構有很多種，但最常見的主要有如下三種：

單鏈表

雙向鏈表

循環鏈表

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

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

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

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

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

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

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

2.2 循環鏈表
循環鏈表的本質是一種特殊的單鏈表，與單鏈表的區別就是在尾結點。單鏈表中的尾結點指針指向空地址，表示這就是最后的結點。而循環鏈表的尾結點指針指向鏈表的頭結點。
與單鏈表相比，循環鏈表的優點是從鏈尾到鏈頭比較方便。當需要處理的數據具有環形結構特點時，就適合用循環鏈表處理。比如著名的“約瑟夫問題”。

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

雙向鏈表需要額外的兩個空間來存儲后繼結點和前驅結點的地址。所以當存儲同樣多的數據時，雙向鏈表要比單鏈表占用更多的內存空間。

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

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

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

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

刪除結點中“值等于某個給定值”的結點

刪除給定指針指向的結點

第一種情況中：

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

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

第二種情況中：

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

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

插入操作

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

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

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

java中LinkedHashMap底層用到的就是雙向鏈表這種數據結構。

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

當內存空間充足時，如果追求代碼的執行速度，就會選擇空間復雜度相對較高，時間復雜度相對較低的算法或數據結構。

如果內存緊缺，就會選擇空間復雜度相對較低，時間復雜度相對較高的算法或數據結構。

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

3. 數組與鏈表性能比較
   通過前面的學習知道，數組與鏈表的內存存儲有區別，因此二者的插入、刪除、隨機訪問操作的時間復雜度正好相反。

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

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

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

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

所以在實際開發過程中，針對不同類型的項目，要根據具體情況，權衡是用數組還是鏈表。

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

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

對于指針或引用可以理解為：將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針。或者說：指針中存儲了這個變量的內存地址，指向了這個變量，通過指針就能找到這個變量。

例如鏈表代碼一：

p->next = q

這行代碼的意思是：p結點中的next指針存儲了q結點的內存地址。

鏈表代碼二：

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

表示：p結點的next指針存儲了p結點的下下一個結點的內存地址。

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

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

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

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

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

其中，head表示鏈表的頭結點。因此可以發現對于單鏈表的插入操作，第一個結點和其他結點的插入邏輯是不一樣的。

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

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

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

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

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

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

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

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

代碼一：

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

代碼二：

// 在數組 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示數組 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 中，以便之后恢復。tmp=6。
// 之所以這樣做的目的是：希望 find() 代碼不要改變 a 數組中的內容
char tmp = a[n-1];
// 把 key 的值放到 a[n-1] 中，此時 a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;

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

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

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

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

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

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

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

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