python單向連結串列範例詳解

# Functions  函數宣告
class Node():
    """
    存放節點類
    每次呼叫該類，範例化一個節點
    預設每個節點中有資料區，next區。
    資料區為該資料，next區為空
    """
    def __init__(self, item,next=None):
        self.item = item
        self.next = next
        pass

class Linklist():
    """
    存放資料類
    將所有的節點存放起來的容器
    首先，預設連結串列為空，在這裡需要有一個頭節點，預設頭節點為空

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

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

    def append(self, item):
        """
        往連結串列尾部新增資料
        1、範例化遊標：使用遊標指向每一個資料，檢索資料和判斷資料next是否為空
        2、移動遊標，從頭節點開始，每次使用self.next移動，以為next指向的就是下一個資料
        3、新增資料，首先判斷連結串列是否為空，為空的情況下，直接將頭節點等於node資料
        4、如果不為空，需要從頭節點開始，移動遊標，判斷遊標指向的next是否為空
        5、使用迴圈不停的移動節點，當遇到節點中的next為空的情況下停止移動
        6、迴圈條件： 當 條件 != None, 進入迴圈獲取，當cur為空時就不會進入迴圈，所以在這裡要使用 cur != None
        """
        # 首先要範例化一個節點
        node = Node(item)
        # 如果連結串列為空
        if self.is_empty():
            # 直接將頭節點的next新增node
            self.head = node
        else:
            # 範例化一個遊標
            cur = self.head
            while cur.next != None:
                # 移動遊標，得到最後一個遊標的資料
                cur = cur.next
            # 將移動後的資料的下一個next新增上 node
            cur.next=node
            pass

    def travel(self):
        """遍歷資料"""
        # 範例化一個遊標
        cur = self.head
        # 資料鏈為空的情況
        if self.is_empty():
            print('')
        else:
            # 獲取每個資料區中的資料
            # 移動遊標，每移動一次，輸出一次資料區內的資料
            while cur != None:
                print(cur.item, end=' ')
                cur = cur.next
            print()

    def length(self):
        """返回連結串列的長度"""
        # 範例化遊標
        cur = self.head
        # 計數，這裡對空連結串列進行判斷，如果是連結串列，則不會進入迴圈，直接輸出 0
        count = 0
        # 移動遊標，獲取下一個資料，然後讓count +=1
        while cur != None:
            # 計數
            count+=1
            # 移動遊標
            cur = cur.next
        return count

    def add(self, item):
        """
        頭部新增資料
        分析： 將資料新增到第一個節點當中
        1、 需要先將node的next指向 原第一個節點，這原第一個節點就是self.head
        2、 再講self.head指向node進行連線
        """
        # 先範例化節點
        node = Node(item)
        # 將資料新增到頭部當中
        node.next=self.head
        self.head=node

    def insert(self, index, item):
        """
        指定位置新增資料
        分析：
        1、首先要找到，該位置的資料
        2、將要新增的資料next等於 原位置的next資料
        3、原資料的 next等於node新資料
        """
        if index<=0:
            # 如果輸入的索引小於或者等於O，預設使用頭插發
            self.add(item)
        elif index>self.length():
            # 如果輸入的索引大於連結串列的長度,使用尾插法
            self.append(item)
        else:
            # 範例化資料節點
            node = Node(item)
            # 找到該資料的位置
            # 範例化一個遊標
            cur = self.head
            # 計數
            conent = 0
            while conent<(index-1):
                conent+=1
                cur = cur.next

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

    def search(self, item):
        """
        查詢指定的資料是否存在
        分析： 查詢指定的資料，需要對整個連結串列掃描，判斷這個資料是否等的該節點中的資料
        """
        # 範例化一個遊標
        cur = self.head
        # 進行判斷是否相等
        while cur != None:
            # 判斷
            if cur.item == item:
                return True
            else:
                cur = cur.next
            pass
        # 否則返回False
        return False

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

        """
        # 先找到該資料
        cur = self.head
        por = None

        while cur != None:
            if cur.item==item:
                # 要判斷是否為第一個節點
                if cur == self.head:
                    self.head = cur.next
                else:
                    por.next = cur.next
                break
            else:
                # 如果在當前節點中沒有相等的，將節點進行移動
                # 移動要注意，現將兩個遊標相等，再講另一個遊標移動一次
                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