Python代码实现双链表_python_

class Node(object):     def __init__(self, item=None):         #放数据         self.item= item         #指向后一个节点         self.next = None         #指向前一个节点         self.prior =None

#双向链表  从左往右读 class Node(object):         """双向链表节点"""         def __init__(self,item):                 #放数据的节点                 self.elem = item                 #指向后一个节点                 self.next = None                 #指向前一个节点                 self.prev = None #双向链表 class LinkList(object):         def __init__(self,node=None):                 #代表头节点                 self.__head = node         #判断链表是否为空         def is_empty(self):                 return self.__head == None         def length(self):                 """返回链表的长度"""                 #cur游标移动，从而实现遍历元素的功能                 cur = self.__head                 #count用来计数                 count = 0                 while cur != None:                         count += 1                         #让cur游标可以向下移动                         cur = cur.next                 return count         #遍历整个链表         def travel(self):                 if self.is_empty():                         return                 #建立游标等于起始节点                 else:                         cur = self.__head                         while cur != None:                                 print(cur.elem,end=" ")                                 cur = cur.next                         print("")         #头插法         def add(self,item):                 #新节点                 node = Node(item)                 if self.is_empty():                         #头节点指向了新的节点                         self.__head = node                 else:                         #新节点指向原第一个节点                         node.next = self.__head                         self.__head = node                         node.next.prev = node         def append(self,item):                 """链表尾部添加元素"""                 node = Node(item)  #定义新节点                 #链表是否为空链表                 if self.is_empty():                         #如果为空，新的节点加了进去                         self.__head = node                 else:                         #头节点 创建游标                         cur = self.__head   #设置指向头结点的游标  此时的当前链表第一个节点，就是头节点指向的节点                         #cur到最后一个节点停下                         while cur.next != None:                                 cur = cur.next                         #添加节点到尾部 cur道了最后一个结点  cur.next指向了新的节点node  从左往右读                           cur.next = node                         #当前的节点指向它前一个                         node.prev = cur         #插入法  #pos从零开始         def insert(self,pos,item):                 """在指定位置添加元素"""                 #指向不是头部元素，self.__head的地址                 # 为下一个元素，所以pre为下一个元素                 if pos <= 0:                         #认为是头插法                         self.add(item)                 #假如长度是3 pos大于2要特殊处理                   elif pos > (self.length()-1):                         #尾插法                         self.append(item)                 else:                         #创建节点 新节点                         node = Node(item)                         cur = self.__head                         count = 0                         #动起来                         while count < pos:                                 count+=1                                 cur = cur.next                                                 #把节点链接到中间任意位置 插入前一个节点   此时，cur停在后一个节点                         node.next = cur                         node.prev = cur.prev                         cur.prev.next = node                         cur.prev = node         def remove(self,item):                 """删除元素"""                 if self.is_empty():                     return                 cur = self.__head                 #查找所有的位置有没有要删除的，若有则删除                 while cur != None:                         #判断cur指向的数据,是否为要删除的数据   item要删除的元素                         if cur.elem == item:                                 #判断此节点是否为头节点                                 #考虑特殊情况,恰好要删除是第一个元素    当前的元素就是我要删除的元素                                  if cur == self.__head:                                         #如果删除中间,  头节点指向后一个节点                                          self.__head = cur.next                                         #考虑链表只有一个节点  直接指向None                                         if cur.next != None:                                                 #是否只有一个节点                                                 cur.next.prev = None                                 else:                                         #中间节点                                         cur.prev.next = cur.next                                         if cur.next != None:                                                 cur.next.prev = cur.prev                                 break                         else:                                 #没有找到,cur游标向继续往下移动                                 cur = cur.next         def search(self,item):                 """查找结点是否存在"""                 #如果是一个空链表                 if self.is_empty():                         return False                 cur = self.__head                 while cur.next != self.__head:                         #cur数据是否为查找的数据 item是要查的数据                          if cur.elem == item:                                 return True                         else:                                 cur = cur.next                 #遍历完成 cur指向None                 return False if __name__ == '__main__':         ll = LinkList()         #第一次的         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.travel()         ll.insert(-1,50)         ll.travel()         ll.insert(2,60)         ll.travel()         ll.insert(10,300)         ll.travel()         ll.remove(50)         ll.travel()         ll.remove(300)         ll.travel()