用 python 學習資料結構（一）連結串列
一、為什麼要學習資料結構
python 語言和標準庫自帶了很多資料結構，比如 list、set、dict、tuple、queue、heapq等，所以很在標準庫或者第三方庫提供的資料結構夠用的情況下，不需要自己再寫資料結構。
當然，掌握了資料結構的原理之後，面對大量資料的時候，可以更輕鬆地選擇合適的資料結構，以及在標準資料結構不夠用的情況下，可以定製化實現自己的資料結構。
為什麼要有資料結構呢？ 可以考慮在不使用資料結構的情況下，如果需要處理100個數據，是不是就需要使用100個變數來表示它們，如果是10000個數據呢，直接就沒法玩兒了。
所以，資料結構就是把大批量要處理的資料組織起來，方便程式設計的時候使用。資料組織的方式（結構）不同，就形成了多種多樣的資料結構。每種結構都有各自的特點以及適用場景。比如，連結串列只能順序存取一個數據，二叉搜尋樹可以 O(log(n))的時間複雜度存取資料，雜湊表 可以使用 O(log(1))的複雜度存取資料但是比較適用於 key->value的資料型別。
二、連結串列是一種什麼樣的資料結構
接下來就講一下 連結串列（List）這個資料結構的原理。
List是一種比較簡單的資料結構，把資料通過指標(引用)串起來，組成一個鏈，操作者只需要拿著 head 或者 tail（雙向連結串列） 就可以操作所有資料了。
ListNode1 --> ListNode2 --> ListNode3 --> ListNode4
每個 ListNode 包含 資料 以及對下一個 ListNode 的引用，如果我們要在某個位置上插入一個節點，比如在 ListNode3後面插入 ListNode5， 插入之後的情況就是：
ListNode1 --> ListNode2 --> ListNode3 --> ListNode5 --> ListNode4
三、python 語言實現簡單的 List 結構
我們使用 python 一步步來實現一下這個資料結構，主要實現 find、insertBefore、insertAfter、remove、append、count 這幾種操作。
這裡主要是學習之用，所以這裡的操作和一些標準庫的 List 提供的操作介面不太一樣。對於高階語言標準容器的List， 一般不會暴露內部的 ListNode。
關於List 的可迭代性，以及更標準的操作封裝，放在下一次實現吧。
下面就是程式碼了，如果有些不對的地方，歡迎大家指正。
歡迎加入免費的 Python 學習交流群，掃描下面二維碼加入社群或者搜尋公眾號“碼農進步”
#-*- coding: utf-8 -*- class ListNode(): """ 定義連結串列節點的class，表示連結串列中的一個節點，其中儲存了資料以及下一個節點的指標 """ def __init__(self,value): self.value = value self.next = None class List(): """ 定義連結串列類，初始化函式中定義了 head、tail 和 count 變數 head 是頭結點，並不用來儲存資料，所以，真正資料從 head.next開始 這樣做的好處，在連結串列頭部插入節點或者最後一個節點被刪除之後， 連結串列的 head 應用不需要變化，簡化的程式碼的編寫。 """ def __init__(self): self.head = ListNode(0) self.tail = self.head self.count = 0 def __len__(self): """ 返回連結串列的長度，len( listA) 函式會呼叫連結串列物件__len__()函式 """ return self.count def append(self, value): """ 在連結串列的結尾新增一個節點，節點的資料為 value 因為 List 類儲存連結串列的末尾節點，因此直接加入到tail 的後面 """ self.tail.next = ListNode(value) self.tail = self.tail.next self.count+=1 return self.tail def find(self, value): """ 查詢第一個值為 value的幾點，並返回ListNode """ cur = self.head.next while cur and cur.value != value: cur = cur.next return cur def remove(self, node): """ 將某個 ListNode 從連結串列中刪除，需要找到這個節點的 上一個節點，然後將上一個幾點的 next 指向被刪除節點的下一個節點。 """ pre = self.head while pre and pre.next != node: pre = pre.next if pre: pre.next = node.next if node == self.tail: self.tail = pre self.count -= 1 return node else: return None def insertBefore(self, node, value): """ 在指定節點 node 之前插入值為 value 的新節點， 需要找到 node 節點的前一個節點，然後 node 和前一個節點之間插入新節點。 這裡需要處理 node 為 None 的時候，插入到連結串列的最後位置。 """ if node is None: return self.append(value) pre = self.head while pre and pre.next != node: pre = pre.next if pre: newNode = ListNode(value) pre.next,newNode.next = newNode,node self.count+=1 return newNode else: return None def insertAfter(self, node, value): """ 在指定節點 node 之後插入值為 value 的新節點， 這裡需要處理 node 為 None 的時候，插入到連結串列的最前位置。 """ if node is self.tail: return self.append(value) newNode = ListNode(value) newNode.next = self.head.next self.count +=1 if node is None: self.head.next = newNode if self.tail is self.head: self.tail = newNode else: node.next,newNode.next = newNode, node.next if self.tail is node: self.tail = newNode return newNode def count(self): return self.count if __name__ == '__main__': # append l = List() l.append(1) l.append(2) l.append(3) # find v1 = l.find(1) v2 = l.find(2) v3 = l.find(3) print(v1.value) print(v1.value) #remove l.remove(v1) l.remove(v2) #insert before v22 = l.insertBefore(v3, -2) v33 = l.insertBefore(v22, -3) #insert after v4 = l.insertAfter(v3, 4) v5 = l.insertAfter(v4, 5) #count 5 print(len(l)) #遍歷輸出連結串列的各個節點，連結串列的遍歷，衝 head.next 開始 #print list -3, -2, 3, 4, 5 cur = l.head.next while cur: #這裡用來判斷是否是最後一個節點，最後一個節點輸出的時候不需要新增逗號 if cur.next: print "%d,"%(cur.value), else: print cur.value cur = cur.next