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()