https://cloud.tencent.com/developer/article/1454690
侯哥的Python分享
# 創建節點
class Node(object):def __init__(self,item):self.element = itemself.next = None# 創建單鏈表類
class SingleLinkList(object):def __init__(self):self.header = Noneself.length = 0# 1、判斷是否為空def is_empty(self):if self.header == None:return Trueelse:return False# 2、頭部插入def add(self,node):if self.is_empty():self.header = nodeelse:node.next = self.headerself.header = node# currentNode = self.headerself.length += 1# 3、尾部插入def appent(self,node):currentNode = self.headerif self.is_empty():self.add(node)else:while (currentNode.next != None):currentNode = currentNode.nextcurrentNode.next = nodeself.length += 1# 4、指定位置插入def insert(self,node,index):currentNode = self.headerif index>self.length+1 or index<=0:print("你要插入的位置不對,請重現選擇位置")if index == 1:self.add(node)elif index == 2:node.next = self.header.nextself.header.next = nodeself.length += 1else:for i in range(1,index-1):currentNode = currentNode.nextnode.next = currentNode.nextcurrentNode.next = nodeself.length += 1# 5、遍歷def travel(self):currentNode = self.headerif self.length == 0:print("你要遍歷的鏈表沒有數據\n")else:print("你要遍歷的鏈表里面的元素有:",end=" ")for i in range(self.length):print("%s "%currentNode.element,end=" ")currentNode = currentNode.nextprint("\n")# 6、排序不用交換節點的位置,只需要交換節點上的數據值def list_sort(self):for i in range(0,self.length-1):currentNode = self.headerfor j in range(0,self.length-i-1):if currentNode.element > currentNode.next.element:temp = currentNode.elementcurrentNode.element = currentNode.next.elementcurrentNode.next.element = tempcurrentNode = currentNode.next# 7、按索引刪除def remove(self,index):if index<=0 or index>self.length:print("你輸入的下標不對,請重新輸入")returnelse:if index == 1:self.header = self.header.nextcurrentNode = self.headerelif index == 2:currentNode = self.headercurrentNode.next = currentNode.next.nextelse:currentNode = self.headerfor i in range(1,index-1):currentNode = currentNode.nextcurrentNode.next = currentNode.next.nextself.length -= 1# 8、查找是否包含,并返回下標def isContain(self,num):contain = 0currentNode = self.headerfor i in range(self.length):if currentNode.element == num:print("%d在鏈表中%d處\n"%(num,i))contain = 1currentNode = currentNode.nextif contain == 0:print("%d不在鏈表中\n"%num)# 9、根據下標找節點def searchNodeByIndex(self,index):currentNode = self.headerif index<=0 or index>self.length:print("你輸入的下標不對,請重新輸入\n")return 0else:for i in range(index-1):currentNode = currentNode.nextreturn currentNode# 10、根據下標修改節點的值def modifyByIndex(self,index,num):currentNode = self.headerif index<=0 or index>self.length:print("你輸入的下標不對,請重新輸入\n")else:for i in range(index-1):currentNode = currentNode.nextcurrentNode.element = numdef main():# 創建一個節點對象node1 = Node(1)# 創建一個單鏈表對象single_link_list = SingleLinkList()print("驗證空鏈表的遍歷")single_link_list.travel()print("驗證頭插")single_link_list.add(node1)single_link_list.travel()print("驗證尾插")node2 = Node(2)single_link_list.appent(node2)single_link_list.travel()print("驗證按位置插入")node3 = Node(3)single_link_list.insert(node3,1)single_link_list.travel()print("繼續驗證頭插")node4 = Node(5)single_link_list.add(node4)single_link_list.travel()print("繼續驗證按位置插入")node5 = Node(4)single_link_list.insert(node5,4)single_link_list.travel()print("驗證刪除")single_link_list.remove(3)single_link_list.travel()print("驗證查找一個節點是否在鏈表中")single_link_list.isContain(8)print("驗證按下標查找節點")node = single_link_list.searchNodeByIndex(2)print("第二個節點的值為:%s"%node.element)print("\n驗證排序")single_link_list.list_sort()single_link_list.travel()print("驗證修改")single_link_list.modifyByIndex(2,10)single_link_list.travel()if __name__ == '__main__':main()驗證空鏈表的遍歷
你要遍歷的鏈表沒有數據驗證頭插
你要遍歷的鏈表里面的元素有: 1 驗證尾插
你要遍歷的鏈表里面的元素有: 1 2 驗證按位置插入
你要遍歷的鏈表里面的元素有: 3 1 2 繼續驗證頭插
你要遍歷的鏈表里面的元素有: 5 3 1 2 繼續驗證按位置插入
你要遍歷的鏈表里面的元素有: 5 3 1 4 2 驗證刪除
你要遍歷的鏈表里面的元素有: 5 3 4 2 驗證查找一個節點是否在鏈表中
8不在鏈表中驗證按下標查找節點
第二個節點的值為:3驗證排序
你要遍歷的鏈表里面的元素有: 2 3 4 5 驗證修改
你要遍歷的鏈表里面的元素有: 2 10 4 5
https://cloud.tencent.com/developer/article/1454690
=========================================
優化說明:
1. 時間復雜度改進:
o 原append方法需要遍歷整個鏈表,時間復雜度為O(n)
o 優化后append方法直接通過tail操作,時間復雜度降為O(1)
2. 空間復雜度:
o 只增加了一個tail指針,空間復雜度仍為O(1)
3. 邊界情況處理:
o 空鏈表時tail為None
o 只有一個結點時header和tail指向同一個結點
o 刪除尾結點時需要更新tail
4. 其他優勢:
o 新增get_tail()方法可以直接獲取尾結點
o 在需要頻繁操作鏈表尾部時性能顯著提升
這種優化特別適合需要頻繁在鏈表尾部進行操作的應用場景,如實現隊列等數據結構。
# 創建節點
class Node(object):def __init__(self,item):self.element = itemself.next = None# 創建單鏈表類
class SingleLinkList(object):def __init__(self):self.header = Noneself.tail = None # 新增尾結點引用self.length = 0# 1、判斷是否為空 def is_empty(self):return self.header is None# 2、頭部插入 def add(self, node):if self.is_empty():self.header = nodeself.tail = node # 鏈表為空時,頭尾都指向新節點else:node.next = self.headerself.header = nodeself.length += 1# 3、尾部插入def append(self, node): # 修正了原方法名拼寫錯誤(appent->append)if self.is_empty():self.add(node)else:self.tail.next = node # 直接通過tail添加self.tail = node # 更新tailself.length += 1# 4、指定位置插入 def insert(self, node, index):if index > self.length + 1 or index <= 0:print("插入位置無效")returnif index == 1:self.add(node)elif index == self.length + 1: # 尾部插入情況self.append(node)else:currentNode = self.headerfor _ in range(1, index-1):currentNode = currentNode.nextnode.next = currentNode.nextcurrentNode.next = nodeself.length += 1# 、按索引刪除 def remove(self, index):if index <= 0 or index > self.length:print("刪除位置無效")returnif index == 1:self.header = self.header.nextif self.length == 1: # 如果刪除后鏈表為空self.tail = Noneelse:currentNode = self.headerfor _ in range(1, index-1):currentNode = currentNode.nextcurrentNode.next = currentNode.next.nextif index == self.length: # 如果刪除的是尾結點self.tail = currentNodeself.length -= 1# 5、遍歷def travel(self):currentNode = self.headerif self.length == 0:print("鏈表為空")else:print("鏈表元素:", end=" ")for _ in range(self.length):print(currentNode.element, end=" ")currentNode = currentNode.nextprint()def get_tail(self):return self.tail # 新增方法,直接返回尾結點# 6、排序不用交換節點的位置,只需要交換節點上的數據值def list_sort(self):for i in range(0,self.length-1):currentNode = self.headerfor j in range(0,self.length-i-1):if currentNode.element > currentNode.next.element:temp = currentNode.elementcurrentNode.element = currentNode.next.elementcurrentNode.next.element = tempcurrentNode = currentNode.next# 8、查找是否包含,并返回下標def isContain(self,num):contain = 0currentNode = self.headerfor i in range(self.length):if currentNode.element == num:print("%d在鏈表中%d處\n"%(num,i))contain = 1currentNode = currentNode.nextif contain == 0:print("%d不在鏈表中\n"%num)# 9、根據下標找節點def searchNodeByIndex(self,index):currentNode = self.headerif index<=0 or index>self.length:print("你輸入的下標不對,請重新輸入\n")return 0else:for i in range(index-1):currentNode = currentNode.nextreturn currentNode# 10、根據下標修改節點的值def modifyByIndex(self,index,num):currentNode = self.headerif index<=0 or index>self.length:print("你輸入的下標不對,請重新輸入\n")else:for i in range(index-1):currentNode = currentNode.nextcurrentNode.element = numif __name__ == '__main__':lst = SingleLinkList()print("空鏈表尾結點:", lst.get_tail())lst.add(Node(1))print("添加1后尾結點:", lst.get_tail().element)lst.append(Node(2))print("追加2后尾結點:", lst.get_tail().element)lst.insert(Node(3), 3) # 在末尾插入print("插入3后尾結點:", lst.get_tail().element)lst.remove(3) # 刪除尾結點print("刪除尾結點后新尾結點:", lst.get_tail().element)空鏈表尾結點: None
添加1后尾結點: 1
追加2后尾結點: 2
插入3后尾結點: 3
刪除尾結點后新尾結點: 2開啟新對話
單循環鏈表
class LNode:def __init__(self, elem, next_=None):self.elem = elemself.next = next_class LinkedListUnderflow(Exception):passclass LCList:def __init__(self):self._rear = Nonedef is_empty(self):return self._rear is Nonedef prepend(self, elem):p = LNode(elem)if self._rear is None:p.next = p self._rear = pelse:p.next = self._rear.nextself._rear.next = p # Fixed typo: changed 'P' to 'p'def append(self, elem):self.prepend(elem)self._rear = self._rear.nextdef pop(self):if self._rear is None:raise LinkedListUnderflow("in pop of CLList")p = self._rear.nextif self._rear is p:self._rear = Noneelse:self._rear.next = p.nextreturn p.elemdef printall(self):if self.is_empty():returnp = self._rear.nextwhile True:print(p.elem, end='')if p is self._rear:breakp = p.nextprint(', ', end='')print()if __name__ == '__main__':# Create a new circular linked listclist = LCList()# Test is_empty on new listprint("Is empty?", clist.is_empty()) # Should print True# Append some elementsclist.append(1)clist.append(2)clist.append(3)# Prepend an elementclist.prepend(0)# Print all elementsprint("List elements:")clist.printall() # Should print 0, 1, 2, 3# Test popprint("Popped:", clist.pop()) # Should pop 0print("After pop:")clist.printall() # Should print 1, 2, 3# Pop remaining elementsprint("Popped:", clist.pop())print("Popped:", clist.pop())print("Popped:", clist.pop())# Test empty listprint("Is empty?", clist.is_empty()) # Should print Truetry:clist.pop()except LinkedListUnderflow as e:print("Error:", e) # Should catch the underflow error
=========================================
Is empty? True
List elements:
0, 1, 2, 3
Popped: 0
After pop:
1, 2, 3
Popped: 1
Popped: 2
Popped: 3
Is empty? True
Error: in pop of CLList雙循環鏈表:
class LNode:def __init__(self, elem, next_=None):self.elem = elemself.next = next_class LinkedListUnderflow(Exception):passclass DLNode(LNode):def __init__(self, elem, prev=None, next_=None):super().__init__(elem, next_)self.prev = prevclass LList1:def __init__(self):self._head = Noneself._rear = Nonedef is_empty(self):return self._head is Nonedef prepend(self, elem):pass # To be overridden by DLListdef append(self, elem):pass # To be overridden by DLListdef pop(self):pass # To be overridden by DLListdef printall(self):p = self._headwhile p is not None:print(p.elem, end='')if p.next is not None:print(', ', end='')p = p.nextprint()class DLList(LList1):def __init__(self):super().__init__()def prepend(self, elem):p = DLNode(elem, None, self._head)if self._head is None:self._rear = pelse:self._head.prev = pself._head = pdef append(self, elem):p = DLNode(elem, self._rear, None)if self._head is None:self._head = pelse:self._rear.next = pself._rear = pdef pop(self):if self._head is None:raise LinkedListUnderflow("in pop of DLList")e = self._rear.elemself._rear = self._rear.previf self._rear is None:self._head = Noneelse:self._rear.next = Nonereturn edef pop_first(self):if self._head is None:raise LinkedListUnderflow("in pop_first of DLList")e = self._head.elemself._head = self._head.nextif self._head is None:self._rear = Noneelse:self._head.prev = Nonereturn edef printall_reverse(self):p = self._rearwhile p is not None:print(p.elem, end='')if p.prev is not None:print(', ', end='')p = p.prevprint()if __name__ == '__main__':# Create a new doubly linked listdlist = DLList()# Test is_empty on new listprint("Is empty?", dlist.is_empty()) # Should print True# Append some elementsdlist.append(1)dlist.append(2)dlist.append(3)# Prepend an elementdlist.prepend(0)# Print all elements forwardprint("List elements (forward):")dlist.printall() # Should print 0, 1, 2, 3# Print all elements in reverseprint("List elements (reverse):")dlist.printall_reverse() # Should print 3, 2, 1, 0# Test pop (removes from end)print("Popped from end:", dlist.pop()) # Should pop 3print("After pop from end:")dlist.printall() # Should print 0, 1, 2# Test pop_first (removes from front)print("Popped from front:", dlist.pop_first()) # Should pop 0print("After pop from front:")dlist.printall() # Should print 1, 2# Pop remaining elementsprint("Popped from end:", dlist.pop())print("Popped from end:", dlist.pop())# Test empty listprint("Is empty?", dlist.is_empty()) # Should print Truetry:dlist.pop()except LinkedListUnderflow as e:print("Error:", e) # Should catch the underflow error=============================================
Is empty? True
List elements (forward):
0, 1, 2, 3
List elements (reverse):
3, 2, 1, 0
Popped from end: 3
After pop from end:
0, 1, 2
Popped from front: 0
After pop from front:
1, 2
Popped from end: 2
Popped from end: 1
Is empty? True
Error: in pop of DLList
雙循環的反轉與冒泡排序
class DLNode:def __init__(self, elem, prev=None, next_=None):self.elem = elemself.prev = prevself.next = next_class DLList:def __init__(self):self._head = Noneself._rear = Nonedef is_empty(self):return self._head is Nonedef prepend(self, elem):p = DLNode(elem, None, self._head)if self._head is None:self._rear = pp.next = pp.prev = pelse:p.next = self._headp.prev = self._rearself._head.prev = pself._rear.next = pself._head = pdef append(self, elem):p = DLNode(elem, self._rear, None)if self._head is None:self._head = pp.next = pp.prev = pelse:p.prev = self._rearp.next = self._headself._rear.next = pself._head.prev = pself._rear = pdef reverse(self):if self.is_empty() or self._head is self._rear:returncurrent = self._headwhile True:# 交換prev和next指針current.prev, current.next = current.next, current.prevcurrent = current.prev # 移動到下一個節點if current is self._head: # 循環結束條件break# 交換頭尾指針self._head, self._rear = self._rear, self._headdef sort(self):if self.is_empty() or self._head is self._rear:returnswapped = Truestart = self._headwhile swapped:swapped = Falsecurrent = startwhile True:next_node = current.nextif next_node is start: # 循環結束條件breakif current.elem > next_node.elem:# 交換數據current.elem, next_node.elem = next_node.elem, current.elemswapped = Truecurrent = next_nodedef print_forward(self):if self.is_empty():print("Empty list")returncurrent = self._headwhile True:print(current.elem, end=" ")current = current.nextif current is self._head:breakprint()def print_backward(self):if self.is_empty():print("Empty list")returncurrent = self._rearwhile True:print(current.elem, end=" ")current = current.previf current is self._rear:breakprint()# 測試代碼
if __name__ == "__main__":dll = DLList()dll.append(3)dll.append(1)dll.append(4)dll.append(2)print("Original list (forward):")dll.print_forward() # 3 1 4 2print("\nReversed list (forward):")dll.reverse()dll.print_forward() # 2 4 1 3print("\nSorted list:")dll.sort()dll.print_forward() # 1 2 3 4print("\nBackward traversal:")dll.print_backward() # 4 3 2 1if current.elem > next_node.elem:# 交換數據current.elem, next_node.elem = next_node.elem, current.elemswapped = Truecurrent = next_nodedef print_forward(self):if self.is_empty():print("Empty list")returncurrent = self._headwhile True:print(current.elem, end=" ")current = current.nextif current is self._head:breakprint()def print_backward(self):if self.is_empty():print("Empty list")returncurrent = self._rearwhile True:print(current.elem, end=" ")current = current.previf current is self._rear:breakprint()# 測試代碼
if __name__ == "__main__":dll = DLList()dll.append(3)dll.append(1)dll.append(4)dll.append(2)print("Original list (forward):")dll.print_forward() # 3 1 4 2print("\nReversed list (forward):")dll.reverse()dll.print_forward() # 2 4 1 3print("\nSorted list:")dll.sort()dll.print_forward() # 1 2 3 4print("\nBackward traversal:")dll.print_backward() # 4 3 2 1
Original list (forward):
3 1 4 2 Reversed list (forward):
2 4 1 3 Sorted list:
1 2 3 4 Backward traversal:
4 3 2 1