鏈表也是一種數(shù)據(jù)結構，相比較于數(shù)組，略顯復雜。鏈表和數(shù)組都是非?；A、非常常用的數(shù)據(jù)結構。
數(shù)組需要一塊連續(xù)的內(nèi)存空間來存儲，對內(nèi)存要求較高。
鏈表不需要一塊連續(xù)的內(nèi)存空間，它通過"指針"將一組零散的內(nèi)存塊串聯(lián)起來。
例如，當我們申請一個100MB大小的數(shù)組，當內(nèi)存空間中沒有連續(xù)的、足夠大的存儲空間時，即便內(nèi)存的剩余總可用空間大于100MB，仍然會申請失敗。但如果我們申請的是100MB大小的鏈表時，就可以申請成功。
單鏈表
雙向鏈表
循環(huán)鏈表
2.1 單鏈表
鏈表通過指針將一組零散的內(nèi)存塊串聯(lián)在一起，我們將內(nèi)存塊稱為鏈表的“結點”。為了將所有的結點串聯(lián)在一起，每個鏈表的結點除了要存儲數(shù)據(jù)之外，還需要記錄鏈上的下一個結點的地址，這個結點地址的指針叫作“后繼指針next”。
單鏈表中有兩個結點比較特殊，分別是第一個結點和最后一個結點。我們習慣性的把第一個結點叫作頭結點，最后一個結點叫作尾結點。
頭結點用來記錄鏈表中的基地址，可以根據(jù)頭結點遍歷得到整個鏈表。
尾結點的指針不是指向下一個結點，而是指向一個空地址NULL，表示這是鏈表上最后一個結點。
在鏈表中進行數(shù)據(jù)的插入和刪除操作要比數(shù)組中高效。因為在數(shù)組中進行插入、刪除操作時，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，需要做大量的數(shù)據(jù)移動，時間復雜度是O(n)。而在鏈表中存儲空間本身就不是連續(xù)的，不需要為了保持內(nèi)存的連續(xù)性而移動大量的數(shù)據(jù)。
在鏈表的插入和刪除操作中，我們只需要考慮相鄰結點的指針改變，所以對應的時間復雜度是O(1)。
鏈表中數(shù)據(jù)的插入和刪除比數(shù)組高效，但當需要隨機訪問第k個數(shù)據(jù)時，就沒有數(shù)組高效。因為鏈表中的數(shù)據(jù)不是連續(xù)存儲的，無法像數(shù)組那樣，根據(jù)首地址和下標，通過尋址公式直接計算出對應的內(nèi)存地址，而是需要根據(jù)指針一個結點一個結點依次遍歷，直到找到對應的結點。
2.2 循環(huán)鏈表
循環(huán)鏈表的本質(zhì)是一種特殊的單鏈表，與單鏈表的區(qū)別就是在尾結點。單鏈表中的尾結點指針指向空地址，表示這就是最后的結點。而循環(huán)鏈表的尾結點指針指向鏈表的頭結點。
與單鏈表相比，循環(huán)鏈表的優(yōu)點是從鏈尾到鏈頭比較方便。當需要處理的數(shù)據(jù)具有環(huán)形結構特點時，就適合用循環(huán)鏈表處理。比如著名的“約瑟夫問題”。
2.3 雙向鏈表
單鏈表中只有一個方向，結點只有一個后繼指針next指向后面的結點。而雙向鏈表中，有兩個方向，每個結點不僅有一個后繼指針指向后面的結點，還有一個前驅(qū)指針prev指向前面的結點。
雙向鏈表需要額外的兩個空間來存儲后繼結點和前驅(qū)結點的地址。所以當存儲同樣多的數(shù)據(jù)時，雙向鏈表要比單鏈表占用更多的內(nèi)存空間。
雖然雙向鏈表中有兩個指針比較浪費存儲空間，但可以支持雙向遍歷，這樣也帶來了雙向鏈表操作的靈活性。
從雙向鏈表從結構上看，可以支持O(1)時間復雜度的情況下找到前驅(qū)結點，因此在某些情況下，雙向鏈表的插入、刪除操作比單鏈表更簡單、高效。其實，前面說的單鏈表的插入、刪除操作的時間復雜度是O(1)是有先決條件的。
2.4 單鏈表與雙向鏈表刪除、插入操作比較
刪除操作
從鏈表中刪除一個數(shù)據(jù)，一般都是如下兩個情況：
刪除結點中“值等于某個給定值”的結點
刪除給定指針指向的結點
第一種情況中：
我們需要先找到值等于給定值的結點，找到結點后，再做刪除操作。
這種情況下，單鏈表或雙向鏈表都需要從頭結點開始一個一個依次的遍歷對比，直到找到值等于給定值的結點。此時單鏈表和雙向鏈表查找的時間復雜度均是O(n)，刪除的時間復雜度是均O(1)，根據(jù)時間復雜度分析中的加法法則，刪除值等于給定值的結點的對應的鏈表操作總的時間復雜度是O(n)。且這種情況下單鏈表與雙向鏈表是同等高效。
第二種情況中：
雖然我們可以根據(jù)指針直接找到要刪除的結點，但刪除某個結點q需要知道它的前驅(qū)結點，而單鏈表中并不支持直接獲取前驅(qū)結點，此時為了找到前驅(qū)結點，我們還需要從頭結點開始遍歷單鏈表，直到p–>next=q，才說明p是q的前驅(qū)結點。
但在這種情況下，雙向鏈表就有優(yōu)勢了，因為雙向鏈表中的結點已經(jīng)保存了前驅(qū)結點的指針，不需要像單鏈表那樣再從頭遍歷一遍。所以這種情況下，單鏈表刪除操作的時間復雜度是O(n)，而雙向鏈表的時間復雜度是O(1)。
插入操作
同理，在插入操作中，按照刪除操作的分析思路，可以知道雙向鏈表的時間復雜度是O(1)；單向鏈表的時間復雜度是O(n)。
雙向鏈表除了刪除、插入操作上有優(yōu)勢上外，還有對于一個有序鏈表。雙向鏈表的按值查詢效率也比單鏈表高一些。
因為在雙向鏈表中，可以記錄上次查找的位置p，后面每次查找時，可以根據(jù)要查找的值與p位置對應值的大小關系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。
java中LinkedHashMap底層用到的就是雙向鏈表這種數(shù)據(jù)結構。
在我們平時開發(fā)的過程中有“用空間換時間”和“用時間換空間”的設計思想：
當內(nèi)存空間充足時，如果追求代碼的執(zhí)行速度，就會選擇空間復雜度相對較高，時間復雜度相對較低的算法或數(shù)據(jù)結構。
如果內(nèi)存緊缺，就會選擇空間復雜度相對較低，時間復雜度相對較高的算法或數(shù)據(jù)結構。
如果整合循環(huán)鏈表和雙向鏈表，那就組合成了“雙向循環(huán)鏈表”。
當然，不能僅用時間復雜度的高低去決定使用數(shù)組還是鏈表，還要看情況而定。
數(shù)組簡單易用，申請的是連續(xù)內(nèi)存空間，可以借助CPU的緩存機制，預讀數(shù)組中的數(shù)據(jù)，這樣隨機訪問的效率會更高。而鏈表中的內(nèi)存空間不是連續(xù)的，因此不能使用CPU緩存機制，沒辦法有效預讀。
數(shù)組大的缺點就是大小固定，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間，如果申請的內(nèi)存空間過大，當系統(tǒng)沒有足夠大的連續(xù)內(nèi)存空間時，就會導致內(nèi)存不足(out of memory)。如果聲明的數(shù)組過小，則可能出現(xiàn)不夠用的情況。這時則需要去申請一個更大的內(nèi)存空間，將原數(shù)組中的數(shù)據(jù)拷貝過去，非常耗時。鏈表本身沒有大小的限制，支持動態(tài)擴容。這也是數(shù)組與鏈表之間大的區(qū)別。
如果代碼對內(nèi)存的使用要求非常高，那建議用數(shù)組。因為鏈表中的每個結點都需要消耗額外的存儲空間去存儲一份指向下一個結點的指針，所以內(nèi)存消耗會翻倍。而且，對鏈表進行頻繁的插入、刪除操作，會導致頻繁的內(nèi)存申請和釋放，容易造成內(nèi)存碎片。如果是在java中，就有可能回導致頻繁的GC。
所以在實際開發(fā)過程中，針對不同類型的項目，要根據(jù)具體情況，權衡是用數(shù)組還是鏈表。
4.1 理解指針或引用的意義
有些語言中有“指針”的概念，比如C語言、C++；有些語言中沒有指針，取而代之的是“引用”，比如java、Python。其實，不管是“指針”還是“引用”它們的意思都是一樣的，都是存儲所指對象的內(nèi)存地址。
對于指針或引用可以理解為：將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針。或者說：指針中存儲了這個變量的內(nèi)存地址，指向了這個變量，通過指針就能找到這個變量。
例如鏈表代碼一：
p->next = q
這行代碼的意思是：p結點中的next指針存儲了q結點的內(nèi)存地址。
鏈表代碼二：
p->next=p->next->next
表示：p結點的next指針存儲了p結點的下下一個結點的內(nèi)存地址。
掌握指針或引用的概念是看懂鏈表代碼的前提。
4.2 利用哨兵簡化實現(xiàn)難度
在上面單鏈表的結點p后面插入一個新的結點，只需要下面兩行代碼就行了：
new_node->next = p->next
p->next = new_node
但當我們向一個空鏈表中插入一個結點時，光上面的兩行代碼就不行了，需要先進行特殊處理下：
if (head == null) {
head = new_node;
}
其中，head表示鏈表的頭結點。因此可以發(fā)現(xiàn)對于單鏈表的插入操作，第一個結點和其他結點的插入邏輯是不一樣的。
再看下單鏈表結點的刪除操作。如果要刪除結點p的后繼結點，那么一行代碼就行了：
p->next = p->next->next;
但如果要刪除的是鏈表中的最后一個結點，前面的刪除代碼就不行了，同樣需要先進行特殊處理：
if (head->next == null) {
head = null;
}
從上面的分析可知，針對鏈表的插入、刪除操作，需要對插入第一個結點和刪除最后一個結點的情況進行特別處理。這樣在代碼實現(xiàn)的時候不僅會顯得繁瑣，還容易出錯。此時如果我們引入哨兵結點，那么在任何時候，不管鏈表是不是空，head指針都會一直指向這個哨兵結點。我們將有哨兵結點的鏈表叫作“帶頭鏈表”，沒有哨兵結點的鏈表叫作“不帶頭鏈表”。
哨兵結點是不存儲數(shù)據(jù)的。因為哨兵結點一直存在，所以插入第一個結點和插入其他結點，刪除最后一個結點和刪除其他結點，都可以用相同的代碼實現(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
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 中，以便之后恢復。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
++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(chǎn)很長的時候，代碼二運行會更快一點，因為在兩段代碼中執(zhí)行次數(shù)最多的就是while循環(huán)部分。而在第二段代碼中，我們通過一個哨兵a[n-1]=key，成功的省掉了一個比較語句i 4.3 重點留意邊界條件處理 如果鏈表為空時，代碼是否還能正常工作？ 如果鏈表只包含了一個結點，代碼是否還能正常工作？ 如果鏈表中只包含兩個結點，代碼是否能正常工作？ 代碼邏輯在處理頭結點和尾結點時，是否還能正常工作？ 在寫完鏈表代碼后，可以從如上幾點去考慮下那些邊界條件。這樣才能更好的保證代碼的健壯性。 另外有需要云服務器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
在寫鏈表代碼中，在邊界條件下也很容易出現(xiàn)bug，平時我們可以從如下幾個方面去檢查鏈表代碼邊界條件是否正確：
網(wǎng)站標題：數(shù)據(jù)結構——鏈表-創(chuàng)新互聯(lián)
文章路徑：http://weahome.cn/article/dpghpi.html
重慶分公司
重慶分公司
