作者 | 思秀 責編 | 張文
頭圖 | CSDN 下載自視覺中國
來源 | sigua心底的小聲音（ID：SiguaMatrix108）
鍊表概念的講解
鍊表是什麼：
鍊表是一種線性數據結構，每個節點都存有數據，通過指針將各個節點連結在一起。
鍊表的性質：
一致性: 每個節點有相同的數據結構，相同的數據大小，內存中佔據相同的大小，存儲相同的數據類型。有序性: 節點之間的相對順序固定，排在某節點前面的節點就是它的前驅，後面的節點就是它的後繼，所以定義裡面有'線性'。鍊表的分類：
連結方式分類：單向鍊表，雙向鍊表。
ps: 代碼展示只用單鍊表舉例。
單鍊表結構
單鍊表中的每個結點包含數據+指向後繼節點的指針，通過這種方式，單鍊表將所有結點按順序組織起來。節點定義：
classNode(object):"""單鍊表結構的Node節點"""def__init__(self, data, next_node=None):"""Node節點的初始化方法。 data:存儲的數據 next:下一個Node節點的引用地址 """ self.data = data self.next = next_node
雙鍊表結構
雙鍊表中的每個節點包含數據+指向前驅和後繼的指針。
鍊表的基本操作：
鍊表基本操作: 插入、搜索、刪除。
以下分別講每個操作是如何進行的，時間複雜度多少，為什麼是那麼多，根據時間複雜度判斷鍊表的適合場景。
查找
按照索引/值查找：遍歷找到對應的位置/值，然後返回該節點。
# 按照值查找node = head_nodewhilenode.data != value:node = node.next_node
# 按照索引查找pos = 0whilepos != index: node = node.next_nodepos += 1
時間複雜度：是線性遍歷的，所以時間複雜度是 O(n)。因為時間複雜度相對較高，所以在大量數據需要經常用檢索的時候就不要用鍊表了。
插入
按照 index 插入
先創建新節點 new_node；找到要插入的位置的前驅節點 pre；新節點 new_node 指向 pre 的後繼節點；pre 指向新節點。new_node.next = pred.nextpred.next = new_node
時間複雜度：由於第2步要線性遍歷去找 index 位置，所以時間複雜度是 O(n)。如果插入在頭部，就不需要找位置，時間複雜度是 O(1)。
刪除
如何做刪除的？
找到待刪節點的前驅 pred；把它的前驅節點的後繼指向待刪節點後繼的後繼。pred.next = pred.next.next
時間複雜度：因為要去找前驅，所以線性遍歷，時間複雜度是 O(n)。如果刪除頭部，就不需要找位置，時間複雜度是 O(1)。
鍊表常見的考點:
啞節點(邊界條件)-用於簡化邊界情況，鍊表為空或鍊表的頭結點和尾節點。解決辦法：自己創建一個啞節點，然後把它的後繼連接原節點。
鍊表的實際應用，通常用於順序記錄的存儲，無需提前分配空間，僅適用小規模數據存儲。
對於適用的操作屬性來說，鍊表適合查找少，無需排序的使用場景，原因:是鍊表的查找效率不高，通過調整指針可以快速調節節點的相對位置。
業界應用: 小規模日誌記錄（通話記錄或通訊錄），讀到內存中後可以以鍊表的方式進行存儲；作業系統中內存快的緩存也可以用鍊表來實現，LRU 緩存(利用了鍊表快速調整相對位置優勢)。
模式識別
以下這些適用解決鍊表相關問題。
runner and chaser 類型
題目中有關鍵詞: 要尋找每個特定位置/相對位置。就用後移速度不同的快慢指針來解決使
遍歷並處理節點: 處理包括交換，改數值，改指針，刪除等等
這類問題的處理方式是每次操作都是當前節點或某類節點，每次處理單個或一對節點；處理的時候，先改變前驅指針，再改變當前節點指針，否則當前節點的 next 信息改變完之後就不對了，通過先改變前驅的指針到達一個保存狀態的目的。要動一個元素的後繼之前，先保存它的後繼。
處理兩個或多個鍊表
處理方式是用 while 循環進行常規處理，循環條件是 list1 非空並且 list2非空，當循環跳出後處理剩下的非空列表。循環至空，再處理剩餘。
應用遞歸處理(涉及鍊表倒序處理問題)
解決當前問題依賴於存在的相似結構的子問題；利用調用函數本身，先解決子問題，再利用子問題的結果解決當前的問題，遞歸的出口通常是問題的初始條件 n=1 的情況。鍊表問題一旦需要倒序處理或與樹之間的數據結構進行相互轉換往往會用到遞歸，或者用棧來解決。
自己實現一個單鍊表類
實現插入查找刪除的功能。
classListNode(object):def__init__(self, value):""" value: 節點的數據值 next: 節點的後繼 """ self.value = value self.next = NoneclassMyLinkedList(object):def__init__(self):""" Initialize your data structure here. """ self.head = ListNode(0) # 用啞結點來當頭節點，方便處理插入和刪除的邊界情況。 self.size = 0defget(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 < 0or index >= self.size:return-1 node = self.headfor _ in range(index + 1): # 記得鍊表的頭結點是啞結點，所以range後界要+1 node = node.nextreturn node.value # 是返回節點值defaddAtHead(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)defaddAtTail(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)defaddAtIndex(self, index, val):"""按照索引添加node :type index: int :type val: int :rtype: None """# 異常情況: 如果索引無效 | 索引超出範圍if index < 0or 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 += 1defdeleteAtIndex(self, index):"""刪除節點 因為刪除操作的流程是，待刪節點node的前驅pre，改變pre後繼節點到node的後繼節點，所以找的節點應該是pre :type index: int :rtype: None """# 異常情況: 如果索引無效 | 索引超出範圍if index < 0or index >= self.size:return# 什麼都不做# 找到要刪除的節點 node = self.headfor _ in range(index): # 找到待刪節點的前驅節點，因為我們已經在頭部加了啞結點，所以真正的頭部節點是不用單獨處理的，按照常規刪節點的方式處理 node = node.next# 刪除待刪節點 node.next =node.next.next# 鍊表的總數減1 self.size -= 1