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 calculate_length(self):
        return self.length_helper_fun(self.head)

    def length_helper_fun(self, curr):
        if curr is None:
            return 0
        return 1 + self.length_helper_fun(curr.next)

my_instance = my_linked_list()
my_data = input('Enter elements of the linked list ').split()
for elem in my_data:
    my_instance.add_value(int(elem))
print('The length of the linked list is ' + str(my_instance.calculate_length()))

実行結果

Enter elements of the linked list 12 45 32 67 88 0 99
The length of the linked list is 7

コードの解説

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

• 続いて、必要な属性を持つ「my_linked_list」クラスを定義します。

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

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

• 「calculate_length」メソッドは、後述のヘルパー関数を呼び出してリンクリストの長さを取得します。

• ヘルパー関数「length_helper_fun」は、再帰処理を行うために定義されています。

• この関数は現在のノードがNoneかどうかを判定し、Noneであれば0を返します。それ以外の場合は「1 + 次のノードの再帰結果」を返すことで、リスト全体の長さを算出します。

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

• input関数でユーザーから連結リストの要素をスペース区切りで受け取ります。

• ループ処理で各要素をadd_valueメソッドによりリストへ追加していきます。

• 最後にcalculate_lengthメソッドを呼び出し、計算された長さをコンソールに出力します。

再帰処理のポイント

このアルゴリズムでは、ベースケースとして「現在のノードがNone（リストの終端）」を設定し、そこに到達した時点で再帰を停止します。各呼び出しごとに1を加算していくことで、ノードの総数が求まります。

なお、この再帰版の計算量はO(n)、空間計算量も再帰スタックの深さ分だけ必要となるためO(n)となります。非常に長いリストを扱う場合は、Pythonの再帰上限（デフォルトで約1000回）に注意が必要です。そのようなケースでは、while文を使った反復処理の方が安全です。