# Functions ?函數聲明
class Node():
? ? """實例化節點類"""
? ? def __init__(self, item):
? ? ? ? self.item = item
? ? ? ? self.next = None

class Linklist():
? ? """
? ? 存放節點類
? ? """
? ? def __init__(self):
? ? ? ? self.head = None

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

? ? # 2. 鏈表的長度
? ? def length(self):
? ? ? ? """
? ? ? ? 返回鏈表的長度
? ? ? ? 遍歷所有的節點，使用計數器計數
? ? ? ? 1、鏈表為空情況
? ? ? ? """
? ? ? ? # 實例化節點
? ? ? ? cur = self.head
? ? ? ? if self.is_empty():
? ? ? ? ? ? return 0
? ? ? ? else:
? ? ? ? ? ? # 計數
? ? ? ? ? ? count = 1
? ? ? ? ? ? # 遍歷鏈表
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? return count

? ? # 3. 遍歷鏈表
? ? def travel(self):
? ? ? ? """
? ? ? ? 遍歷鏈表，獲取所有的數據
? ? ? ? 實例游標，遍歷數據，輸出數據
? ? ? ? 1、 空鏈表情況
? ? ? ? 2、 只有頭部節點情況
? ? ? ? 3、 只有尾部節點情況
? ? ? ? """
? ? ? ? # 實例化游標
? ? ? ? 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)

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

? ? # 5. 鏈表尾部添加元素
? ? def append(self, item):
? ? ? ? """
? ? ? ? 往尾部添加數據
? ? ? ? 分析
? ? ? ? 實例化節點，再實例化游標先指向最后一個節點
? ? ? ? 調換指向
? ? ? ? 1、空鏈表情況
? ? ? ? 2、只有一個鏈表情況

? ? ? ? """
? ? ? ? # 實例化節點
? ? ? ? node = Node(item)
? ? ? ? # 實例化游標
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.add(item)
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況,移動游標指向最后一個節點
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? node.next = self.head
? ? ? ? ? ? cur.next = node
? ? ? ? ? ? pass

? ? # 6. 鏈表指定位置添加元素
? ? def insert(self, index, item):
? ? ? ? """
? ? ? ? 指定位置添加數據
? ? ? ? 實例化節點， 實例化游標指向索引的數據，更改指向
? ? ? ? 位置大小
? ? ? ? 鏈表是否為空

? ? ? ? """
? ? ? ? # 實例化節點
? ? ? ? node = Node(item)
? ? ? ? # 實例化游標
? ? ? ? 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:
? ? ? ? ? ? ? ? # 移動游標，指向指定的索引位置
? ? ? ? ? ? ? ? count = 0
? ? ? ? ? ? ? ? while count < index-1:
? ? ? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? node.next = cur.next
? ? ? ? ? ? ? ? cur.next = node
? ? ? ? ? ? pass

? ? # 7. 鏈表刪除節點
? ? def remove(self, item):
? ? ? ? """
? ? ? ? 刪除指定的節點
? ? ? ? 實例化游標，遍歷鏈表插件這個節點是否存在，存在則更改指向
? ? ? ? 不存在，則不修改
? ? ? ? 空鏈表情況
? ? ? ? 頭節點情況
? ? ? ? 尾結點情況
? ? ? ? """
? ? ? ? # 實例化游標
? ? ? ? cur = self.head
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空，遍歷鏈表，對比數據是否相等
? ? ? ? ? ? # 如果頭節點是要刪除的數據
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? self.head=cur.next
? ? ? ? ? ? ? ? # 找出最后的節點，將最后的節點指向，刪除后面的那個節點
? ? ? ? ? ? ? ? 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. 查找節點是否存在
? ? def search(self, item):
? ? ? ? """
? ? ? ? 查找該節點是否存在
? ? ? ? 實例化游標，遍歷所有的節點
? ? ? ? 查看當前節點的數據是否和item 相等
? ? ? ? 空鏈表
? ? ? ? 頭節點
? ? ? ? 尾結點
? ? ? ? """
? ? ? ? # 實例化游標
? ? ? ? cur = self.head
? ? ? ? # 判斷空鏈表
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空遍歷整個鏈表
? ? ? ? ? ? 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