# -*- coding:utf-8 -*-#!python3#鏈表的節點class Node(object): def __init__(self , item ):  self.item = item #節點數值  self.prev = None #用于指向前一個元素  self.next = None #用于指向后一個元素#雙向循環鏈表class DoubleCircleLinkList(object): def __init__(self):  self.__head = None #初始化的時候頭節點設為空、 #判斷鏈表是否為空，head為None 的話則鏈表是空的 def is_empty(self):  return self.__head is None #頭部添加元素的方法 def add(self,item):  node = Node(item) #新建一個節點node 里面的值是item  # 如果鏈表是空的，則node的next和prev都指向自己(因為是雙向循環)，head指向node  if self.is_empty():   self.__head = node   node.next = node   node.prev = node  # 否則鏈表不空  else:   node.next = self.__head #node的next設為現在的head   node.prev = self.__head.prev #node的prev 設為現在head的prev   self.__head.prev.next = node #現在head的前一個元素的next設為node   self.__head.prev = node #現在head的前驅 改為node   self.__head = node #更改頭部指針 #尾部添加元素方法 def append(self , item):  #如果當前鏈表是空的 那就調用頭部插入方法  if self.is_empty():   self.add(item)  #否則鏈表不為空  else :   node = Node(item) #新建一個節點node   #因為是雙向循環鏈表，所以head的prev其實就是鏈表的尾部   node.next = self.__head #node的下一個設為頭   node.prev = self.__head.prev #node的前驅設為現在頭部的前驅   self.__head.prev.next = node #頭部前驅的后繼設為node   self.__head.prev = node #頭部自己的前驅改為node #獲得鏈表長度 節點個數 def length(self):  #如果鏈表是空的 就返回0  if self.is_empty():   return 0  #如果不是空的  else:   cur = self.__head #臨時變量cur表示當前位置 初始化設為頭head   count = 1 #設一個計數器count，cur每指向一個節點，count就自增1 目前cur指向頭，所以count初始化為1   #如果cur.next不是head，說明cur目前不是最后一個元素，那么count就1，再讓cur后移一位   while cur.next is not self.__head:    count += 1    cur = cur.next   #跳出循環說明所有元素都被累加了一次 返回count就是一共有多少個元素   return count #遍歷鏈表的功能 def travel(self):  #如果當前自己是空的，那就不遍歷  if self.is_empty():   return  #鏈表不空  else :   cur = self.__head #臨時變量cur表示當前位置，初始化為鏈表的頭部   #只要cur的后繼不是頭說明cur不是最后一個節點，我們就輸出當前值，并讓cur后移一個節點   while cur.next is not self.__head:    print( cur.item,end=" " )    cur = cur.next   #當cur的后繼是head的時候跳出循環了，最后一個節點還沒有打印值 在這里打印出來   print( cur.item ) #置頂位置插入節點 def insert(self, pos , item ):  #如果位置<=0 則調用頭部插入方法  if pos <= 0:   self.add(item)  #如果位置是最后一個或者更大 就調用尾部插入方法  elif pos > self.length() - 1 :   self.append(item)  #否則插入位置就是鏈表中間  else :   index = 0 #設置計數器，用于標記我們后移了多少步   cur = self.__head #cur標記當前所在位置   #讓index每次自增1 ，cur后移，當index=pos-1的時候說明cur在要插入位置的前一個元素，這時候停下   while index < pos - 1 :    index += 1    cur = cur.next   #跳出循環，cur在要插入位置的前一個元素，將node插入到cur的后面   node = Node(item) #新建一個節點   node.next = cur.next #node的后繼設為cur的后繼   node.prev = cur #node的前驅設為cur   cur.next.prev = node #cur后繼的前驅改為node   cur.next = node #cur后繼改為node #刪除節點操作 def remove(self,item):  #如果鏈表為空 直接不操作  if self.is_empty():   return  #鏈表不為空  else:   cur = self.__head #臨時變量標記位置，從頭開始   #如果頭結點就是 要刪除的元素   if cur.item == item:    #如果只有一個節點 鏈表就空了 head設為None    if self.length() == 1:     self.__head = None    #如果多個元素    else:     self.__head = cur.next #頭指針指向cur的下一個     cur.next.prev= cur.prev #cur后繼的前驅改為cur的前驅     cur.prev.next = cur.next #cur前驅的后繼改為cur的后繼   #否則 頭節點不是要刪除的節點 我們要向下遍歷   else:    cur = cur.next #把cur后移一個節點    #循環讓cur后移一直到鏈表尾元素位置，期間如果找得到就刪除節點，找不到就跳出循環，    while cur is not self.__head:     #找到了元素cur就是要刪除的     if cur.item == item:      cur.prev.next = cur.next #cur的前驅的后繼改為cur的后繼      cur.next.prev = cur.prev #cur的后繼的前驅改為cur的前驅     cur = cur.next #搜索節點是否存在 def search(self , item):  #如果鏈表是空的一定不存在  if self.is_empty():   return False  #否則鏈表不空  else:   cur = self.__head #設置臨時cur從頭開始   # cur不斷后移，一直到尾節點為止   while cur.next is not self.__head:    #如果期間找到了就返回一個True 結束運行    if cur.item == item:     return True    cur = cur.next   # 從循環跳出來cur就指向了尾元素 看一下為元素是不是要找的 是就返回True   if cur.item ==item:    return True   #所有元素都不是 就返回False 沒找到   return Falseif __name__ == "__main__": dlcl = DoubleCircleLinkList() print(dlcl.search(7)) dlcl.travel() dlcl.remove(1) print(dlcl.length()) print(dlcl.is_empty()) dlcl.append(55) print(dlcl.search(55)) dlcl.travel() dlcl.remove(55) dlcl.travel() print(dlcl.length()) dlcl.add(3) print(dlcl.is_empty()) dlcl.travel() dlcl.add(4) dlcl.add(5) dlcl.append(6) dlcl.insert(-10,1) dlcl.travel() print(dlcl.length()) dlcl.remove(6) dlcl.travel() print(dlcl.search(7) ) dlcl.append(55) dlcl.travel()