python单向链表如何实现

python单向链表如何实现

说明

1、每个节点包括两个域、一个信息域(元素域)和一个连接域,该链接指向链接表的下一个节点,最后一个节点的链接指向空值。

2、表要素elem用于存储具体数据。链接域next用于存管下一个节点的位置

变量P指向链表头节点(首节点)的位置,可以从P出发找到表中的任意节点。

实例

classNode(object):
def__init__(self,elem):
"""
:paramelem:表元素域
next:下一结点链接域
cursor(cur):游标
"""
self.elem=elem
#定义next指向空
self.next=None


classSingleLinkList(object):
"""
单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一一个节点,而最后-个节点的链接域则指向一个空值。
表元素域elem用来存放具体的数据。
链接域next用来存放下一个节点的位置(python中的标识)
变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。
"""

def__init__(self,node=None):
self.__head=node#node.elemnode.next

defis_empty(self):
"""链表是否为空"""
returnself.__headisNone

deflength(self):
"""链表长度"""
#cur游标,用来移动遍历节点
cur=self.__head
count=0
whilecurisnotNone:
count+=1
cur=cur.next
#count记录数量
returncount

deftravel(self):
"""遍历整个链表"""
cur=self.__head
whilecurisnotNone:
print(cur.elem,end='')
cur=cur.next

defadd(self,item):
"""链表头部添加元素:头插法"""
node=Node(item)
node.next=self.__head
self.__head=node

defappend(self,item):
"""链表尾部添加元素:尾插法"""
node=Node(item)
#下一结点链接域不为空
ifself.is_empty():
self.__head=node
else:
cur=self.__head
whilecur.nextisnotNone:
cur=cur.next
cur.next=node

definsert(self,pos,item):
"""
pos:pos从0开始
pre:指定节点前一节点,相当于游标
node:插入的指定节点
指定位置添加元素
"""
#ifpos<=0头插法
ifpos<=0:
self.add(item)
#elifpos>(self.length()-1)尾插法
elifpos>(self.length()-1):
self.append(item)
#else插入法
else:
pre=self.__head
count=0
#当循环退出后,pre指向pos-1
whilecount<(pos-1):
count+=1
pre=pre.next
node=Node(item)
node.next=pre.next
pre.next=node

defremove(self,item):
"""删除元素"""
#考虑删除头部、尾部、中间节点
cur=self.__head
pre=None
whilecurisnotNone:
ifcur.elem==item:
#先判断是否是头节点
ifcur==self.__head:
self.__head=cur.next
else:
pre.next=cur.next
break
else:
pre=cur
cur=cur.next

defsearch(self,item):
"""查找节点是否存在"""
#1.创建游标
cur=self.__head
#2.遍历游标
whilecurisnotNone:
#3.cur.elem=item
ifcur.elem==item:
returnTrue
else:
cur=cur.next
returnFalse
if__name__=='__main__':
ll=SingleLinkList()
ll.is_empty()
l1=ll.length()
print(l1)

ll.append(55)
ll.is_empty()
l2=ll.length()
print(l2)

ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
ll.append(5)
#5518234
ll.insert(-1,9)#98552182345
ll.insert(2,100)#98100552182345
ll.travel()

以上就是python单向链表的实现,希望对大家有所帮助。更多Python学习指路:Python基础教程