鏈表（python）
一、鏈表和數組
在編寫程式碼中，我們儲存的數據是存儲於記憶體當中，記憶體就像一塊塊並列排序的小方盒，每個小方盒都有自己地址，我們儲存的數據就在這樣一個個小方盒當中。
這些數據存放的結構有兩種基本方式，數組和鏈表。
1，數組
數組在記憶體中是按順序，記憶體地址來存儲的，就好似上圖的抽屜，從上到下，按順序存放物品。這一特徵也就意味著數據在記憶體中是相連的，緊緊不分開的，小的記憶體空間可能會裝不下較多的數據，造成了記憶體空間浪費。
世界上許多事情有好有壞，有利有弊，數組也是如此，數據在記憶體中緊密相連，也就意味著牽一髮而動全身，比如你想在數組中添加一項數據，這就好比一排已經排好隊的士兵，每個人都有自己的編號，而此時你突然要插入其中。
你：「兄弟方便讓個位置嗎？」
你後面的士兵都一臉凶神惡煞地看著你，如果不是排長強力要求你插入其中，他們肯定不會讓你入隊，因為你的入隊，讓你身後的士兵的編號都要往後挪。
數組也是一樣，當新加入一個數據時，這就意味著它後面的數據記憶體地址都要往後稍一稍，刪除亦如此。
2，鏈表 和賦值原理
鏈表和在記憶體中排列整齊的數組不同，它們像一堆散兵游勇，散佈於記憶體中，只要哪裡有空隙就往哪裡鑽，鏈表高效地運用了記憶體空間。雖然它們看起來雜亂無章，但其實它們井然有序，暗號讓它們緊緊相連。數據與數據之間有一條「暗號」的鏈子相連接，那個數據在首位，那個數據在第二位……在末尾都非常清楚。
這種「暗號」其實就是記憶體地址，如下圖，長方形就是節點，一個節點包含了兩個方面的內容，數據和「暗號」，這個「暗號」其實就是下一個節點的引用資訊。
鏈表的第一個和最後一個節點最重要和最特殊，最後一個節點則意味著後面沒有數據了，所以它指向None,第一個節點的記憶體地址需要一個地方來保存，所以設立一個head屬性對第一個節點應用。
下面來實現節點程式碼,一個節點需要存放數據和對下一個數據的引用：
class Node:
def __init__(self,x):
self.data = initdata #存放數據
self.next = None #對下一個節點的引用
def getData(self): #返回數據
return self.data
def getNext(self): #返回下一個節點
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
相信很多人都有疑問，為什麼把下一個節點賦給上一個節點的next就實現了記憶體的引用呢？這與Python的特性有關，Python沒有專門的指針，所有變數即是指針。
舉一個例子，a = 6,一個簡單的賦值，它在記憶體中是怎樣實現的呢？
首先在記憶體中會創建數據6，數據6在記憶體中有自己的記憶體地址，然後再把變數標籤a指向6，如上圖a這個長方形中，實際是數據6的記憶體地址。再比如，a,b = b,a, 這實際就是a指向原來b指向的地址，b指向原來a指向的地址。明白了記憶體中賦值的原理，那麼對Python鏈表中，next = 下一個節點，就會很清晰了，next指向下一個節點的記憶體地址。
三，單鏈表的實現
1，鏈表的優點和缺點
鏈表插入和刪除數據非常快，但讀取數據非常慢
| 數組 | 鏈表 | |
| 讀取 | O(1) | O(N) |
| 插入 | O(N) | O(1) |
| 刪除 | O(N) | O(1) |
數組的讀取非常快，因為它在記憶體中連續存儲，插入和刪除慢，是因為插入和刪除都要改變相應的記憶體地址。
鏈表的插入和刪除都很快，因為只要相應的改變節點中next的指向即可，鏈表訪問一個特定數據時，必須沿著鏈表一個一個數據訪問，所以讀取很慢、
2，鏈表的方法
from node import Node class UnorderedList: def __init__(self): self.head = None def add(self,item): #添加數據 temp = Node(item) temp.setNext(self.head) #next指向表頭，head為引用表頭的資訊 self.head = temp #在把head指向新增加的節點 def size(self): #返回鏈表的size current =self.head count = 0 while current != None: count +=1 current = current.getNext() return count def search(self,item): #數據是否在鏈表中 current = self.head found = False while current != None and not found: if current.getData() == item: found = True else: current = current.getNext() return found def remove(self): #刪除某個數據 current = self.head previous = None found = False while not found: if current.getData == item: found = True else: previous = current current = current.getNext() if previous == None: self.head = current.getNext() else:
previous.setNext(current.getNext())
