再帰を使って連結リスト内の交互ノードを出力する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):
        self.alternate_helper_fun(self.head)

    def alternate_helper_fun(self, curr):
        if curr is None:
            return
        print(curr.data, end = ' ')
        if curr.next:
            self.alternate_helper_fun(curr.next.next)

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 :78 56 34 52 71 96 0 80
The alternate elements in the linked list are :
78 34 71 0

コードの解説

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

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

• 「__init__」関数では、先頭ノードを表す「head」と末尾ノードを表す「last_node」を「None」で初期化します。

• 「add_value」メソッドは、連結リストの末尾に新しいデータを追加するために定義されています。

• 「print_it」メソッドは、リスト全体を反復処理しながらすべての要素を表示します。

• 「alternate_nodes」メソッドは、後述のヘルパー関数を呼び出すためのエントリポイントとして機能します。

• ヘルパー関数「alternate_helper_fun」は、連結リストを走査し、交互のインデックス（1つおき）に存在する要素を表示します。

• この関数は再帰的に定義されており、自身を繰り返し呼び出すことでリストの末尾まで処理を進めます。

• 具体的には、現在のノードの値を出力した後、「curr.next.next」を引数として自身を呼び出すことで、1つ飛ばしで次のノードへ移動しています。

• 「my_linked_list」クラスのオブジェクトを生成し、ユーザーからの入力を受け取って各要素をリストに追加します。

• 最後に「alternate_nodes」メソッドを呼び出すことで、交互の要素がコンソールに出力されます。