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