點擊上方藍字，關注公眾號
鏈表概念的講解
鏈表是什么
鏈表是一種線性數據結構，每個節點都存有數據，通過指針將各個節點鏈接在一起。
鏈表的性質
- 一致性: 每個節點有相同的數據結構，相同的數據大小，內存中占據相同的大小，存儲相同的數據類型。
- 有序性: 節點之間的相對順序固定，排在某節點前面的節點就是它的前驅，后面的節點就是它的后繼，所以定義里面有'線性'。
鏈表的分類
鏈接方式分類：單向鏈表，雙向鏈表。
ps: 代碼展示只用單鏈表舉例。
單鏈表結構
節點定義
class?Node(object):"""單鏈表結構的Node節點"""
????def?__init__(self,?data,?next_node=None):"""Node節點的初始化方法。
????????data:存儲的數據
????????next:下一個Node節點的引用地址
????????"""
????????self.data?=?data
????????self.next?=?next_node雙鏈表結構
雙鏈表中的每個節點包含數據+指向前驅和后繼的指針。
鏈表的基本操作
鏈表基本操作: ?插入，搜索，刪除。以下分別講每個操作是如何操作的，時間復雜度多少，為什么是那么多，根據時間復雜度判斷鏈表的適合場景。查找
按照索引/值查找: 遍歷找到對應的位置/值，然后返回該節點。
#?按照值查找
node?=?head_nodewhile?node.data?!=?value:
????node?=?node.next_node#?按照索引查找
pos?=?0while?pos?!=?index:
????node?=?node.next_node
????pos?+=?1時間復雜度：是線性遍歷的，所以時間復雜度是O(n)。因為時間復雜度相對較高，所以在大量數據需要經常用檢索的時候就不要用鏈表了。
插入
按照index插入
1.先創建新節點new_node
2.找到要插入的位置的前驅節點pre
3.新節點new_node指向pre的后繼節點
4.pre指向新節點
new_node.next?=?pred.next
pred.next?=?new_node時間復雜度：由于第2步要線性遍歷去找index位置，所以時間復雜度是O(n)。如果插入在頭部，就不需要找位置，時間復雜度是O(1)。
刪除
如何做刪除的?
1.找到待刪節點的前驅pred
2.把它的前驅節點的后繼指向待刪節點后繼的后繼
pred.next?=?pred.next.next時間復雜度：因為要去找前驅，所以線性遍歷，時間復雜度是O(n)。如果刪除頭部，就不需要找位置，時間復雜度是O(1)。
鏈表常見的考點: 啞節點(邊界條件)- 用于簡化邊界情況，鏈表為空或鏈表的頭結點和尾節點。解決辦法，自己創建一個啞節點，然后把它的后繼連接原節點。
鏈表的實際應用，通常用于順序記錄的存儲，無需提前分配空間，僅適用小規模數據存儲。
對于適用的操作屬性來說，鏈表適合查找少，無需排序的使用場景，原因:是鏈表的查找效率不高，通過調整指針可以快速調節節點的相對位置。
業界應用: 小規模日志記錄(通話記錄或通訊錄)，讀到內存中后可以以鏈表的方式進行存儲；操作系統中內存快的緩存也可以用鏈表來實現，LRU緩存(利用了鏈表快速調整相對位置優勢)。
模式識別
以下這些適用解決鏈表相關問題。
runner and chaser類型題目中有關鍵詞: 要尋找每個特定位置/相對位置。就用后移速度不同的快慢指針來解決使以下文章用到這個方法:【LeetCode-19-Remove Nth Node From End of List】刪除鏈表的倒數第N個節點
【LeetCode-141-Linked List Cycle】環形鏈表
【LeetCode-876-Middle of the Linked List】鏈表的中間節點
【LeetCode24. Swap Nodes in Pairs】兩兩交換鏈表中的元素
【LeetCode-25-Reverse Nodes in k-Group】K 個一組翻轉鏈表
【LeetCode-143-Reorder List】重排鏈表，次頭條。
【LeetCode-21. Merge Two Sorted Lists】合并兩個有序鏈表?
自己實現一個單鏈表類
實現插入查找刪除的功能。
class?ListNode(object):
????def?__init__(self,?value):"""
????????value:?節點的數據值
????????next:?節點的后繼
????????"""
????????self.value?=?value
????????self.next?=?None
class?MyLinkedList(object):
????def?__init__(self):"""
????????Initialize?your?data?structure?here.
????????"""
????????self.head?=?ListNode(0)?#?用啞結點來當頭節點，方便處理插入和刪除的邊界情況。
????????self.size?=?0
????def?get(self,?index):"""按照索引查找
????????Get?the?value?of?the?index-th?node?in?the?linked?list.?If?the?index?is?invalid,?return?-1.
????????:type?index:?int
????????:rtype:?int
????????"""#?異常情況:?如果索引無效?|?索引超出范圍if?index?=?self.size:return?-1
????????node?=?self.headfor?_?in?range(index?+?1):?#?記得鏈表的頭結點是啞結點，所以range后界要+1
????????????node?=?node.nextreturn?node.value?#?是返回節點值
????def?addAtHead(self,?val):"""添加到頭節點
????????Add?a?node?of?value?val?before?the?first?element?of?the?linked?list.?After?the?insertion,?the?new?node?will?be?the?first?node?of?the?linked?list.
????????:type?val:?int
????????:rtype:?None
????????"""
????????self.addAtIndex(0,?val)
????def?addAtTail(self,?val):"""添加到尾節點
????????Append?a?node?of?value?val?to?the?last?element?of?the?linked?list.
????????:type?val:?int
????????:rtype:?None
????????"""
????????self.addAtIndex(self.size,?val)
????def?addAtIndex(self,?index,?val):"""按照索引添加node
????????:type?index:?int
????????:type?val:?int
????????:rtype:?None
????????"""#?異常情況:?如果索引無效?|?索引超出范圍if?index?=?self.size?+?1:return?#?什么都不做#?找到要加入節點的前驅節點
????????node?=?self.headfor?_?in?range(index):?
????????????node?=?node.next#?加入新節點
????????new_node?=?ListNode(val)?#?創建新節點
????????new_node.next?=?node.next
????????node.next?=?new_node#?鏈表的總數加1
????????self.size?+=?1
????def?deleteAtIndex(self,?index):"""刪除節點
????????因為刪除操作的流程是，待刪節點node的前驅pre，改變pre后繼節點到node的后繼節點，所以找的節點應該是pre
????????:type?index:?int
????????:rtype:?None
????????"""#?異常情況:?如果索引無效?|?索引超出范圍if?index?=?self.size:return?#?什么都不做#?找到要刪除的節點
????????node?=?self.headfor?_?in?range(index):?#?找到待刪節點的前驅節點，因為我們已經在頭部加了啞結點，所以真正的頭部節點是不用單獨處理的，按照常規刪節點的方式處理
????????????node?=?node.next#?刪除待刪節點
????????node.next?=node.next.next#?鏈表的總數減1
????????self.size?-=?1參考資料:
- 力扣
原創文章，歡迎轉載，轉載請在公眾號菜單欄查看【聯系我】。
? ? ? ? ? ? ? 喜歡本文的小伙伴點【在看】分享給你的朋友?↓↓↓
實例代碼)
，缺陷(bug)和異常(exception))
