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

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

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

? ? # 2. 鏈表的長度
? ? def length(self):
? ? ? ? """
? ? ? ? 返回鏈表的長度
? ? ? ? 遍歷所有的節(jié)點(diǎn)，使用計(jì)數(shù)器計(jì)數(shù)
? ? ? ? 1、鏈表為空情況
? ? ? ? """
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? 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

? ? # 3. 遍歷鏈表
? ? def travel(self):
? ? ? ? """
? ? ? ? 遍歷鏈表，獲取所有的數(shù)據(jù)
? ? ? ? 實(shí)例游標(biāo)，遍歷數(shù)據(jù)，輸出數(shù)據(jù)
? ? ? ? 1、 空鏈表情況
? ? ? ? 2、 只有頭部節(jié)點(diǎn)情況
? ? ? ? 3、 只有尾部節(jié)點(diǎn)情況
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 遍歷數(shù)據(jù)
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? print(cur.item, end=' ')
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? # 最后一個(gè)節(jié)點(diǎn)要單獨(dú)輸出
? ? ? ? ? ? print(cur.item)

? ? # 4. 鏈表頭部添加元素
? ? def add(self, item):
? ? ? ? """
? ? ? ? 往鏈表頭部添加數(shù)據(jù)
? ? ? ? 分析
? ? ? ? 鏈表為空
? ? ? ? ? ? self.head 直接指向node， 再講node指向自己
? ? ? ? 鏈表不為空
? ? ? ? ? ? node.next = self.head
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.head = node
? ? ? ? ? ? node.next = node
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況
? ? ? ? ? ? # 要將最后一個(gè)節(jié)點(diǎn)指向node
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? node.next = self.head
? ? ? ? ? ? self.head = node
? ? ? ? ? ? cur.next = node

? ? # 5. 鏈表尾部添加元素
? ? def append(self, item):
? ? ? ? """
? ? ? ? 往尾部添加數(shù)據(jù)
? ? ? ? 分析
? ? ? ? 實(shí)例化節(jié)點(diǎn)，再實(shí)例化游標(biāo)先指向最后一個(gè)節(jié)點(diǎn)
? ? ? ? 調(diào)換指向
? ? ? ? 1、空鏈表情況
? ? ? ? 2、只有一個(gè)鏈表情況

? ? ? ? """
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.add(item)
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況,移動(dòng)游標(biāo)指向最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? node.next = self.head
? ? ? ? ? ? cur.next = node
? ? ? ? ? ? pass

? ? # 6. 鏈表指定位置添加元素
? ? def insert(self, index, item):
? ? ? ? """
? ? ? ? 指定位置添加數(shù)據(jù)
? ? ? ? 實(shí)例化節(jié)點(diǎn)， 實(shí)例化游標(biāo)指向索引的數(shù)據(jù)，更改指向
? ? ? ? 位置大小
? ? ? ? 鏈表是否為空

? ? ? ? """
? ? ? ? # 實(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:
? ? ? ? ? ? # 判斷鏈表是否為空
? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? self.add(item)
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? # 移動(dòng)游標(biāo)，指向指定的索引位置
? ? ? ? ? ? ? ? count = 0
? ? ? ? ? ? ? ? while count < index-1:
? ? ? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? node.next = cur.next
? ? ? ? ? ? ? ? cur.next = node
? ? ? ? ? ? pass

? ? # 7. 鏈表刪除節(jié)點(diǎn)
? ? def remove(self, item):
? ? ? ? """
? ? ? ? 刪除指定的節(jié)點(diǎn)
? ? ? ? 實(shí)例化游標(biāo)，遍歷鏈表插件這個(gè)節(jié)點(diǎn)是否存在，存在則更改指向
? ? ? ? 不存在，則不修改
? ? ? ? 空鏈表情況
? ? ? ? 頭節(jié)點(diǎn)情況
? ? ? ? 尾結(jié)點(diǎn)情況
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空，遍歷鏈表，對(duì)比數(shù)據(jù)是否相等
? ? ? ? ? ? # 如果頭節(jié)點(diǎn)是要?jiǎng)h除的數(shù)據(jù)
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? self.head=cur.next
? ? ? ? ? ? ? ? # 找出最后的節(jié)點(diǎn)，將最后的節(jié)點(diǎn)指向，刪除后面的那個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? cur.next = cur.next
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? pro = None
? ? ? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? ? ? ? ? pro.next = cur.next
? ? ? ? ? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? pro = cur
? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? pro.next = self.head
? ? ? ? ? ? pass

? ? # 8. 查找節(jié)點(diǎn)是否存在
? ? def search(self, item):
? ? ? ? """
? ? ? ? 查找該節(jié)點(diǎn)是否存在
? ? ? ? 實(shí)例化游標(biāo)，遍歷所有的節(jié)點(diǎn)
? ? ? ? 查看當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)是否和item 相等
? ? ? ? 空鏈表
? ? ? ? 頭節(jié)點(diǎn)
? ? ? ? 尾結(jié)點(diǎn)
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷空鏈表
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空遍歷整個(gè)鏈表
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? 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.insert(4,6)
? ? # a.remove(6)
? ? print(a.length()) ?# 5
? ? a.travel() ? ? ? ? # 100 200 300 400 6
? ? print(a.search(100)) # True
? ? pass