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

class Linklist():
? ? """
? ? 存儲所有節點類
? ? """
? ? def __init__(self):
? ? ? ? """
? ? ? ? 初始化一個頭結點
? ? ? ? 默認為空
? ? ? ? """
? ? ? ? self.head = None

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

? ? # 2. 鏈表的長度
? ? def length(self):
? ? ? ? """
? ? ? ? 返回節點的長度
? ? ? ? 實例化一個游標
? ? ? ? 使用這個游標遍歷所有的數據
? ? ? ? 使用一個計數器，遍歷一個數據，自增一，最后輸出計數器
? ? ? ? """
? ? ? ? # 實例化游標
? ? ? ? cur = self.head
? ? ? ? # 技術器
? ? ? ? # 如果鏈表為空，不會進入循環，直接輸出 0
? ? ? ? count = 0
? ? ? ? # 遍歷所有的數據
? ? ? ? while cur != None:
? ? ? ? ? ? count +=1
? ? ? ? ? ? cur = cur.next
? ? ? ? return count

? ? # 3. 遍歷鏈表
? ? def treval(self):
? ? ? ? """
? ? ? ? 遍歷鏈表，獲取所有的數據
? ? ? ? 使用游標，遍歷整個鏈表，每次輸出cur.item 的值
? ? ? ? 注意鏈表為空的情況，
? ? ? ? """
? ? ? ? # 實例化一個游標
? ? ? ? cur = self.head
? ? ? ? # 遍歷鏈表
? ? ? ? while cur != None:
? ? ? ? ? ? print(cur.item, end=' ')
? ? ? ? ? ? cur = cur.next
? ? ? ? print()
? ? # 4. 鏈表頭部添加元素
? ? def add(self, item):
? ? ? ? """
? ? ? ? 頭部添加數據
? ? ? ? 分析：
? ? ? ? 1、頭部添加數據，鏈表為空時： self.head 指向node
? ? ? ? 2、鏈表不為空時： 先將node.next = self.head.next, 再講 self.head = node
? ? ? ? """
? ? ? ? # 實例化節點
? ? ? ? node = Node(item)
? ? ? ? # 添加數據
? ? ? ? # 判斷鏈表是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? # 為空，直接將self.head 指向node
? ? ? ? ? ? self.head=node
? ? ? ? else:
? ? ? ? ? ? # 不為空，先將noede
? ? ? ? ? ? node.next = self.head
? ? ? ? ? ? self.head.prev=node
? ? ? ? ? ? self.head=node

? ? # 5. 鏈表尾部添加元素
? ? def append(self,item):
? ? ? ? """
? ? ? ? 尾部添加數據
? ? ? ? 分析：
? ? ? ? 要先將指針指向尾部的節點
? ? ? ? 最后的節點的 cur.next = node, node.prev = cur
? ? ? ? """
? ? ? ? # 實例化節點
? ? ? ? node = Node(item)
? ? ? ? # 實例化游標
? ? ? ? cur = self.head
? ? ? ? # 移動游標到最后一個節點
? ? ? ? # 如果鏈表為空
? ? ? ? # 直接使用頭插法
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.add(item)
? ? ? ? else:
? ? ? ? ? ? while cur.next != None:
? ? ? ? ? ? ? ? # cur.next 不為空，則進入循環， 上次循環，是進入上上個節點，但 將cur ?= cur.next，就指向了最后一個節點
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? node.prev = cur
? ? ? ? ? ? cur.next = node

? ? # 6. 鏈表指定位置添加元素
? ? def insert(self, index, item):
? ? ? ? """
? ? ? ? 指定位置添加數據
? ? ? ? 分析
? ? ? ? 單鏈表中需要實例化兩個有游標
? ? ? ? 雙向鏈表，直接向指針指向索引的位置
? ? ? ? 將這個位置節點的 cur.
? ? ? ? """
? ? ? ? # 實例化節點
? ? ? ? node = Node(item)
? ? ? ? # 實例化游標
? ? ? ? cur = self.head
? ? ? ? # 起始位置
? ? ? ? count = 0
? ? ? ? if index<=0:
? ? ? ? ? ? # 使用頭插法
? ? ? ? ? ? self.add(item)
? ? ? ? elif index > (self.length()-1):
? ? ? ? ? ? self.append(item)
? ? ? ? else:
? ? ? ? ? ? # 移動游標
? ? ? ? ? ? while count < index:
? ? ? ? ? ? ? ? # 增加一
? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? ? ? # 移動游標到索引位置
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? node.next = cur
? ? ? ? ? ? node.prev = cur.prev
? ? ? ? ? ? cur.prev.next = node
? ? ? ? ? ? cur.prev = node


? ? # 7. 鏈表刪除節點
? ? def remove(self,item):
? ? ? ? """
? ? ? ? 刪除指定的節點
? ? ? ? 首先實例化節點，遍歷鏈表，找到該節點，刪除該節點
? ? ? ? """
? ? ? ? # 實例化游標
? ? ? ? cur = self.head
? ? ? ? # 遍歷鏈表，找到該節點
? ? ? ? while cur != None:
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? if self.head == cur:
? ? ? ? ? ? ? ? ? ? self.head = cur.next
? ? ? ? ? ? ? ? ? ? if cur.next:
? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = None
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next
? ? ? ? ? ? ? ? ? ? # 如果有下個節點，防止最后一個節點
? ? ? ? ? ? ? ? ? ? if cur.next:
? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev
? ? ? ? ? ? ? ? ? ? pass
? ? ? ? ? ? ? ? break
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? cur = cur.next

? ? # # 8. 查找節點是否存在
? ? def search(self, item):
? ? ? ? """
? ? ? ? 查看節點是否存在
? ? ? ? 分析
? ? ? ? 遍歷鏈表，查看每一個節點的數據區
? ? ? ? 空鏈表
? ? ? ? 只有頭節點
? ? ? ? 只有尾節點
? ? ? ? """
? ? ? ? # 實例化一個游標
? ? ? ? cur = self.head

? ? ? ? # 遍歷鏈表
? ? ? ? while cur != None:
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? return False

# 程序的入口
if __name__ == "__main__":
? ? s = Linklist()
? ? print(s.is_empty()) ?# ?True
? ? s.append(100)?
? ? s.append(200)
? ? s.append(300)
? ? s.add(6)
? ? s.insert(1, 10)
? ? s.search(6)
? ? s.treval() ? # 6 10 100 200 300?
? ? s.remove(100)
? ? s.treval() ? # 6 10 200 300?
? ? pass