python單向迴圈連結串列範例詳解

# 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