# Functions ?函數(shù)聲明
class Node():
? ? """
? ? 存放節(jié)點(diǎn)類
? ? 每次調(diào)用該類，實(shí)例化一個(gè)節(jié)點(diǎn)
? ? 默認(rèn)每個(gè)節(jié)點(diǎn)中有數(shù)據(jù)區(qū)，next區(qū)。
? ? 數(shù)據(jù)區(qū)為該數(shù)據(jù)，next區(qū)為空
? ? """
? ? def __init__(self, item,next=None):
? ? ? ? self.item = item
? ? ? ? self.next = next
? ? ? ? pass

class Linklist():
? ? """
? ? 存放數(shù)據(jù)類
? ? 將所有的節(jié)點(diǎn)存放起來的容器
? ? 首先，默認(rèn)鏈表為空，在這里需要有一個(gè)頭節(jié)點(diǎn)，默認(rèn)頭節(jié)點(diǎn)為空

? ? """
? ? def __init__(self, head=None):
? ? ? ? self.head = head

? ? def is_empty(self):
? ? ? ? return self.head == None

? ? def append(self, item):
? ? ? ? """
? ? ? ? 往鏈表尾部添加數(shù)據(jù)
? ? ? ? 1、實(shí)例化游標(biāo)：使用游標(biāo)指向每一個(gè)數(shù)據(jù)，檢索數(shù)據(jù)和判斷數(shù)據(jù)next是否為空
? ? ? ? 2、移動游標(biāo)，從頭節(jié)點(diǎn)開始，每次使用self.next移動，以為next指向的就是下一個(gè)數(shù)據(jù)
? ? ? ? 3、添加數(shù)據(jù)，首先判斷鏈表是否為空，為空的情況下，直接將頭節(jié)點(diǎn)等于node數(shù)據(jù)
? ? ? ? 4、如果不為空，需要從頭節(jié)點(diǎn)開始，移動游標(biāo)，判斷游標(biāo)指向的next是否為空
? ? ? ? 5、使用循環(huán)不停的移動節(jié)點(diǎn)，當(dāng)遇到節(jié)點(diǎn)中的next為空的情況下停止移動
? ? ? ? 6、循環(huán)條件： 當(dāng) 條件 != None, 進(jìn)入循環(huán)獲取，當(dāng)cur為空時(shí)就不會進(jìn)入循環(huán)，所以在這里要使用 cur != None
? ? ? ? """
? ? ? ? # 首先要實(shí)例化一個(gè)節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 如果鏈表為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? # 直接將頭節(jié)點(diǎn)的next添加node
? ? ? ? ? ? self.head = node
? ? ? ? else:
? ? ? ? ? ? # 實(shí)例化一個(gè)游標(biāo)
? ? ? ? ? ? cur = self.head
? ? ? ? ? ? while cur.next != None:
? ? ? ? ? ? ? ? # 移動游標(biāo)，得到最后一個(gè)游標(biāo)的數(shù)據(jù)
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? # 將移動后的數(shù)據(jù)的下一個(gè)next添加上 node
? ? ? ? ? ? cur.next=node
? ? ? ? ? ? pass

? ? def travel(self):
? ? ? ? """遍歷數(shù)據(jù)"""
? ? ? ? # 實(shí)例化一個(gè)游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 數(shù)據(jù)鏈為空的情況
? ? ? ? if self.is_empty():
? ? ? ? ? ? print('')
? ? ? ? else:
? ? ? ? ? ? # 獲取每個(gè)數(shù)據(jù)區(qū)中的數(shù)據(jù)
? ? ? ? ? ? # 移動游標(biāo)，每移動一次，輸出一次數(shù)據(jù)區(qū)內(nèi)的數(shù)據(jù)
? ? ? ? ? ? while cur != None:
? ? ? ? ? ? ? ? print(cur.item, end=' ')
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? print()

? ? def length(self):
? ? ? ? """返回鏈表的長度"""
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 計(jì)數(shù)，這里對空鏈表進(jìn)行判斷，如果是鏈表，則不會進(jìn)入循環(huán)，直接輸出 0
? ? ? ? count = 0
? ? ? ? # 移動游標(biāo)，獲取下一個(gè)數(shù)據(jù)，然后讓count +=1
? ? ? ? while cur != None:
? ? ? ? ? ? # 計(jì)數(shù)
? ? ? ? ? ? count+=1
? ? ? ? ? ? # 移動游標(biāo)
? ? ? ? ? ? cur = cur.next
? ? ? ? return count

? ? def add(self, item):
? ? ? ? """
? ? ? ? 頭部添加數(shù)據(jù)
? ? ? ? 分析： 將數(shù)據(jù)添加到第一個(gè)節(jié)點(diǎn)當(dāng)中
? ? ? ? 1、 需要先將node的next指向 原第一個(gè)節(jié)點(diǎn)，這原第一個(gè)節(jié)點(diǎn)就是self.head
? ? ? ? 2、 再講self.head指向node進(jìn)行連接
? ? ? ? """
? ? ? ? # 先實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 將數(shù)據(jù)添加到頭部當(dāng)中
? ? ? ? node.next=self.head
? ? ? ? self.head=node

? ? def insert(self, index, item):
? ? ? ? """
? ? ? ? 指定位置添加數(shù)據(jù)
? ? ? ? 分析：
? ? ? ? 1、首先要找到，該位置的數(shù)據(jù)
? ? ? ? 2、將要添加的數(shù)據(jù)next等于 原位置的next數(shù)據(jù)
? ? ? ? 3、原數(shù)據(jù)的 next等于node新數(shù)據(jù)
? ? ? ? """
? ? ? ? if index<=0:
? ? ? ? ? ? # 如果輸入的索引小于或者等于O，默認(rèn)使用頭插發(fā)
? ? ? ? ? ? self.add(item)
? ? ? ? elif index>self.length():
? ? ? ? ? ? # 如果輸入的索引大于鏈表的長度,使用尾插法
? ? ? ? ? ? self.append(item)
? ? ? ? else:
? ? ? ? ? ? # 實(shí)例化數(shù)據(jù)節(jié)點(diǎn)
? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? # 找到該數(shù)據(jù)的位置
? ? ? ? ? ? # 實(shí)例化一個(gè)游標(biāo)
? ? ? ? ? ? cur = self.head
? ? ? ? ? ? # 計(jì)數(shù)
? ? ? ? ? ? conent = 0
? ? ? ? ? ? while conent<(index-1):
? ? ? ? ? ? ? ? conent+=1
? ? ? ? ? ? ? ? cur = cur.next

? ? ? ? ? ? node.next=cur.next
? ? ? ? ? ? cur.next=node

? ? def search(self, item):
? ? ? ? """
? ? ? ? 查詢指定的數(shù)據(jù)是否存在
? ? ? ? 分析： 查詢指定的數(shù)據(jù)，需要對整個(gè)鏈表掃描，判斷這個(gè)數(shù)據(jù)是否等的該節(jié)點(diǎn)中的數(shù)據(jù)
? ? ? ? """
? ? ? ? # 實(shí)例化一個(gè)游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 進(jìn)行判斷是否相等
? ? ? ? while cur != None:
? ? ? ? ? ? # 判斷
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? pass
? ? ? ? # 否則返回False
? ? ? ? return False

? ? def remove(self, item):
? ? ? ? """
? ? ? ? 移除指定的數(shù)據(jù)
? ? ? ? 分析：
? ? ? ? 1、刪除數(shù)據(jù)，需要首先判斷數(shù)據(jù)是否存在
? ? ? ? 2、找到該數(shù)據(jù)所在的位置，將該數(shù)據(jù)的上一個(gè)數(shù)據(jù)的next指向自己的next
? ? ? ? 3、如何獲取該數(shù)據(jù)的指向，和上一個(gè)數(shù)據(jù)的指向
? ? ? ? 4、需要定義兩個(gè)指針
? ? ? ? 5、先將兩個(gè)指針相等，再講一個(gè)指針先移動一次，再同時(shí)移動

? ? ? ? """
? ? ? ? # 先找到該數(shù)據(jù)
? ? ? ? cur = self.head
? ? ? ? por = None

? ? ? ? while cur != None:
? ? ? ? ? ? if cur.item==item:
? ? ? ? ? ? ? ? # 要判斷是否為第一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ? ? if cur == self.head:
? ? ? ? ? ? ? ? ? ? self.head = cur.next
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? por.next = cur.next
? ? ? ? ? ? ? ? break
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? # 如果在當(dāng)前節(jié)點(diǎn)中沒有相等的，將節(jié)點(diǎn)進(jìn)行移動
? ? ? ? ? ? ? ? # 移動要注意，現(xiàn)將兩個(gè)游標(biāo)相等，再講另一個(gè)游標(biāo)移動一次
? ? ? ? ? ? ? ? por = cur
? ? ? ? ? ? ? ? cur = cur.next

# 程序的入口
if __name__ == "__main__":
? ? s = Linklist()
? ? s.append(100)
? ? s.append(200)
? ? s.append(300)
? ? s.add(1)
? ? s.add(12)
? ? s.insert(-1,6)
? ??
? ? s.travel() ? ? ? # ?6 12 1 100 200 300?
? ? print(s.length()) ?# 6
? ? print(s.search(11)) # False
? ? s.remove(12)
? ? s.travel() ? ? ? # 6 1 100 200 300?
? ? print(s.length()) ?# 5
? ? print(s.search(11)) # False
? ? pass