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