Python如何實現環形鏈表

Python如何實現環形鏈表

環形鏈表是一種特殊的鏈表結構，其中鏈表的最后一個節點指向鏈表中的某個節點，形成一個環。與普通鏈表不同，環形鏈表沒有明確的末尾節點。環形鏈表在某些場景下非常有用，例如在實現循環隊列、約瑟夫問題等算法時。

本文將介紹如何使用Python實現環形鏈表，并探討其基本操作。

1. 環形鏈表的基本概念

在環形鏈表中，每個節點包含兩個部分： - 數據域：存儲節點的數據。 - 指針域：指向下一個節點的指針。

與普通鏈表不同的是，環形鏈表的最后一個節點的指針域指向鏈表中的某個節點，而不是None。這個節點可以是鏈表的頭節點，也可以是鏈表中的任意一個節點。

2. 環形鏈表的實現

2.1 定義節點類

首先，我們需要定義一個節點類Node，用于表示鏈表中的每個節點。每個節點包含數據域和指針域。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

2.2 定義環形鏈表類

接下來，我們定義一個環形鏈表類CircularLinkedList，用于管理鏈表的各種操作。

class CircularLinkedList:
    def __init__(self):
        self.head = None

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

    def append(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def prepend(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head
            self.head = new_node

    def delete(self, data):
        if self.is_empty():
            return

        current = self.head
        prev = None

        while True:
            if current.data == data:
                if prev is not None:
                    prev.next = current.next
                    if current == self.head:
                        self.head = current.next
                else:
                    if current.next == self.head:
                        self.head = None
                    else:
                        self.head = current.next
                        temp = self.head
                        while temp.next != current:
                            temp = temp.next
                        temp.next = self.head
                return
            prev = current
            current = current.next
            if current == self.head:
                break

    def display(self):
        if self.is_empty():
            print("Circular Linked List is empty")
            return

        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("(head)")

2.3 基本操作

2.3.1 插入節點

• 在鏈表末尾插入節點：使用append方法在鏈表的末尾插入一個新節點。
• 在鏈表頭部插入節點：使用prepend方法在鏈表的頭部插入一個新節點。

2.3.2 刪除節點

• 刪除指定數據的節點：使用delete方法刪除鏈表中第一個匹配指定數據的節點。

2.3.3 顯示鏈表

• 顯示鏈表內容：使用display方法遍歷并打印鏈表中的所有節點。

3. 示例代碼

下面是一個使用環形鏈表的示例代碼：

if __name__ == "__main__":
    cll = CircularLinkedList()
    cll.append(1)
    cll.append(2)
    cll.append(3)
    cll.prepend(0)
    cll.display()  # 輸出: 0 -> 1 -> 2 -> 3 -> (head)

    cll.delete(2)
    cll.display()  # 輸出: 0 -> 1 -> 3 -> (head)

4. 總結

環形鏈表是一種特殊的鏈表結構，適用于需要循環訪問數據的場景。通過Python實現環形鏈表，我們可以輕松地進行節點的插入、刪除和遍歷操作。掌握環形鏈表的實現有助于理解更復雜的數據結構和算法。

在實際應用中，環形鏈表可以用于實現循環隊列、約瑟夫問題等算法。希望本文對你理解和使用環形鏈表有所幫助！