Python中的環型鏈表是一種循環數據結構,可以在鏈表的末尾鏈接回到鏈表的頭部,形成一個環狀鏈表。
創建一個Python環型鏈表,我們先要定義一個節點類,該類包括節點值和指向下一個節點的指針。
class Node: def __init__(self, value): self.value = value self.next = None
接下來,我們需要定義一個環型鏈表類。該類需要保存頭節點和尾節點,并提供添加節點、刪除節點、查找節點等操作。
class CircularLinkedList: def __init__(self, head=None): self.head = head self.tail = None def add_node(self, node): if self.head is None: self.head = node self.head.next = self.head self.tail = self.head else: node.next = self.head self.tail.next = node self.tail = node def delete_node(self, node): if self.head == node: self.head = node.next self.tail.next = self.head node.next = None else: current = self.head while current.next != self.head: if current.next == node: current.next = node.next node.next = None break current = current.next def find_node(self, value): current = self.head while current is not None and current.value != value: if current.next == self.head: break current = current.next return current if current.value == value else None
上述代碼中,我們把頭節點和尾節點都初始化為None,若沒有頭節點時,添加的節點即為頭節點,并讓該節點的指針指向自己。若鏈表中已有其他節點,我們讓新加入的節點指向頭節點,尾節點的指針指向該節點。刪除節點時,如果是頭節點,我們需要把尾節點的指針指向新的頭節點,否則需要在鏈表中找到要刪除的節點并刪除。查找節點時,我們遍歷鏈表,直到遇到頭節點或找到節點的值相等時退出循環。
在Python中,我們可以創建一個環型鏈表并測試其操作:
linked_list = CircularLinkedList() linked_list.add_node(Node(1)) linked_list.add_node(Node(2)) linked_list.add_node(Node(3)) assert linked_list.find_node(2).value == 2 linked_list.delete_node(linked_list.find_node(2)) assert linked_list.find_node(2) is None
上述代碼中,我們先添加三個節點到鏈表中,然后使用find_node方法查找值為2的節點,結果應該是2。接下來,我們刪除值為2的節點,并使用find_node方法再次查找該節點,結果應該為None。
這是Python環型鏈表的基本功能,我們可以結合其他數據結構和算法,如快慢指針、雙向鏈表等來實現更為復雜的操作。