单链表
#coding:utf-8
class Node:
def __init__(self,data):#__init构造函数
self.data = data
self.next =None #一个节点的初始状态，不知道这个节点指向哪里，为空
class SingleLinkList:
def __init__(self,node=None):#构造函数
self.__head = node
def is_empty(self):#对象方法，将类实例化
return self.__head ==None
def length1(self):
current =self.__head
length =1
if currentis None:
return 0
else:
while currentis not None:
length +=1
current = current.next
return length -1
def length(self):#不需要除self之外的参数#注意考虑空链表的特殊情况
current =self.__head
length =0
while currentis not None:
current = current.next#address to rear
length +=1
return length
def travel(self):#不需要除self之外的参数
current =self.__head
length =0
while currentis not None:
print(current.data,end=' ')
current = current.next# address to rear
def add(self,newnode):#add data to head,注意先后顺序，先要保留要修改的链表的首节点地址
node = Node(newnode)
current =self.__head#先要保留要修改的链表的首节点地址
self.__head = node#将头节点指向新的节点
node.next = current
def append(self,newnode):#tail to add,newnode is a data
current =self.__head
node = Node(newnode)
if self.is_empty():
self.__head = node
# node.next = None the action of adding data to tail is not needed to do this
else:
while current.nextis not None:#空链表需要特殊处理，None 的next没有值，会出错
current = current.next
current.next = node
# node.next = None
def insert(self,position,newnode):#position是下标
node = Node(newnode)
current =self.__head
i =0
# for i in range(position-1):
# current = current.next
# # d = current.next#插新节点在这个position之后
# # current.next = node
# # node.next = d
# # d = current
# node.next = current.next#注意for循环起始的时候current所知的位置，循环结束后curr的位置，防止循环调用，造成无限输出
# current.next = node
if position <=0:#默认做头插法
self.add(newnode)
elif position >self.length()-1:#默认用尾插法
self.append(newnode)
else:
while i < position-1:
current = current.next
i +=1
node.next = current.next
current.next = node
def remove(self,deletenode):#只删除第一个找到的数
# current = self.__head
# while current.next is not None:
# d = current
# current = current.next
# if current.data == deletenode:
# d.next = current.next
# break
# else:
# continue
# if self.search2(deletenode):
# pre = self.__head
# current = pre.next
# if pre.data == deletenode:
# self.__head = current
# else:
# while current.data != deletenode:
# pre = current
# current = current.next
# pre.next = current.next
# else:print("没有这个点")
current =self.__head
pre =None
# while current.data != deletenode:
# pre = current
# current = current.next
while currentis not None:
if current.data == deletenode:
if current ==self.__head:
self.__head = current.next
else:
pre.next = current.next
break
else:
pre = current
current =current.next
def search1(self, searchnode):#效果只是有没有这个值
node = Node(searchnode)
current =self.__head
while current !=None:
if current.data == node.data:
return True
else:
current = current.next
return False
def search2(self,searchnode):
node = Node(searchnode)
current =self.__head
i =0
while i
if current.data == node.data:
return True
else:
current = current.next
i +=1
else:
return False
def search(self,searchnode):
node = Node(searchnode)
current =self.__head
i =0
ll = []
while i
if current.data != node.data :
current = current.next
i +=1
continue
elif current.data == node.data :
current = current.next
print(i)
ll.append(i)
i +=1
continue
if len(ll) ==0:print("there is not a searchnode")
# if current.next == None:
# print("there is not a searchnode")
# else:
# current = current.next
if __name__ =="__main__":
ll = SingleLinkList()
# print(ll.is_empty())
# print(ll.length())
# print(ll.length1())
# ll.append(1)
# print(ll.is_empty())
# print(ll.length())
# print(ll.length1())
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
ll.add(0)
ll.insert(3,6.5)
ll.insert(-1,9)
ll.insert(100,100)
ll.insert(4,3)
# print(ll.length())
ll.travel()
print("")
ll.search2(300)
# a = ll.search2(9)
# print(a)
ll.remove(9)
ll.travel()
双链表
class Node():
def __init__(self,data):
self.data = data
self.next =None
self.pre =None
class DoubleLinkList():
def __init__(self, node=None):
self.__head = node
def is_empty(self):# 对象方法，将类实例化
return self.__headis None
def length(self):# 不需要除self之外的参数#注意考虑空链表的特殊情况
current =self.__head
length =0
while currentis not None:
current = current.next# address to rear
length +=1
return length
def travel(self):# 不需要除self之外的参数
current =self.__head
length =0
while currentis not None:
print(current.data,end=' ')
current = current.next# address to rear
print("")
def add(self,data):
node = Node(data)
self.__head.pre = node#旧链表需要改变的地方，先向后移动
node.next =self.__head# 将node和旧节点连起来，保护旧的现场，否则无法连起来
self.__head = node# 将node定义为新的首节点
def append(self,data):
node = Node(data)
current =self.__head
if self.is_empty():#注意空链表
self.__head = node
else:
while current.next !=None:
current = current.next
current.next = node
node.pre = current
def insert(self,position,data):
node = Node(data)
current =self.__head
if position <=0:# 默认做头插法
self.add(data)
elif position >self.length() -1:# 默认用尾插法
self.append(data)
else:##注意上来不要改变旧的节点，先将新的node节点P N区做出来，再处理旧的节点关系
i =0
while i < position:
current = current.next
i +=1#循环结束的时候，current指向position的位置
node.pre = current.pre
node.next = current
current.pre.next = node
current.pre = node
def remove(self,deletedata):
current =self.__head
while currentis not None:
if current.data == deletedata:
if current ==self.__head:
self.__head = current.next
if current.next:
current.next.pre =None
else:
current.pre.next = current.next
if current.next:
current.next.pre = current.pre
break
else:
current = current.next
def search2(self, searchnode):
node = Node(searchnode)
current =self.__head
i =0
while i
if current.data == node.data:
return True
else:
current = current.next
i +=1
else:
return False
if __name__=="__main__":
ll = DoubleLinkList()
print(ll.is_empty())
print(ll.length())
ll.append(1)
print(ll.is_empty())
print(ll.length())
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
ll.add(0)
ll.insert(3,6.5)
ll.insert(-1,9)
ll.insert(100,100)
ll.insert(4,3)
print(ll.length())
ll.travel()
print("")
ll.search2(300)
ll.remove(9)
ll.travel()
单向循环列表
class Node:
def __init__(self,data):#__init构造函数
self.data = data
self.next =None
class SinglecircleLinkList:
def __init__(self, node=None):# 构造函数
self.__head = node
if node:
node.next = node
def add(self, newnode):# add data to head,注意先后顺序，先要保留要修改的链表的首节点地址
node = Node(newnode)
current =self.__head# 先要保留要修改的链表的首节点地址
rear =self.__head
if self.is_empty():#空链表
self.__head = node
node.next = node
else:
while rear.nextis not self.__head:
rear = rear.next
rear.next = node
self.__head = node# 将头节点指向新的节点
node.next = current#current 是旧的首节点地址
#空链表
#只有一个节点
def insert(self, position, newnode):# position是下标
node = Node(newnode)
current =self.__head
i =0
if position <=0:# 默认做头插法
self.add(newnode)
elif position >self.length() -1:# 默认用尾插法
self.append(newnode)
else:
while i < position -1:#position是对于用户来说的，用户不了解下标从0 开始
current = current.next
i +=1
node.next = current.next
current.next = node
def append(self, newnode):# tail to add,newnode is a data
current =self.__head
node = Node(newnode)
if self.is_empty():#为空
self.__head = node
node.next = node
else:
while current.nextis not self.__head:
current = current.next
current.next = node
node.next =self.__head##node.next = current.next#只有一个节点
#为空
#只有一个节点
def is_empty(self):# 对象方法，将类实例化
return self.__head ==None
def length(self):# 不需要除self之外的参数#注意考虑空链表的特殊情况
current =self.__head
length =1#注意起始的值必须从1开始
if self.is_empty():#如果为空链表
return 0
while current.nextis not self.__head:#循环列表的游标不存在None,循环结束的标志尾部节点再次指向首节点
current = current.next# address to rear
length +=1
return length
def travel(self):# 不需要除self之外的参数
current =self.__head
if self.__head ==None:
return
while current.nextis not self.__head:#不能用current is not self.head ,首节点直接就退出了
print(current.data,end=' ')
current = current.next# address to rear
print(current.data)#注意最后一个取不到
#特殊情况，空链表|只有一个节点|
def search(self, searchnode):
node = Node(searchnode)
current =self.__head
if self.is_empty():
return False
while current.nextis not self.__head:
if current.data == node.data:
return True
else:
current = current.next
if current.data == node.data:
return True
return False
#最后一个节点没法判断if current.data == node.data:
#空链表if self.is_empty():
#只有一个节点if current.data == node.data:
def remove(self, deletenode):
if self.is_empty():
return
current =self.__head
pre =None
while current.nextis not self.__head:#能狗进入循环体
if current.data == deletenode:
if current ==self.__head:#头节点就是我要删除的
rear =self.__head
while rear.nextis not self.__head:
rear = rear.next
self.__head = current.next
rear.next = current.next
else:#中间节点
pre.next = current.next
return#给返回，整个函数退出
else:#两个游标同时右移
pre = current
current = current.next
#退出循环，实现对尾部节点的操作
if current.data == deletenode :#退出循环，实现对尾部节点的操作
if current ==self.__head:##只有一个节点，也进不了上面的循环
self.__head =None
else:
pre.next = current.next
#如果是头节点的删除,或者尾节点删除需要特殊处理,放在最后pass
#同时尾部的节点被删除也不在循环体里面
#为空
#只有一个节点
if __name__=="__main__":
ll = SinglecircleLinkList()
print(ll.is_empty())
print(ll.length())
ll.append(1)
print(ll.is_empty())
print(ll.length())
ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
ll.insert(-1,9)
ll.travel()
ll.insert(3,100)
ll.travel()
ll.insert(10,200)
ll.travel()
ll.remove(100)
ll.travel()
ll.remove(9)
ll.travel()
ll.remove(200)
ll.travel()
