本文转载请联系python与大数据分析公众号。今天终于明白了大学时候想都没想过的链表数据结构。收获不小，还挺好玩的。文末附上链表操作示意图。单向链表（singlelinkedlist）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问从头部开始，顺序读取。单链表是一种链式访问数据结构，它使用一组任意地址的存储单元来存储线性表中的数据元素。链表中的数据由节点表示。每个节点的组成是：元素（数据元素的图像）+指针（表示后续元素的存储位置）。元素是存储数据的存储单元，指针是连接各个节点的地址数据。它的每个节点都包含两个域，一个信息域（元素域）和一个链接域。此链接指向链表中的下一个节点，最后一个节点的链接字段指向空值。isempty(self)链表是否为空length(self)链表的长度travel(self)遍历整个链表add(self,item)向链表头部添加元素append(self,item)向链表尾部添加元素insert(self,item,index)在指定位置添加元素deletebyitem(self,item)根据数据项删除节点deletebyindex(self,index)根据数据项删除节点索引位置search(self,item)根据数据项查找节点是否存在update(self,index,item)暂无实现getitem(self,index)获取索引位置对应的数据项getindex(self,item)获取数据项对应的索引位置代码基本是原创的，经过大量改写returnstr(self.item)classSingleLinkList(object):def__init__(self):self.header=Noneself.currentnum=0defisempty(s精灵):returnsself.header==Nonedeflength(self):returnsself.currentnumdeftravel(self):cur=self.headerwhilecur!=None:print("{}".format(cur.item),end="")cur=cur.nextprint("\r")defadd(self,item):node=Node(item)#新节点的链接指向头节点node.next=self.header#链表的头部指向到新节点self.header=nodeself.currentnum+=1defappend(self,item):tempnode=self.headernode=Node(item)ifself.isempty():self.add(node)else:whiletempnode.next!=None:tempnode=tempnode.nexttempnode.next=nodeself.currentnum+=1definsert(self,item,index):节点=Node(item)tempnode=self.headerifindex>self.currentnum+1orindex<=0:raiseIndexError("{}isnotfindinLinklist".format(index))#指定位置为第一个即在头部插入ifindex==1:self.add(node)elifindex>self.currentnum-1:self.append(node)else:foriinrange(1,index-1):tempnode=tempnode.nextnode.next=tempnode.nexttempnode.next=nodeself.currentnum+=1defdeletebyitem(自我，项目):tempnode=self.headerprenode=Nonewhiletempnode!=None:iftempnode.item==item:iftempnode==self.header:self.header=tempnode.nextelse:prenode.next=tempnode.nextbreakelse:prenode=tempnodetempnode=tempnode.nextdefdeletebyindex(self,index):ifindex>self.currentnumorindex<=0:raiseIndexError("{}isnotfindinLinklist".format(index))i=1tempnode=self.headerprenode=self.headerifindex==1:self.header=tempnode.nextself.currentnum-=1returnwhiletempnode.nextandi
