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 reverse_display(self):
        self.helper_reverse_display(self.head)

    def helper_reverse_display(self, curr):
        if curr is None:
            return

        self.helper_reverse_display(curr.next)
        print(curr.data)

my_instance = my_linked_list()
n = int(input('How many elements you wish to add ? '))
for i in range(n):
    data = int(input('Enter the data item : '))
    my_instance.add_value(data)

print('The reversed linked list is: ')
my_instance.reverse_display()

出力結果

How many elements you wish to add ? 4
Enter the data item : 21
Enter the data item : 34
Enter the data item : 56
Enter the data item : 68
The reversed linked list is:
68
56
34
21

コードの解説

• まず、ノードを表す「Node」クラスを作成します。

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

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

• 「add_value」メソッドは、リンクリストの末尾に新しいデータを追加するために使用します。

• 「reverse_display」メソッドは、リンクリストの内容をコンソールに逆順で表示するための入り口となるメソッドです。

• 再帰処理を行うために、ヘルパー関数「helper_reverse_display」を別途定義しています。

• 「reverse_display」からヘルパー関数が呼び出され、ヘルパー関数は自分自身を再帰的に呼び出しながら処理を進めます。

• 再帰呼び出しはリストの末尾（None）に到達すると停止し、呼び出し元へ戻りながら各ノードのデータを順に出力します。これにより、特別な反転処理を書かずとも自然に逆順表示が実現できます。

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

• ユーザーから追加する要素の個数を入力として受け取ります。

• forループで指定された回数だけ反復処理を行い、各データ項目をリンクリストに追加していきます。

• 最後に「reverse_display」メソッドを呼び出し、逆順に並べられたリンクリストをコンソールに表示します。

補足：再帰処理のポイント

このプログラムでは、再帰呼び出しがリストの末尾に到達した後、スタックを巻き戻すタイミングで print 文が実行されるため、逆順の出力が得られます。ただし、要素数が非常に多い場合は再帰の深さが増し、Python の再帰上限（デフォルトで約1000回）に達する可能性がある点には注意してください。そのようなケースでは、ループによる反転処理やスタックの活用を検討するとよいでしょう。