python單向循環鏈表如何實現

本篇內容主要講解“python單向循環鏈表如何實現”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“python單向循環鏈表如何實現”吧!

單向循環鏈表

將所有的鏈接在一起，每一個節點分為數據存儲區和鏈接區，數據區存儲數據，鏈接區鏈接下一個節點

item： 存儲數據的地方
next： 鏈接下一個節點
注意： 單向循環鏈表是首位鏈接，即尾部的節點要和頭部的節點鏈接

單向鏈表操作

1、鏈表是否為空
2、鏈表的長度
3、遍歷鏈表
4、鏈表頭部添加元素
5、鏈表尾部添加元素
6、鏈表指定位置添加元素
7、鏈表刪除節點
8、查找節點是否存在

代碼實現

# 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

到此，相信大家對“python單向循環鏈表如何實現”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！