Python数据结构之单链表详解

2023-09-24 21:43:06 55

#节点类 classNode(): __slots__=['_item','_next']#限定Node实例的属性 def__init__(self,item): self._item=item self._next=None#Node的指针部分默认指向None defgetItem(self): returnself._item defgetNext(self): returnself._next defsetItem(self,newitem): self._item=newitem defsetNext(self,newnext): self._next=newnext #单链表 classSingleLinkedList(): def__init__(self): self._head=None#初始化链表为空始终指向链表的头部 self._size=0#链表大小 #返回链表的大小 defsize(self): current=self._head count=0 whilecurrent!=None: count+=1 current=current.getNext() returncount #遍历链表 deftravel(self): current=self._head whilecurrent!=None: print(current.getItem()) current=current.getNext() #检查链表是否为空 defisEmpty(self): returnself._head==None #在链表前端添加元素 defadd(self,item): temp=Node(item)#创建新的节点 temp.setNext(self._head)#新创建的next指针指向_head self._head=temp#_head指向新创建的指针 #在链表尾部添加元素 defappend(self,item): temp=Node(item) ifself.isEmpty(): self._head=temp#若为空表就直接插入 else: current=self._head whilecurrent.getNext()!=None: current=current.getNext()#遍历列表 current.setNext(temp)#此时current为链表最后的元素，在末尾插入 #检索元素是否在链表中 defsearch(self,item): current=self._head founditem=False whilecurrent!=Noneandnotfounditem: ifcurrent.getItem()==item: founditem=True else: current=current.getNext() returnfounditem #索引元素在表中的位置 defindex(self,item): current=self._head count=0 found=None whilecurrent!=Noneandnotfound: count+=1 ifcurrent.getItem()==item: found=True else: current=current.getNext() iffound: returncount else: return-1#返回-1表示不存在 #删除表中的某项元素 defremove(self,item): current=self._head pre=None whilecurrent!=None: ifcurrent.getItem()==item: ifnotpre: self._head=current.getNext() else: pre.setNext(current.getNext()) break else: pre=current current=current.getNext() #在链表任意位置插入元素 definsert(self,pos,item): ifpos<=1: self.add(item) elifpos>self.size(): self.append(item) else: temp=Node(item) count=1 pre=None current=self._head whilecount

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

Python数据结构之单链表详解

热门推荐

随机推荐