【Python入門】双方向連結リストから最大値を見つける方法

双方向連結リスト（Doubly Linked List）の中で最も大きな要素を探す必要がある場合、以下の3つの機能を実装します。

• 連結リストに要素を追加するメソッド
• 連結リストの要素を出力・操作するための構造
• 連結リスト内の最大値を求めるメソッド

ここでは、「Node」クラスで各ノードを定義し、前後のノードへの参照（prev / next）を持たせることで、双方向にたどれる連結リストを構築します。その後、先頭から順に各ノードのデータを比較していくことで最大値を取得します。

サンプルコード

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

class DoublyLinkedList_structure:
    def __init__(self):
        self.first = None
        self.last = None

    def add_vals(self, data):
        self.insert_at_end(Node(data))

    def insert_at_end(self, newNode):
        if self.last is None:
            self.last = newNode
            self.first = newNode
        else:
            newNode.prev = self.last
            self.last.next = newNode
            self.last = newNode

def find_largest_val(my_list):
    if my_list.first is None:
        return None
    largest_val = my_list.first.data
    curr = my_list.first.next
    while curr:
        if curr.data > largest_val:
            largest_val = curr.data
        curr = curr.next
    return largest_val

my_instance = DoublyLinkedList_structure()

my_list = input('Enter the elements in the doubly linked list ').split()
for elem in my_list:
    my_instance.add_vals(int(elem))

largest_val = find_largest_val(my_instance)
if largest_val:
    print('The largest element is {}.'.format(largest_val))
else:
    print('The list is empty.')

実行結果

Enter the elements in the doubly linked list 45 12 67 89 234 567 888 44 999
The largest element is 999.

コードの解説

• まず「Node」クラスを作成します。このクラスはデータ（data）、次のノードへの参照（next）、前のノードへの参照（prev）の3つの属性を持ちます。

• 次に、必要な属性を持つ「DoublyLinkedList_structure」クラスを作成します。

• 「__init__」（イニシャライザ）関数では、先頭の要素（ヘッド）を「None」として初期化します。

• 「add_vals」メソッドを定義し、リストへ値を簡単に追加できるようにします。

• 「insert_at_end」メソッドを定義し、双方向連結リストの末尾に新しいノードを挿入できるようにします。リストが空の場合は、新規ノードが先頭かつ末尾になります。

• さらに「find_largest_val」関数を定義し、連結リスト全体を走査して最大値を検出します。最初のノードの値を初期値とし、残りのノードの値と順番に比較していきます。

• 「DoublyLinkedList_structure」クラスのインスタンスを生成します。

• ユーザーからの入力値を整数に変換しながら連結リストへ追加していきます。

• 「find_largest_val」メソッドを呼び出して最大値を取得します。

• 結果をコンソールに出力して表示します。リストが空の場合は、その旨のメッセージを表示します。

このアルゴリズムの計算量は O(n) であり、リストの長さに比例して処理時間が増加します。双方向連結リストは末尾への挿入が O(1) で行えるため、頻繁に要素を追加しながら最大値を求めたいケースにも効率的に対応できます。