一、什么是鏈表？

1.和數(shù)組一樣，鏈表也是一種線性表。

2.從內(nèi)存結(jié)構(gòu)來看，鏈表的內(nèi)存結(jié)構(gòu)是不連續(xù)的內(nèi)存空間，是將一組零散的內(nèi)存塊串聯(lián)起來，從而進行數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)。

3.鏈表中的每一個內(nèi)存塊被稱為節(jié)點Node。結(jié)點除了存儲數(shù)據(jù)外，還需記錄鏈上下一個結(jié)點的地址，即后繼指針next。

二、為什么使用鏈表？（鏈表的特點）

1.插入、刪除效率高，時間復(fù)雜度為 O(1) 級別(只需更改指針指向即可)，隨機訪問效率低，時間復(fù)雜度為 O(n) 級別(需要從鏈頭至鏈尾進行遍歷)。

2.和數(shù)組相比，內(nèi)存空間消耗更大，因為每個存儲數(shù)據(jù)的節(jié)點都需要額外的空間存儲后繼指針。

三、常見的鏈表結(jié)構(gòu)

1.單鏈表

1）每個節(jié)點只包含一個指針，即后繼指針。

2）單鏈表有兩個特殊的節(jié)點，即首節(jié)點和尾節(jié)點

為什么特殊？

• 用首節(jié)點地址表示整條鏈表
• 尾節(jié)點的后繼指針指向空地址null

3）性能特點

插入和刪除節(jié)點的時間復(fù)雜度為O（1）

查找的時間復(fù)雜度為O（n）

2.循環(huán)鏈表

循環(huán)鏈表是一種特殊的單鏈表，除了尾節(jié)點的后繼指針指向首節(jié)點的地址外均與單鏈表一致

和單鏈表相比，循環(huán)鏈表的優(yōu)點是從鏈表到鏈頭比較方便。

適用于存儲有循環(huán)特點的數(shù)據(jù)，如約瑟夫問題

3.雙向鏈表

1）節(jié)點除了存儲數(shù)據(jù)外，還有兩個地址分別指向前一個節(jié)點地址（前驅(qū)指針prev）和下一個節(jié)點地址（后繼指針next）

2）首節(jié)點的前驅(qū)指針prev和尾節(jié)點的后繼指針均指向空地址

3）性能特點：

和單鏈表相比，存儲相同的數(shù)據(jù)，需要消耗更多的存儲空間。

插入、刪除操作比單鏈表效率更高，為O（1）級別

以刪除操作為例，刪除操作分為2種情況：

• 給定數(shù)據(jù)值刪除對應(yīng)節(jié)點
• 給定節(jié)點地址刪除節(jié)點
  對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進行遍歷，從而找到對應(yīng)節(jié)點進行刪除。
  對于第二種情況，要進行刪除操作必須找到前驅(qū)節(jié)點，單鏈表需要從頭到尾進行遍歷直到p->next = q，時間復(fù)雜度為O（n），而雙向鏈表可以直接找到前驅(qū)節(jié)點，時間復(fù)雜度為O（1）.

對于一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。

因為我們可以記錄上次查找的位置p，每一次查詢時，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。

4.雙向循環(huán)鏈表

首節(jié)點的前驅(qū)指針指向尾節(jié)點，尾節(jié)點的后繼指針指向首節(jié)點。

四、選擇數(shù)組還是鏈表？

1.插入、刪除和隨機訪問的時間復(fù)雜度

數(shù)組：插入、刪除的時間復(fù)雜度是O（n），隨機訪問的時間復(fù)雜度是O（1）

鏈表：插入、刪除的時間復(fù)雜度是O（1），隨機訪問的時間復(fù)雜度是O（n）

2.數(shù)組的缺點

1）若申請內(nèi)存空間很大，比如100MB，但若內(nèi)存空間沒有100Mb的連續(xù)空間時，則會申請失敗，盡管內(nèi)存可用空間超過100MB

2）大小固定，若存儲空間不足，需進行擴容，一旦擴容就要進行數(shù)據(jù)復(fù)制（數(shù)據(jù)搬移），而這是非常耗時的。

3.鏈表的缺點

1）內(nèi)存空間消耗更大，因為需要額外的空間存儲指針信息。

2）對鏈表進行頻繁的插入和刪除操作，會導(dǎo)致頻繁的內(nèi)存申請和釋放，容易造成內(nèi)存碎片，如果時Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。

4.如何選擇？

數(shù)組簡單易用，在實現(xiàn)上使用連續(xù)的內(nèi)存空間，可以借助CPU的緩沖機制預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高

鏈表在內(nèi)存中并不是連續(xù)存儲，所以對CPU緩存不友好，沒辦法預(yù)讀

如果代碼對內(nèi)存的使用非常苛刻，那數(shù)組就更適合。