Pythonで循環リンクリストから最大値ノードと最小値ノードを検索する方法

循環リンクリスト（環状連結リスト）から最大値ノードと最小値ノードを検索する必要がある場合、まず「Node」クラスを作成します。このクラスには、ノードに格納されるデータと、リンクリストにおける次のノードへの参照という2つの属性が含まれます。

循環リンクリストでは、先頭（head）と末尾（tail）が互いに隣接しています。これらは円形になるように接続されており、通常のリンクリストと異なり、最後のノードに「NULL」が存在しません。

さらに、初期化関数を持つ別のクラスを作成し、ノードのheadを「None」で初期化します。

続いて、リンクリストへノードを追加するメソッド、ノード内の最小値・最大値を検索するメソッド、そして結果を表示するメソッドなど、複数のメソッドを定義していきます。

以下に具体的な実装例を示します。

サンプルコード

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

class list_creation:  
    def __init__(self):  
        self.head = Node(None)  
        self.tail = Node(None)  
        self.head.next = self.tail  
        self.tail.next = self.head 

    def add_data(self,my_data):  
        new_node = Node(my_data)  
        if self.head.data is None:  
            self.head = new_node  
            self.tail = new_node  
            new_node.next = self.head  
        else:  
            self.tail.next = new_node  
            self.tail = new_node  
            self.tail.next = self.head 

    def find_min_node(self):  
        curr = self.head
        min_val = self.head.data
        if(self.head == None):  
            print("The list is empty")
        else:  
            while(True):  
                if(min_val > curr.data):  
                    min_val = curr.data
                curr = curr.next
                if(curr == self.head):  
                    break
        print("Minimum value node in the list: "+ str(min_val))

    def find_max_node(self):  
        curr = self.head
        max_val = self.head.data
        if(self.head == None):  
            print("List is empty")
        else:  
            while(True):  
                if(max_val < curr.data):  
                    max_val = curr.data
                curr = curr.next
                if(curr == self.head):  
                    break
        print("The maximum valueed node is : "+ str(max_val))

class circular_linked_list:  
    my_cl = list_creation()
    print("Values have been added to the list")
    my_cl.add_data(11)  
    my_cl.add_data(52)  
    my_cl.add_data(36)  
    my_cl.add_data(74)  
    my_cl.find_max_node()
    my_cl.find_min_node()

出力

Values have been added to the list
The maximum valueed node is : 74
Minimum value node in the list: 11

コードの解説

• まず、ノードの構造を表す「Node」クラスを作成します。
• 次に、必要な属性を持つ「list_creation」クラスを作成します。
• 「__init__」メソッドでは、循環リンクリストの最初と最後のノードをNoneで初期化し、headとtailが互いを指すように設定します。
• 「add_data」メソッドは、循環リンクリストに新しいデータを追加するために使用されます。リストが空の場合は新ノードがhead兼tailとなり、自身を指すことで循環構造を形成します。
• 「find_max_node」メソッドは、リスト全体を走査し、各ノードの値を比較しながら最大値を取得します。
• 「find_min_node」メソッドも同様にリストを走査し、最小値を取得します。
• 走査は「curr」が再びheadに戻った時点で終了します。これが循環リンクリスト特有の終了条件です。
• 「list_creation」クラスのオブジェクトを生成し、メソッドを呼び出してデータ（11、52、36、74）を追加します。
• 最後に「find_max_node」と「find_min_node」を呼び出し、リスト内の最大値と最小値をコンソールに表示します。

このアルゴリズムの計算量はO(n)です。リスト内の全ノードを一度ずつ訪問するため、ノード数に比例した時間がかかります。空間計算量はO(1)であり、比較用の変数のみを使用するため効率的です。