链表的python实现
单链表的实现
#定义单链表节点类class Node(object): def __init__(self,value=None,next=None): self.value = value self.next = next#单链表结构类class LinkedList(object): def __init__(self): #初始化链表的头节点以及链表的长度 self.head = Node() self.length = 0 def __len__(self): #返回链表的长度 return self.length #定义尾插节点方法 def append(self,value): #添加节点，从末尾处添加 node = Node(value) if self.length==0: self.head.next=node self.length += 1 else: curnode = self.head.next while curnode.next!=None: curnode = curnode.next curnode.next=node self.length += 1 #定义链表开始处添加 def start_insert(self,insert_value):#在开始处插入 node = Node(insert_value) if self.length==0: self.head.next = node else: tmp_node=self.head.next self.head.next = node node.next = tmp_node self.length +=1 #定义在链表任意处添加节点 def insert(self,location,value):#在任意位置插入节点 node = Node(value) if self.length==0: self.head.next = node self.length += 1 #插入一个节点，链表长度加1 else: for nd in self.iter_node(): if nd.value == location: tmp_node = nd.next nd.next = node node.next = tmp_node self.length += 1 return True return False #返回False，未找到插入位置 #定义遍历链表方法 def __iter__(self): #遍历链表节点 for node in self.iter_node(): yield node.value def iter_node(self): curnode = self.head.next while curnode.next !=None: yield curnode curnode = curnode.next if curnode.next == None: yield curnode #定义搜索节点方法(按照节点的value搜索) def search(self,value): #搜索节点 index = 1 if self.length==0: #如果长度为0，则表示链表结构中只有一个头节点 return -1 #返回-1，表示不存在该节点 else: for node in self.iter_node(): if node.value == value: return index #搜索到节点的序号 index += 1 return -1 #未搜索到节点 #定义删除节点的方法 def del_node(self,del_value):#删除节点 Flag = False if self.length==0: return Flag else: previous_node = self.head for curnode in self.iter_node(): if curnode.value == del_value: previous_node.next=curnode.next del curnode self.length -= 1 Flag = True else: previous_node = curnode return Flag
双链表的实现
#定义节点类class Node(object): def __init__(self,value=None,prev=None,next=None): self.value = value self.prev = prev self.next = next#定义双链表类class Double_LinkedList(object): def __init__(self):#初始化双链表只有一个头结点，它的前向指针和后向指针都指向自己，长度为0 node = Node() node.prev = node node.next = node self.head = node self.length = 0 def __len__(self): return self.length def headnode(self): #获取第一个节点 return self.head.next def tailnode(self): #获取最后一个节点 return self.head.prev def append(self,value): #添加节点，从末尾添加 node = Node(value) tail_node = self.tailnode() tail_node.next = node node.prev = tail_node node.next = self.head self.head.prev = node self.length += 1 def head_append(self,value): #添加节点，从头添加 node =Node(value) if self.head.next is self.head: node.next = self.head node.prev = self.head self.head.next = node self.head.prev = node else: node.prev = self.head head_node = self.headnode() self.head.next = node head_node.prev = node node.next = head_node self.length += 1 def insert(self,index,value): #在任意位置插入新节点 node = Node(value) i = 1 if self.length<index: raise Exception('out of range') if self.head.next is self.head: self.head.next = node self.head.prev = node node.next = self.head node.prev = self.head self.length += 1 return True else: if index==0: self.head_append(value) return True for cur_node in self.iter_node(): if i == index: next_node = cur_node.next node.prev = cur_node node.next = next_node cur_node.next = node next_node.prev = node self.length += 1 return True i += 1 def del_node(self,index): #删除节点 i=1 for cur_node in self.iter_node(): if i == index: next_node=cur_node.next prev_node=cur_node.prev prev_node.next = next_node next_node.prev = prev_node self.length -= 1 return True i += 1 def iter_node(self): #遍历节点 if self.head.next is self.head: return -1 cur_node = self.head.next while cur_node.next is not self.head: yield cur_node cur_node = cur_node.next yield cur_node def __iter__(self): #遍历节点，输出每个节点的值 for node in self.iter_node(): yield node.value def reverse_iter_node(self):#反向遍历节点 if self.head.prev is self.head: return False cur_node = self.head.prev while cur_node.prev is not self.head: yield cur_node cur_node = cur_node.prev yield cur_node
深碍√TFBOYSˉ_
小鱼儿
ゞ 浴缸里的玫瑰
还没有评论，来说两句吧...