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