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

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

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

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

? ? # 3. 遍歷鏈表
? ? def treval(self):
? ? ? ? """
? ? ? ? 遍歷鏈表，獲取所有的數(shù)據(jù)
? ? ? ? 使用游標(biāo)，遍歷整個鏈表，每次輸出cur.item 的值
? ? ? ? 注意鏈表為空的情況，
? ? ? ? """
? ? ? ? # 實例化一個游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 遍歷鏈表
? ? ? ? while cur != None:
? ? ? ? ? ? print(cur.item, end=' ')
? ? ? ? ? ? cur = cur.next
? ? ? ? print()
? ? # 4. 鏈表頭部添加元素
? ? def add(self, item):
? ? ? ? """
? ? ? ? 頭部添加數(shù)據(jù)
? ? ? ? 分析：
? ? ? ? 1、頭部添加數(shù)據(jù)，鏈表為空時： self.head 指向node
? ? ? ? 2、鏈表不為空時： 先將node.next = self.head.next, 再講 self.head = node
? ? ? ? """
? ? ? ? # 實例化節(jié)點
? ? ? ? node = Node(item)
? ? ? ? # 添加數(shù)據(jù)
? ? ? ? # 判斷鏈表是否為空
? ? ? ? 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):
? ? ? ? """
? ? ? ? 尾部添加數(shù)據(jù)
? ? ? ? 分析：
? ? ? ? 要先將指針指向尾部的節(jié)點
? ? ? ? 最后的節(jié)點的 cur.next = node, node.prev = cur
? ? ? ? """
? ? ? ? # 實例化節(jié)點
? ? ? ? node = Node(item)
? ? ? ? # 實例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 移動游標(biāo)到最后一個節(jié)點
? ? ? ? # 如果鏈表為空
? ? ? ? # 直接使用頭插法
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.add(item)
? ? ? ? else:
? ? ? ? ? ? while cur.next != None:
? ? ? ? ? ? ? ? # cur.next 不為空，則進(jìn)入循環(huán)， 上次循環(huán)，是進(jìn)入上上個節(jié)點，但 將cur ?= cur.next，就指向了最后一個節(jié)點
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? node.prev = cur
? ? ? ? ? ? cur.next = node

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


? ? # 7. 鏈表刪除節(jié)點
? ? def remove(self,item):
? ? ? ? """
? ? ? ? 刪除指定的節(jié)點
? ? ? ? 首先實例化節(jié)點，遍歷鏈表，找到該節(jié)點，刪除該節(jié)點
? ? ? ? """
? ? ? ? # 實例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 遍歷鏈表，找到該節(jié)點
? ? ? ? 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
? ? ? ? ? ? ? ? ? ? # 如果有下個節(jié)點，防止最后一個節(jié)點
? ? ? ? ? ? ? ? ? ? if cur.next:
? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev
? ? ? ? ? ? ? ? ? ? pass
? ? ? ? ? ? ? ? break
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? cur = cur.next

? ? # # 8. 查找節(jié)點是否存在
? ? def search(self, item):
? ? ? ? """
? ? ? ? 查看節(jié)點是否存在
? ? ? ? 分析
? ? ? ? 遍歷鏈表，查看每一個節(jié)點的數(shù)據(jù)區(qū)
? ? ? ? 空鏈表
? ? ? ? 只有頭節(jié)點
? ? ? ? 只有尾節(jié)點
? ? ? ? """
? ? ? ? # 實例化一個游標(biāo)
? ? ? ? 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