Python数据结构之链表1.链表基础知识。什么是链表？熟悉python语法的同学一定知道list，但这并不是真正意义上的链表。链表是由一系列节点（节点）实现的，每个节点存储一个指向下一个节点的指针，以实现快速插入。此外，每个节点都有一个包含特定数据的货物。根据链表的结构，其类型可分为单向链表、单项循环链表、双向循环链表、双向循环链表等。2.新建链表由于链表的功能是由节点完成的，所以链表的建立首先要创建节点类。我们通过节点间传值的方式将指针指向下一个节点。下面的代码是链表的创建，下一节将介绍如何遍历链表。节点类：def__init__(self,dataval=None):self.dataval=datavalself.nextval=None类SLinkedList:def__init__(self):self.headval=None)e2=Node("Tue")e3=Node("Wed")#连接第一和第二个节点li.headval.nextval=e2#连接第二和第三个节点e2.nextval=e3print(e2.nextval)#Theresultise3memoryaddress<__main__.Nodeobjectat0x0000001A0F9644BE0>print(e2.nextval.dataval)#result为e3所代表的值Wed3.链表遍历创建链表后，可以进入第一个节点遍历整个链表#在链表的末尾添加一个新节点defappend(self,newdata):NewNode=Node(newdata)ifself.headvalisNone:self.headval=NewNodereturnlaste=self.headvalwhile(laste.nextval):laste=laste.nextvallaste.nextval=NewNode#打印链表defshow(self):printval=self.headvalwhilenotprintval:print(printval.dataval)printval=printval.nextval的resultis:MonTueWedThu4.在链表中插入插入一个元素是指将一个指针从一个已经存在的节点指向一个新插入的节点节点依赖于不同的插入位置，主要有以下几种情况。1.在链表的开头插入在开头插入一个节点，顾名思义，就是把原来的节点变成第二个节点，后面的排列顺序不变。#在开头插入，在链表左边defadd_left(self,newdata):NewNode=Node(newdata)结果：SunMonTueWed2，在链表末尾插入和开头插入类似，需要什么要做的是将原链表末尾的指针指向新的Node，即原来的last指针变成倒数第二个节点，新节点变成最后一个节点。#在路的尽头添加defappend(self,newdata):NewNode=Node(newdata)#判断原链表是否没有节点，如果没有则该节点为首节点self.headval:self.headval=NewNodereturnlaste=self.headval#while执行后，如果一直存在laste.nextval，则遍历到原链表的最后一个while(laste.nextval):laste=laste.nextval#继续后一个节点原来的最后一个节点last.nextval=NewNodeli.append("Thu")li.show()result:MonTueWedThu3.在两个元素之间插入如果想在链表中间插入一个节点，应该怎么办？相信大家在熟悉了前两种插入方式之后，应该能够掌握链表中间的插入了。是的，它们都是一样的。也是在指针上做文章。将要插入位置的前一个指针指向新节点，将新节点指针指向插入位置的下一个节点。classNode:def__init__(self,dataval=None):self.dataval=datavalself.nextval=NoneclassSLinkedList:def__init__(self):self.headval=None#添加节点definsert(self,middle_node,newdata):ifnotmiddle_node:print("Thementionednodeisabsent")returnNewNode=Node(newdata)NewNode.nextval=middle_node.nextvalmiddle_node.nextval=NewNode#printlistdeflistprint(self):printval=self.headval而printval不是无：print(printval.dataval)printval=printval.nextvalli=SLinkedList()li.headval=Node("Mon")e2=Node("Tue")e3=Node("Thu")li.headval.nextval=e2e2.nextval=e3li.insert(list.headval.nextval,"Fri")li.show()结果：MonTueFriThu5.删除链表元素添加完之后，接下来就是删除了。节点类：def__init__(self,data=None):self.data=dataself.next=NoneNewNode.next=self.headself.head=NewNode#删除节点defremove(self,Removekey):HeadVal=self.headifnotHeadVal:if(HeadVal.data==Removekey):self.head=HeadVal.nextHeadVal=Nonereturn而不是HeadVal:ifHeadVal.data==Removekey:breakprev=HeadValHeadVal=HeadVal.nextif(HeadVal==None):returnprev.next=HeadVal.nextHeadVal=Nonedefshow(self):printval=self.headwhile(printval):print(printval.data),printval=printval.nextli=SLinkedList()li.add_left("Mon")li.add_left("Tue")li.add_left("Wed")li.add_left("Thu")li.add_left("Tue")li.show()结果：ThuWedMon参考：tutorialspoint
