## 單向鏈表 單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節點包含兩個域，一個信息域（元素域）和一個鏈接域。這個鏈接指向鏈表中的下一個節點，而最后一個節點的鏈接域則指向一個空值。  * 表元素域elem用來存放具體的數據。 * 鏈接域next用來存放下一個節點的位置（python中的標識） * 變量p指向鏈表的頭節點（首節點）的位置，從p出發能找到表中的任意節點。 ## 節點實現 ~~~ class SingleNode(object): """單鏈表的結點""" def __init__(self,item): # _item存放數據元素 self.item = item # _next是下一個節點的標識 self.next = None ~~~ ## 單鏈表的操作 * is_empty() 鏈表是否為空 * length() 鏈表長度 * travel() 遍歷整個鏈表 * add(item) 鏈表頭部添加元素 * append(item) 鏈表尾部添加元素 * insert(pos, item) 指定位置添加元素 * remove(item) 刪除節點 * search(item) 查找節點是否存在 ## 單鏈表的實現 ~~~ class SingleLinkList(object): """單鏈表""" def __init__(self): self._head = None def is_empty(self): """判斷鏈表是否為空""" return self._head == None def length(self): """鏈表長度""" # cur初始時指向頭節點 cur = self._head count = 0 # 尾節點指向None，當未到達尾部時 while cur != None: count += 1 # 將cur后移一個節點 cur = cur.next return count def travel(self): """遍歷鏈表""" cur = self._head while cur != None: print cur.item, cur = cur.next print "" ~~~ ### 1.頭部添加元素  ~~~ def add(self, item): """頭部添加元素""" # 先創建一個保存item值的節點 node = SingleNode(item) # 將新節點的鏈接域next指向頭節點，即_head指向的位置 node.next = self._head # 將鏈表的頭_head指向新節點 self._head = node ~~~ ### 2.尾部添加元素 ~~~ def append(self, item): """尾部添加元素""" node = SingleNode(item) # 先判斷鏈表是否為空，若是空鏈表，則將_head指向新節點 if self.is_empty(): self._head = node # 若不為空，則找到尾部，將尾節點的next指向新節點 else: cur = self._head while cur.next != None: cur = cur.next cur.next = node ~~~ ### 3.指定位置添加元素  ~~~ def insert(self, pos, item): """指定位置添加元素""" # 若指定位置pos為第一個元素之前，則執行頭部插入 if pos <= 0: self.add(item) # 若指定位置超過鏈表尾部，則執行尾部插入 elif pos > (self.length()-1): self.append(item) # 找到指定位置 else: node = SingleNode(item) count = 0 # pre用來指向指定位置pos的前一個位置pos-1，初始從頭節點開始移動到指定位置 pre = self._head while count < (pos-1): count += 1 pre = pre.next # 先將新節點node的next指向插入位置的節點 node.next = pre.next # 將插入位置的前一個節點的next指向新節點 pre.next = node ~~~ ### 4.刪除節點  ~~~ def remove(self,item): """刪除節點""" cur = self._head pre = None while cur != None: # 找到了指定元素 if cur.item == item: # 如果第一個就是刪除的節點 if not pre: # 將頭指針指向頭節點的后一個節點 self._head = cur.next else: # 將刪除位置前一個節點的next指向刪除位置的后一個節點 pre.next = cur.next break else: # 繼續按鏈表后移節點 pre = cur cur = cur.next ~~~ ### 5.查找節點是否存在 ~~~ def search(self,item): """鏈表查找節點是否存在，并返回True或者False""" cur = self._head while cur != None: if cur.item == item: return True cur = cur.next return False ~~~ ### 6.測試 ~~~ if __name__ == "__main__": ll = SingleLinkList() ll.add(1) ll.add(2) ll.append(3) ll.insert(2, 4) print "length:",ll.length() ll.travel() print ll.search(3) print ll.search(5) ll.remove(1) print "length:",ll.length() ll.travel() ~~~ ## 鏈表與順序表的對比 鏈表失去了順序表隨機讀取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大，但對存儲空間的使用要相對靈活。 鏈表與順序表的各種操作復雜度如下所示： | 操作 | 鏈表 | 順序表訪問元素 | | --- | --- | --- | | 訪問元素 | O(n) | O(1) | | 在頭部插入/刪除 | O(1) | O(n) | | 在尾部插入/刪除 | O(n) | O(1) | | 在中間插入/刪除 | O(n) | O(n) | **注意:** 雖然表面看起來復雜度都是 O(n)，但是鏈表和順序表在插入和刪除時進行的是完全不同的操作。鏈表的主要耗時操作是遍歷查找，刪除和插入操作本身的復雜度是O(1)。順序表查找很快，主要耗時的操作是拷貝覆蓋。因為除了目標元素在尾部的特殊情況，順序表進行插入和刪除時需要對操作點之后的所有元素進行前后移位操作，只能通過拷貝和覆蓋的方法進行。