再帰を使わずに連結リスト（リンクリスト）の長さを求めるPythonプログラム

はじめに

再帰処理を使わずに連結リスト（リンクリスト）の長さを求める場合、まず「要素をリンクリストへ追加するメソッド」と「リンクリストの長さを計算するメソッド」を定義しておく必要があります。

本記事では、反復処理（whileループ）によって長さをカウントするシンプルな手法を紹介します。以下にその実装例を示します。

サンプルコード

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):
        curr = self.head
        length_val = 0
        while curr:
            length_val = length_val + 1
            curr = curr.next
        return length_val

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 34 12 56 86 32 99 0 6
The length of the linked list is 8

コードの解説

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

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

• このクラスには初期化用の「__init__」関数があり、先頭ノードを表す「head」と末尾ノードを表す「last_node」を「None」で初期化します。

• 「add_value」メソッドは、リンクリストの末尾に新しいデータを追加するために定義されています。末尾ノードを追跡することで、毎回先頭から走査せずに済むため、追加操作が効率的に行えます。

• 「calculate_length」メソッドは、先頭ノードから順に「next」をたどりながらカウンターを増やし、リンクリスト全体の長さを求めます。

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

• input()関数でユーザーから要素を入力として受け取り、空白区切りで分割してリンクリストの要素として扱います。

• forループ内で各要素を整数に変換し、「add_value」メソッドを呼び出してリンクリストへ順番に追加していきます。

• 最後に「calculate_length」メソッドを呼び出してリストの長さを取得します。

• その結果がコンソールに出力されます。

ポイント

この方法では再帰呼び出しを行わず、whileループによる反復処理だけでリンクをたどるため、スタックオーバーフローの心配がなく、非常に大きなリストでも安全に動作します。計算量はリストの要素数 n に対して O(n) となり、空間計算量は O(1) と効率的です。再帰版と比較すると、深いネストによるPythonの再帰上限（デフォルトで約1000回）に制限されない点が大きなメリットです。