鏈表：由一系列不必再記憶體中相連的結構組成，每一個結構均含有表元素和指向後繼結構的指針。 與數組、列表的主要區別： 記憶體不連續； 不能通過下標隨機訪問。 優點： 插入、刪除操作效率高，時間複雜度為o(1)； 記憶體利用率高，不會浪費記憶體； 大小不固定，擴展靈活； 缺點： 隨機訪問性差，查找效率低，時間復 ...
鏈表：由一系列不必再記憶體中相連的結構組成，每一個結構均含有表元素和指向後繼結構的指針。
與數組、列表的主要區別：
- 記憶體不連續；
- 不能通過下標隨機訪問。
優點：
- 插入、刪除操作效率高，時間複雜度為o(1)；
- 記憶體利用率高，不會浪費記憶體；
- 大小不固定，擴展靈活；
缺點：
- 隨機訪問性差，查找效率低，時間複雜度為o(n)；
實現一個鏈表：
1 class Node(object): 2 """定義鏈表元素類""" 3 def __init__(self, value=None, next=None): 4 self.value = value 5 self.next = next 6 7 8 class SingleLinkList(object): 9 def __init__(self): 10 self.head = Node() # 頭節點沒有數據，僅作為鏈表訪問的起點 11 self.tail = self.head 12 self.length = 0 13 14 def append(self, value): 15 node = Node(value) 16 self.tail.next = node 17 self.tail = node 18 self.length += 1 19 20 def appendleft(self, value): 21 """將節點插入到head後面""" 22 node = Node(value) 23 if self.head.next is not None: # 判斷鏈表是否插入過元素 24 firstnode = self.head.next 25 node.next = firstnode 26 self.head.next = node 27 else: 28 self.head.next = node 29 self.tail = node 30 self.length += 1 31 32 def iter_node(self): 33 """構造生成器用於遍歷鏈表節點""" 34 curnode = self.head.next 35 while curnode is not self.tail: 36 yield curnode 37 curnode = curnode.next 38 yield curnode 39 40 def __iter__(self): 41 """通過生成器，使鏈表可被for迴圈遍歷""" 42 for node in self.iter_node(): 43 yield node.value 44 45 def __len__(self): 46 return self.length 47 48 def remove(self, value): 49 for curnode in self.iter_node(): 50 if curnode.next is not None and curnode.next.value == value: 51 node = curnode.next 52 curnode.next = node.next 53 del node 54 self.length -= 1 55 return 0 # 刪除成功 56 return -1 # 刪除失敗 57 58 def popleft(self): 59 """刪除鏈表第一個節點""" 60 if self.length > 0: 61 node = self.head.next 62 self.head.next = node.next 63 self.length -= 1 64 return node.value 65 else: 66 raise Exception('LinkList is empty')
以上代碼定義了一個單鏈表類，並實現了常用的添加、刪除鏈表元素的方法。
雙端鏈表：單鏈表無法滿足有些倒敘遍歷鏈表的需求，因此需要雙端鏈表。雙端鏈表的實現只需要在單鏈表的基礎上增加一個指向前一節點的指針即可，卻極大的簡化了某些針對節點的操作，如刪除某節點的時間複雜度直接變為o(1)。
迴圈雙端鏈表：將雙端鏈表的頭節點與尾節點鏈接起來，就是迴圈雙端鏈表。
代碼實現：
1 class Node(object): 2 def __init__(self, value=None, next=None, prev=None): 3 self.value, self.next, self.prev = value, next, prev 4 5 6 class CircularDoubleLinkList(object): 7 def __init__(self): 8 self.head = Node() # 頭節點沒有數據，僅作為鏈表訪問的起點 9 self.tail = self.head 10 self.length = 0 11 12 def append(self, value): 13 node = Node(value, self.head, self.tail) 14 self.tail.next = node 15 self.head.prev = node 16 self.tail = node 17 self.length += 1 18 19 def appendleft(self, value): 20 node = Node(value) 21 if self.head.next is not None: 22 nextnode = self.head.next 23 node.next = nextnode 24 node.prev = self.head 25 nextnode.prev = node 26 self.head.next = node 27 else: 28 node.prev = self.head 29 node.next = self.head 30 self.head.next = node 31 self.head.prev = node 32 self.tail = node 33 self.length += 1 34 35 def iter_node(self): 36 """構造生成器用於遍歷鏈表節點""" 37 curnode = self.head.next 38 while curnode is not self.tail: 39 yield curnode 40 curnode = curnode.next 41 yield curnode 42 43 def __iter__(self): 44 """通過生成器，使鏈表可被for迴圈遍歷""" 45 for node in self.iter_node(): 46 yield node.value 47 48 def __len__(self): 49 return self.length 50 51 def remove(self, node): 52 """註意參數是node""" 53 prevnode = node.prev 54 nextnode = node.next 55 if node is self.tail: 56 self.tail = prevnode 57 prevnode.next = nextnode 58 nextnode.prev = prevnode 59 self.length -= 1 60 61 def iter_node_reverse(self): 62 curnode = self.tail 63 while curnode is not self.head: 64 yield curnode 65 curnode = curnode.prev
