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