【Python】双方向連結リストから最大値・最小値のノードを検索する方法

双方向連結リスト（Doubly Linked List）から最大値と最小値を求める必要がある場合、まず「Node」クラスを作成します。このクラスには3つの属性を持たせます。ノードが保持するデータ、連結リスト上の次のノードへの参照、そして前のノードへの参照です。

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

サンプルコード

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

class double_list:
    def __init__(self):
        self.head = None
        self.tail = None

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

    def min_node(self):
        curr = self.head
        if(self.head == None):
            print("The list is empty")
            return 0
        else:
            minimum = self.head.data
            while(curr != None):
                if(minimum > curr.data):
                    minimum = curr.data
                curr = curr.next
            return minimum

    def max_node(self):
        curr = self.head
        if(self.head == None):
            print("The list is empty")
            return 0
        else:
            maximum = self.head.data
            while(curr != None):
                if(curr.data > maximum):
                    maximum = curr.data
                curr = curr.next
            return maximum

    def print_it(self):
        curr = self.head
        if (self.head == None):
            print("The list is empty")
            return
        print("The nodes in the doubly linked list are :")
        while curr != None:
            print(curr.data)
            curr = curr.next

my_instance = double_list()
print("Elements are being added to the doubly linked list")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
my_instance.add_data(77)
my_instance.add_data(92)
my_instance.print_it()
print("The node with maximum value is : ")
print(my_instance.max_node())
print("The node with minimum value is : ")
print(my_instance.min_node())

実行結果

Elements are being added to the doubly linked list
The nodes in the doubly linked list are :
10
24
54
77
92
The node with maximum value is :
92
The node with minimum value is :
10

処理の流れと解説

• まず「Node」クラスを作成します。
• 続いて、必要な属性を持つ「double_list」クラスを作成します。
• 「add_data」メソッドを定義し、双方向連結リストの末尾にデータを追加できるようにします。
• 「print_it」メソッドを定義し、連結リスト内のすべてのノードを順番に表示します。
• 「max_node」メソッドを定義し、双方向連結リスト内の最大値を検索します。
• 「min_node」メソッドを定義し、双方向連結リスト内の最小値を検索します。
• 「__init__」メソッドでは、headノードとtailノードをNoneに初期化します。
• 「double_list」クラスのインスタンスを生成し、各メソッドを呼び出してノードの最大値と最小値を求めます。
• リストを先頭から順に走査しながら各ノードの値を比較することで、最大値と最小値を特定できます。
• 最後に、結果をコンソールに出力して確認します。

計算量について

max_nodeメソッドおよびmin_nodeメソッドは、リスト全体を一度だけ走査するため、時間計算量はO(n)です（nは連結リスト内のノード数）。また、リストが空の場合には「The list is empty」というメッセージを表示し、0を返すようになっています。双方向連結リストは前後両方向へのポインタを持つため、挿入や削除が柔軟に行える一方、ランダムアクセスには向かないという特徴があります。