构建节点类
class Node(object):
def init(self,item):
self.elem=item
self.next=None
构建链表类
class Single_linkList(object):
def __init__(self,node=None): #构造函数,链表头部
self.__head=node
def __str__(self):
return ("您所察看的数据为单向链表，该链表的长度为：%d"%(self.length()))
def is_empty(self):
"""判断链表头部是否指向空"""
return self.__head==None
def length(self):
"""遍历链表，求长度"""
cur=self.__head ### 使用cur表示当前指针
count=0
while cur !=None:
count +=1
cur = cur.next
return count
def travle(self):
"""遍历打印元素"""
cur=self.__head
if self.is_empty():
return "There is nothing"
else:
while cur !=None:
print(cur.elem,end="->")
cur=cur.next
def append(self,item):
"""尾部添加元素"""
"""遍历节点"""
node=Node(item) #构造节点
cur=self.__head
if self.__head==None: #如果连链表为空，则将head 指向 append的元素
self.__head=node
else:
while cur.next != None:
cur = cur.next
cur.next=node
def insert(self,persition,item):
"""向指定位置添加元素"""
node=Node(item) #构造节点
cur=self.__head
count=0
if persition<=0: ### 传入的数值小于0时，认为是在头部插入元素
self.add(item)
elif persition>=self.length():
self.append(item) ### 数值大于链表长度时，在尾部追加元素
else:
while cur != None and count <= persition-2:
count +=1
cur = cur.next
node.next=cur.next
cur.next=node
def add(self,item):
"""向头部添加元素"""
node=Node(item) #构造节点
cur=self.__head
node.next=cur
self.__head=node
def get_item(self,persition):
"""获取指定位置的元素"""
cur=self.__head
count=1
if self.is_empty(): ### 空列表直接返回
return "There is nothing"
elif persition<0:
return self.__head.elem
elif persition>self.length()-1: # 遍历获取最后一个元素
cur=self.__head
while cur.next !=None:
cur=cur.next
return cur.elem
else:
while cur != None and count <=persition:
count +=1
cur = cur.next
return cur.elem
def pop(self):
"""删除尾部元素"""
cur=self.__head
if self.length()<=1: #如果只有一个元素或链表为空，则直接将链表的head指向空
self.__head=None
else:
while cur.next.next != None:
cur = cur.next
cur.next=None
def remove(self,item): ### 移除第一个元素容易出现问题，，主要是将链表的头部指向下一个元素即可
"""移除指定的第一个元素"""
cur=self.__head
per=self.__head
if self.index(item)==0:
self.__head=cur.next
else:
while cur != None:
cur=cur.next
if per.next.elem == item:
per.next=cur.next
return
per=per.next
def pop_n(self,position):
"""移除指定位置的元素"""
cur=self.__head
per=self.__head
count = 1
if position > self.length()-1: ### 位置超出链表元素个数时，移除最后一个元素
position = self.length()-1
if position <= 0: ### 移除首个元素
self.__head=cur.next
return cur.elem
else:
while cur != None:
cur=cur.next
if count == position:
per.next=cur.next
return cur.elem
per=per.next
count += 1
def type(self):
return "This is a single link list"
def clear(self):
"""清除列表的所有元素"""
self.__head=None
def index(self,item):
"""返回元素在链表中的位置"""
cur=self.__head
count=0
while cur.elem !=item:
cur = cur.next
count +=1
return count
