class Node(object):
?? ?def __init__(self, item=None):
?? ??? ?#放數(shù)據(jù)
?? ??? ?self.item= item
?? ??? ?#指向后一個節(jié)點(diǎn)
?? ??? ?self.next = None
?? ??? ?#指向前一個節(jié)點(diǎn)
?? ??? ?self.prior =None

#雙向鏈表 ?從左往右讀
class Node(object):
? ? ? ? """雙向鏈表節(jié)點(diǎn)"""
? ? ? ? def __init__(self,item):
? ? ? ? ? ? ? ? #放數(shù)據(jù)的節(jié)點(diǎn)
? ? ? ? ? ? ? ? self.elem = item
? ? ? ? ? ? ? ? #指向后一個節(jié)點(diǎn)
? ? ? ? ? ? ? ? self.next = None
? ? ? ? ? ? ? ? #指向前一個節(jié)點(diǎn)
? ? ? ? ? ? ? ? self.prev = None
#雙向鏈表
class LinkList(object):
? ? ? ? def __init__(self,node=None):
? ? ? ? ? ? ? ? #代表頭節(jié)點(diǎn)
? ? ? ? ? ? ? ? self.__head = node

? ? ? ? #判斷鏈表是否為空
? ? ? ? def is_empty(self):
? ? ? ? ? ? ? ? return self.__head == None

? ? ? ? def length(self):
? ? ? ? ? ? ? ? """返回鏈表的長度"""
? ? ? ? ? ? ? ? #cur游標(biāo)移動，從而實(shí)現(xiàn)遍歷元素的功能
? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? #count用來計(jì)數(shù)
? ? ? ? ? ? ? ? count = 0
? ? ? ? ? ? ? ? while cur != None:
? ? ? ? ? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? ? ? ? ? ? ? #讓cur游標(biāo)可以向下移動
? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? return count

? ? ? ? #遍歷整個鏈表
? ? ? ? def travel(self):
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ? ? ? ? return
? ? ? ? ? ? ? ? #建立游標(biāo)等于起始節(jié)點(diǎn)
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? ? ? ? ? while cur != None:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? print(cur.elem,end=" ")
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? ? ? ? ? print("")

? ? ? ? #頭插法
? ? ? ? def add(self,item):
? ? ? ? ? ? ? ? #新節(jié)點(diǎn)
? ? ? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ? ? ? ? #頭節(jié)點(diǎn)指向了新的節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? self.__head = node
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? #新節(jié)點(diǎn)指向原第一個節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? node.next = self.__head
? ? ? ? ? ? ? ? ? ? ? ? self.__head = node
? ? ? ? ? ? ? ? ? ? ? ? node.next.prev = node

? ? ? ? def append(self,item):
? ? ? ? ? ? ? ? """鏈表尾部添加元素"""
? ? ? ? ? ? ? ? node = Node(item) ?#定義新節(jié)點(diǎn)
? ? ? ? ? ? ? ? #鏈表是否為空鏈表
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ? ? ? ? #如果為空，新的節(jié)點(diǎn)加了進(jìn)去
? ? ? ? ? ? ? ? ? ? ? ? self.__head = node
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? #頭節(jié)點(diǎn) 創(chuàng)建游標(biāo)
? ? ? ? ? ? ? ? ? ? ? ? cur = self.__head ? #設(shè)置指向頭結(jié)點(diǎn)的游標(biāo) ?此時的當(dāng)前鏈表第一個節(jié)點(diǎn)，就是頭節(jié)點(diǎn)指向的節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? #cur到最后一個節(jié)點(diǎn)停下
? ? ? ? ? ? ? ? ? ? ? ? while cur.next != None:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? ? ? ? ? #添加節(jié)點(diǎn)到尾部 cur道了最后一個結(jié)點(diǎn) ?cur.next指向了新的節(jié)點(diǎn)node ?從左往右讀 ?
? ? ? ? ? ? ? ? ? ? ? ? cur.next = node
? ? ? ? ? ? ? ? ? ? ? ? #當(dāng)前的節(jié)點(diǎn)指向它前一個
? ? ? ? ? ? ? ? ? ? ? ? node.prev = cur

? ? ? ? #插入法 ?#pos從零開始
? ? ? ? def insert(self,pos,item):
? ? ? ? ? ? ? ? """在指定位置添加元素"""
? ? ? ? ? ? ? ? #指向不是頭部元素，self.__head的地址
? ? ? ? ? ? ? ? # 為下一個元素，所以pre為下一個元素
? ? ? ? ? ? ? ? if pos <= 0:
? ? ? ? ? ? ? ? ? ? ? ? #認(rèn)為是頭插法
? ? ? ? ? ? ? ? ? ? ? ? self.add(item)
? ? ? ? ? ? ? ? #假如長度是3 pos大于2要特殊處理 ?
? ? ? ? ? ? ? ? elif pos > (self.length()-1):
? ? ? ? ? ? ? ? ? ? ? ? #尾插法
? ? ? ? ? ? ? ? ? ? ? ? self.append(item)
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ?? ??? ?#創(chuàng)建節(jié)點(diǎn) 新節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? ? ? ? ? count = 0
? ? ? ? ? ? ? ? ? ? ? ? #動起來
? ? ? ? ? ? ? ? ? ? ? ? while count < pos:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? #把節(jié)點(diǎn)鏈接到中間任意位置 插入前一個節(jié)點(diǎn) ? 此時，cur停在后一個節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? 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指向的數(shù)據(jù),是否為要刪除的數(shù)據(jù) ? item要刪除的元素
? ? ? ? ? ? ? ? ? ? ? ? if cur.elem == item:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #判斷此節(jié)點(diǎn)是否為頭節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #考慮特殊情況,恰好要刪除是第一個元素 ? ?當(dāng)前的元素就是我要刪除的元素?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if cur == self.__head:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #如果刪除中間, ?頭節(jié)點(diǎn)指向后一個節(jié)點(diǎn)?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? self.__head = cur.next
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #考慮鏈表只有一個節(jié)點(diǎn) ?直接指向None
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if cur.next != None:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #是否只有一個節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = None
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #中間節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if cur.next != None:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #沒有找到,cur游標(biāo)向繼續(xù)往下移動
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next

? ? ? ? def search(self,item):
? ? ? ? ? ? ? ? """查找結(jié)點(diǎn)是否存在"""
? ? ? ? ? ? ? ? #如果是一個空鏈表
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ? ? ? ? return False
? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? while cur.next != self.__head:
? ? ? ? ? ? ? ? ? ? ? ? #cur數(shù)據(jù)是否為查找的數(shù)據(jù) item是要查的數(shù)據(jù)?
? ? ? ? ? ? ? ? ? ? ? ? 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()