再帰を使わずに連結リストの交互ノードを出力するPythonプログラム

連結リスト（リンクリスト）内の交互ノードを、再帰処理を使わずに出力したい場合があります。その際は、連結リストへ要素を追加するメソッド、連結リストの要素を表示するメソッド、そして連結リストから交互の値を取得するメソッドを定義します。

以下に実装例を示します。

サンプルコード

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

class my_linked_list:
    def __init__(self):
        self.head = None
        self.last_node = None

    def add_value(self, my_data):
        if self.last_node is None:
            self.head = Node(my_data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(my_data)
            self.last_node = self.last_node.next

    def print_it(self):
        curr = self.head
        while curr:
            print(curr.data)
            curr = curr.next

    def alternate_nodes(self):
        curr = self.head
        while curr:
            print(curr.data)
            if curr.next is not None:
                curr = curr.next.next
            else:
                break

my_instance = my_linked_list()
my_list = input("Enter the elements of the linked list :").split()
for elem in my_list:
    my_instance.add_value(elem)
print("The alternate elements in the linked list are :")
my_instance.alternate_nodes()

出力結果

Enter the elements of the linked list :56 78 43 51 23 89 0 6
The alternate elements in the linked list are :
56
43
23
0

解説

• まず「Node」クラスを作成します。このクラスはデータと次のノードへの参照を保持します。

• 必要な属性を持つ「my_linked_list」クラスを別途作成します。

• 「__init__」関数では、先頭ノードである「head」と最終ノード「last_node」を初期値「None」で初期化します。

• 「add_value」メソッドを定義し、連結リストの末尾に新しいデータを追加できるようにします。リストが空の場合はheadに設定し、そうでなければlast_nodeのnextに接続します。

• 「print_it」メソッドを定義し、リスト全体を走査してすべての要素を出力します。

• 「alternate_nodes」メソッドを定義し、連結リストを1つおきに走査して交互の位置にある要素のみを出力します。ここでは再帰を使わず、whileループとポインタの2回進める操作だけで実現しています。

• 「my_linked_list」クラスのオブジェクトを生成します。

• ユーザーから入力を受け取り、各要素を連結リストに追加した後、「alternate_nodes」メソッドを呼び出して交互インデックスの要素を取得します。

• 結果がコンソールに表示されます。

ポイント

再帰を使わないアプローチでは、現在のノードから「next.next」へ一度に2つ進むことで交互ノードを効率的に取得できます。これによりスタックオーバーフローのリスクを避けられ、長い連結リストでも安全に処理できます。計算量はO(n)、空間計算量はO(1)となります。