python3数据结构链表

python使用链表

单链表&＃xff1a;

import gc #垃圾回收
class ListNode: #结点类def __init__(self, x):self.val &＃61; xself.next &＃61; Noneclass LinkedList: #链表类def __init__(self):self.__head &＃61; ListNode(None) #初始化建立头节点self.__num &＃61; 0self.end &＃61; self.__head #建立尾节点def __len__(self):return self.__num#加节点操作(单个)def addNode(self,x):x &＃61; ListNode(x)self.end.next &＃61; xself.end &＃61; xself.end.next &＃61; Noneself.__num &＃43;&＃61; 1#加节点操作&＃xff08;多个&＃xff09;def addList(self,l:list):for x in l:x &＃61; ListNode(x)self.end.next &＃61; xself.end &＃61; xself.end.next &＃61; Noneself.__num &＃43;&＃61; len(l)#删除节点操作&＃xff0c;可按值删除&＃xff0c;可按索引删除def deleteNode(self,x,op&＃61;&＃39;val&＃39;):assert op &＃61;&＃61;&＃39;val&＃39; or op&＃61;&＃61;&＃39;index&＃39; #op必须为val或者indexhead &＃61; self.__head.nextpreNode &＃61; self.__head #删除操作必须要一前一后两个指针变量if head &＃61;&＃61; None:print(&＃39;empty List!&＃39;)if op &＃61;&＃61;&＃39;val&＃39;:while head!&＃61; None:if head.val &＃61;&＃61; x:preNode.next &＃61; head.nexthead.next &＃61; Nonedel headgc.collect()head &＃61; preNode.nextself.__num -&＃61;1else:head &＃61; head.nextpreNode &＃61; preNode.nextif op &＃61;&＃61;&＃39;index&＃39;:if isinstance(x,list):x.sort(reverse&＃61;True) #从大到小排序&＃xff0c;先删除链表靠后的节点就不会影响index的次序for index in x:for i in range(index):head &＃61; head.nextpreNode &＃61; preNode.nextpreNode.next &＃61; head.nexthead.next &＃61; Nonedel headgc.collect()self.__num -&＃61; 1head &＃61; self.__head.nextpreNode &＃61; self.__headelse:for i in range(x):head &＃61; head.nextpreNode &＃61; preNode.nextpreNode.next &＃61; head.nexthead.next &＃61; Nonedel head #删除head指针变量指向的结点gc.collect() #删除的内容马上释放self.__num -&＃61; 1def modifyByVal(self,old,new):head &＃61; self.__head.nextwhile head !&＃61;None:if head.val &＃61;&＃61; old:head.val &＃61; newhead &＃61; head.nextdef modifyByIndex(self,indexes,val):assert isinstance(indexes,list)head &＃61; self.__head.nextfor index in indexes:for i in range(index):head &＃61; head.nexthead.val &＃61; valhead &＃61; self.__head.nextdef showList(self):result &＃61; []if self.__num &＃61;&＃61; 0:print(&＃39;empty List!&＃39;)return Noneelse:head &＃61; self.__head.nextwhile head !&＃61; None:result.append(head.val)head &＃61; head.nextprint(result)def getList(self)->ListNode:return self.__headif __name__ &＃61;&＃61; &＃39;__main__&＃39;:l &＃61; LinkedList()l.addList([7,4,5,4,1,2])l.showList()l.deleteNode(4,op&＃61;&＃39;val&＃39;)l.showList()l.modifyByIndex([2,0],0)l.showList()