# Functions ?函數(shù)聲明
class Node():
? ? """實(shí)例化節(jié)點(diǎn)類"""
? ? def __init__(self, item):
? ? ? ? self.item = item
? ? ? ? self.prev = None
? ? ? ? self.next = None

class Linklist():
? ? """
? ? 存放節(jié)點(diǎn)類
? ? """
? ? def __init__(self):
? ? ? ? self.head = None

? ? # 1. 鏈表是否為空
? ? def is_empty(self):
? ? ? ? return self.head == None

? ? # 2. 鏈表的長(zhǎng)度
? ? def length(self):
? ? ? ? """
? ? ? ? 返回鏈表中所有數(shù)據(jù)的個(gè)數(shù)
? ? ? ? 實(shí)例化游標(biāo)，遍歷鏈表，使用計(jì)數(shù)器自增一
? ? ? ? 空鏈表

? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return 0
? ? ? ? else:
? ? ? ? ? ? # 不為空
? ? ? ? ? ? # 定義計(jì)數(shù)
? ? ? ? ? ? count = 1
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? return count
? ? ? ? ? ? pass

? ? # 3. 遍歷鏈表
? ? def travel(self):
? ? ? ? """
? ? ? ? 遍歷鏈表
? ? ? ? 實(shí)例化游標(biāo)，遍歷鏈表，每次輸出節(jié)點(diǎn)的數(shù)據(jù)
? ? ? ? 空鏈表
? ? ? ? 只有頭節(jié)點(diǎn)
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? print(cur.item, end=' ')
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? print(cur.item)
? ? ? ? ? ? pass

? ? # 4. 鏈表頭部添加元素
? ? def add(self, item):
? ? ? ? """
? ? ? ? 頭節(jié)點(diǎn)添加
? ? ? ? 實(shí)例化節(jié)點(diǎn)，
? ? ? ? """
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? node.next = node
? ? ? ? ? ? node.prev = node
? ? ? ? ? ? self.head = node
? ? ? ? else:
? ? ? ? ? ? # 鏈表不為空的情況
? ? ? ? ? ? # 只有一個(gè)節(jié)點(diǎn)的情況
? ? ? ? ? ? # node.next = self.head
? ? ? ? ? ? node.next = cur
? ? ? ? ? ? node.prev = cur
? ? ? ? ? ? if cur.next == self.head:
? ? ? ? ? ? ? ? # print(cur.item)
? ? ? ? ? ? ? ? cur.prev = node
? ? ? ? ? ? ? ? cur.next = node
? ? ? ? ? ? ? ? self.head = node
? ? ? ? ? ? elif cur.next != self.head:
? ? ? ? ? ? ? ? pro = self.head
? ? ? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? pro.prev = node
? ? ? ? ? ? ? ? cur.next = node
? ? ? ? ? ? ? ? self.head = node
? ? ? ? ? ? ? ? pass

? ? # 5. 鏈表尾部添加元素
? ? def append(self, item):
? ? ? ? """
? ? ? ? 鏈表尾部添加數(shù)據(jù)
? ? ? ? 實(shí)例化節(jié)點(diǎn)，實(shí)例化游標(biāo)，指向尾部節(jié)點(diǎn)，修改指向
? ? ? ? 鏈表為空
? ? ? ? """
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.add(item)
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況
? ? ? ? ? ? # 指針指向最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? self.head.prev = node
? ? ? ? ? ? node.next = self.head
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? node.prev = cur
? ? ? ? ? ? cur.next = node
? ? ? ? ? ? pass

? ? # 6. 鏈表指定位置添加元素
? ? def insert(self, index, item):
? ? ? ? """
? ? ? ? 指定位置添加數(shù)據(jù)
? ? ? ? 實(shí)例化節(jié)點(diǎn)， 實(shí)例化游標(biāo)
? ? ? ? 移動(dòng)游標(biāo)到索引位置，更改指向
? ? ? ? 輸入索引大小判斷
? ? ? ? 鏈表是否為空
? ? ? ? """
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? if index <= 0:
? ? ? ? ? ? self.add(item)
? ? ? ? elif index > (self.length()-1):
? ? ? ? ? ? self.append(item)
? ? ? ? else:
? ? ? ? ? ? # 中間添加數(shù)據(jù)
? ? ? ? ? ? # 聲明計(jì)數(shù)
? ? ? ? ? ? count = 0
? ? ? ? ? ? print(index)
? ? ? ? ? ? while count < index-1:
? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? # print(cur.item)
? ? ? ? ? ? node.next = cur.next
? ? ? ? ? ? node.prev = cur
? ? ? ? ? ? cur.next.prev = node
? ? ? ? ? ? cur.next = node
? ? ? ? ? ? pass

? ? # 7. 鏈表刪除節(jié)點(diǎn)
? ? def remove(self, item):
? ? ? ? """
? ? ? ? 刪除數(shù)據(jù)
? ? ? ? 實(shí)例化游標(biāo)，遍歷鏈表，查找有沒有改數(shù)據(jù)
? ? ? ? 有，對(duì)改數(shù)據(jù)兩側(cè)的節(jié)點(diǎn)進(jìn)行指向修改
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況下
? ? ? ? ? ? # 如果刪除的是頭節(jié)點(diǎn)
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? # 如果只有一個(gè)頭節(jié)點(diǎn)
? ? ? ? ? ? ? ? if cur.next == self.head:
? ? ? ? ? ? ? ? ? ?self.head = None
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? # self.head = cur.next
? ? ? ? ? ? ? ? ? ? pro = cur.next
? ? ? ? ? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? ? ? cur.next = pro
? ? ? ? ? ? ? ? ? ? pro.prev = cur
? ? ? ? ? ? ? ? ? ? self.head = pro
? ? ? ? ? ? ? ? ? ? pass
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? ? ? # print(cur.item)
? ? ? ? ? ? ? ? ? ? ? ? pro = cur.prev
? ? ? ? ? ? ? ? ? ? ? ? nex = cur.next
? ? ? ? ? ? ? ? ? ? ? ? pro.next = cur.next
? ? ? ? ? ? ? ? ? ? ? ? nex.prev = pro
? ? ? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? # 如果是最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? cur.prev.next = self.head
? ? ? ? ? ? ? ? ? ? self.head.prev = cur.prev

? ? # 8. 查找節(jié)點(diǎn)是否存在
? ? def search(self, item):
? ? ? ? """
? ? ? ? 查詢指定的數(shù)據(jù)是否存在
? ? ? ? 實(shí)例化游標(biāo)
? ? ? ? 遍歷所有的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)中判斷數(shù)據(jù)是否相等，相等，返回True
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況
? ? ? ? ? ? # 遍歷所有的節(jié)點(diǎn)
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? pass

# 程序的入口
if __name__ == "__main__":
? ? a = Linklist()
? ? a .add(400)
? ? a .add(300)
? ? a .add(200)
? ? a .add(100)
? ? a.append(10)
? ? a.append(11)
? ? a.add(1)
? ? a.insert(30, 12) # 1 100 200 300 400 10 11 12
? ? a.remove(1) ? ?# 100 200 300 400 10 11 12
? ? a.remove(12) ? # 100 200 300 400 10 11
? ? a.remove(400) ?# # 100 200 300 ?10 11
? ? a.remove(4000)
? ? print(a.search(100)) ?# True
? ? print(a.search(11)) ? # True
? ? print(a.search(111)) ?# None
? ? print(a.is_empty()) ? # False
? ? a.travel() ? ? ? ? ? ?# 100 200 300 10 11
? ? print(a.length()) ? ? # 5
? ? pass