尾结点指向头结点为环链表
class node(object):
def __init__(self,item):
self.item = item
self.next = None
class circlechainlist(object):
def __init__(self,length = 10):
self.length = length
self.head = node(None)
self.head.next = self.head
self.count = 0
def __num_node(self,x:int):
self.count += x
def search(self,x:node): # search for the node and return the precvious node
if self.head.next == x:
return self.head
else:
temp = self.head.next
while temp.next != x:
temp = temp.next
return temp
def add_node(self,node:node): # add at the end of chain
if self.count == self.length:
print('cannot exceed max length')
else:
self.find_tail().next = node
node.next = self.head
self.__num_node(1)
def find_tail(self,x=None): # find the last node
if x is None:
x = self.head
if x.next == self.head:
return x
else:
temp = x.next
if temp.next == self.head:
return temp
else:
return self.find_tail(temp)
def del_node(self,x=None):
if self.head.next == self.head:
print('no node any more!')
else:
if x is None:
self.search(self.find_tail()).next=None
self.__num_node(-1)
else:
self.search(x).next = x.next
x = None
self.__num_node(-1)
def insert_node(self,x:node,y:node):
if self.count == self.length:
print('cannot exceed max length')
else:
if self.head.next == self.head:
self.head.next = y
y.next = self.head
self.__num_node(1)
else:
self.search(x).next = y
y.next = x
self.__num_node(1)
def get_chain(self):
chain = [self.head]
while chain[-1].next != self.head:
chain.append(chain[-1].next)
return chain
