本講內(nèi)容
鏈表定義和分類
鏈表和數(shù)組比較
鏈表操作
寫鏈表代碼的技巧
簡單算法題
鏈表定義和分類
定義：通過指針把零散的內(nèi)存空間串聯(lián)起來存儲數(shù)據(jù)
思想：空間換時間
對于執(zhí)行較慢的程序垒探，可以通過消耗更多的內(nèi)存（空間換時間）來進(jìn)行優(yōu)化葬荷；而消耗過多內(nèi)存的程序供置，可以通過消耗更多的時間（時間換空間）來降低內(nèi)存的消耗督暂。
分類：單鏈表乎芳，循環(huán)鏈表馋缅，雙向鏈表贫途，雙向循環(huán)鏈表
循環(huán)鏈表是一種特殊的單鏈表，單鏈表尾指針指向null蹋肮，循環(huán)鏈表尾指針指向頭節(jié)點
單鏈表是單向的出刷，每個節(jié)點只有一個指針，而雙向鏈表每個節(jié)點有兩個指針括尸，所以占用的空間更大巷蚪，但是它的操作相比于單鏈表更靈活高效。
接下來我們看下主要高效在什么地方濒翻？
刪除操作：
- 刪除結(jié)點中“值等于某個給定值”的結(jié)點；
- 刪除給定指針指向的結(jié)點啦膜。
第一種情況有送，不管是單鏈表還是雙向鏈表，為了查找到值等于給定值的結(jié)點僧家，都需要從頭結(jié)點開始一個一個依次遍歷對比雀摘，直到找到值等于給定值的結(jié)點，然后再通過我前面講的指針操作將其刪除八拱。盡管單純的刪除操作時間復(fù)雜度是 O(1)阵赠，但遍歷查找的時間是主要的耗時點涯塔，對應(yīng)的時間復(fù)雜度為 O(n)。根據(jù)時間復(fù)雜度分析中的加法法則清蚀，刪除值等于給定值的結(jié)點對應(yīng)的鏈表操作的總時間復(fù)雜度為 O(n)匕荸。
第二種情況，我們已經(jīng)找到了要刪除的結(jié)點枷邪，但是刪除某個結(jié)點 q 需要知道其前驅(qū)結(jié)點榛搔，而單鏈表并不支持直接獲取前驅(qū)結(jié)點，所以东揣，為了找到前驅(qū)結(jié)點践惑，我們還是要從頭結(jié)點開始遍歷鏈表，直到 p->next=q嘶卧，說明 p 是 q 的前驅(qū)結(jié)點尔觉。
對于單鏈表，需要從頭遍歷找到該節(jié)點的前向節(jié)點指針芥吟，然后指向刪除操作侦铜，刪除操作時間復(fù)雜度O(1)，但是遍歷節(jié)點的時間復(fù)雜度為 O(n)运沦，所以根據(jù)復(fù)雜度計算的加法原則泵额，總時間復(fù)雜度為 O(n)
對于雙向鏈表，找到的節(jié)點包含前向節(jié)點的指針携添，因此不需要再進(jìn)行遍歷嫁盲，找到前向節(jié)點O(1)，刪除節(jié)點O(1)烈掠，所以總時間復(fù)雜度為 O(1)
鏈表和數(shù)組比較
| 分類 | 內(nèi)存 | 優(yōu)點 | 缺點 |
|---|---|---|---|
| 數(shù)組 | 連續(xù)內(nèi)存羞秤，可以隨機(jī)讀取 | 結(jié)構(gòu)簡單，使用容易左敌，可以利用CPU的緩存 | 1. 大小固定瘾蛋，為避免越界一般會超額申請，即使有容器類的數(shù)組矫限，但是在擴(kuò)容時哺哼，會先拷貝現(xiàn)有的數(shù)據(jù)，性能比較差 |
| 鏈表 | 零散內(nèi)存叼风，需要通過指針進(jìn)行連接和取值 | 插入刪除操作時間復(fù)雜度O(1)取董，頻繁的插入刪除會導(dǎo)致內(nèi)存碎片多，需要進(jìn)行垃圾回收 | 占用空間多 |
鏈表操作
-
插入和刪除
單鏈表的插入和刪除 查找
寫鏈表代碼技巧
技巧一：理解指針或引用的含義
將某個變量賦值給指針无宿，實際上就是將這個變量的地址賦值給指針茵汰，或者反過來說，指針中存儲了這個變量的內(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)存地址溉卓。
技巧二：警惕指針丟失和內(nèi)存泄漏
示例：
單鏈表的插入
p->next = x; // 將p的next指針指向x結(jié)點；
x->next = p->next; // 將x的結(jié)點的next指針指向b結(jié)點搬泥；
以上代碼會導(dǎo)致指針丟失桑寨，b節(jié)點后的節(jié)點無法訪問
插入結(jié)點時，一定要注意操作的順序
正確寫法：
x->next = p->next; // 將x的結(jié)點的next指針指向b結(jié)點忿檩；
p->next = x; // 將p的next指針指向x結(jié)點尉尾；
刪除鏈表結(jié)點時，也一定要記得手動釋放內(nèi)存空間燥透，否則沙咏，也會出現(xiàn)內(nèi)存泄漏的問題。當(dāng)然班套，對于像 Java 這種虛擬機(jī)自動管理內(nèi)存的編程語言來說肢藐，就不需要考慮這么多了。
注：什么是內(nèi)存泄漏吱韭？
內(nèi)存泄露 memory leak吆豹，是指程序在申請內(nèi)存后，無法釋放已申請的內(nèi)存空間理盆，一次內(nèi)存泄露危害可以忽略痘煤，但內(nèi)存泄露堆積后果很嚴(yán)重，無論多少內(nèi)存猿规，遲早會被占光衷快。
memory leak會最終會導(dǎo)致out of memory(內(nèi)存溢出)！
技巧三：利用哨兵簡化實現(xiàn)難度
- 為什么要引入哨兵姨俩？
針對鏈表的插入蘸拔、刪除操作，需要對插入第一個結(jié)點和刪除最后一個結(jié)點的情況進(jìn)行特殊處理环葵。
單鏈表插入
其他節(jié)點插入
x->next = p->next; // 將x的結(jié)點的next指針指向b結(jié)點都伪；
p->next = x; // 將p的next指針指向x結(jié)點；
第一個節(jié)點的插入
if (head == null) { head = new_node;}
單鏈表刪除
其他節(jié)點刪除
p->next = p->next->next;
最后一個節(jié)點刪除
if (head->next == null) { head = null;}
如果我們引入哨兵結(jié)點积担，在任何時候，不管鏈表是不是空猬仁，head 指針都會一直指向這個哨兵結(jié)點帝璧。我們也把這種有哨兵結(jié)點的鏈表叫帶頭鏈表先誉。相反，沒有哨兵結(jié)點的鏈表就叫作不帶頭鏈表的烁。
哨兵結(jié)點是不存儲數(shù)據(jù)的褐耳。因為哨兵結(jié)點一直存在，所以插入第一個結(jié)點和插入其他結(jié)點渴庆，刪除最后一個結(jié)點和刪除其他結(jié)點铃芦，都可以統(tǒng)一為相同的代碼實現(xiàn)邏輯了。
技巧四：重點留意邊界條件處理
要實現(xiàn)沒有 Bug 的鏈表代碼襟雷，一定要在編寫的過程中以及編寫完成之后刃滓，檢查邊界條件是否考慮全面，以及代碼在邊界條件下是否能正確運行耸弄。
常需檢查的邊界情況：
- 如果鏈表為空時咧虎，代碼是否能正常工作？
- 如果鏈表只包含一個結(jié)點時计呈，代碼是否能正常工作砰诵？
- 如果鏈表只包含兩個結(jié)點時，代碼是否能正常工作捌显？
- 代碼邏輯在處理頭結(jié)點和尾結(jié)點的時候茁彭，是否能正常工作？
技巧五：舉例畫圖扶歪，輔助思考
技巧六：多寫多練理肺，沒有捷徑
- 單鏈表反轉(zhuǎn)
- 鏈表中環(huán)的檢測
- 兩個有序的鏈表合并
- 刪除鏈表倒數(shù)第 n 個結(jié)點
- 求鏈表的中間結(jié)點
簡單算法題
如何實現(xiàn)LRU緩存淘汰算法？
