C++で連結リストの長さを求める方法（反復処理と再帰処理の両アプローチ）

この記事では、反復（イテレーティブ）と再帰（リカーシブ）という2つの異なるアプローチを用いて、C++で連結リストの長さを求める方法を詳しく解説します。リストの先頭ポインタが与えられている場合、以下の手順に従うことでノード数を正確に取得できます。

反復アプローチの手順

• リストの先頭ノードから処理を開始します。
• 現在のポインタがNULLでない間、次のノードへ移動し、そのたびにカウントを1増やしていきます。
• ポインタがNULLになった時点でのカウント値が、リスト全体の長さとなります。

再帰アプローチの手順

• 先頭ノードを引数として関数に渡します。
• 基本条件（ベースケース）は「引数がNULLの場合は0を返す」ことです。
• それ以外の場合は、現在のノードの次のノードを引数として自分自身を再帰的に呼び出します。
• 戻り値は「1 + 部分リストの長さ」となり、これによって全体のノード数が計算されます。

コード例

#include<iostream>
using namespace std;
class Node {
    public:
        int data;
    Node* next;
};
void append(struct Node** start, int data) {
    struct Node* new_node = new Node;
    new_node->data = data;
    new_node->next = (*start);
    (*start) = new_node;
}
int count_recursive(Node* start) {
    if (start == NULL)
        return 0;
    return 1 + count_recursive(start->next);
}
int count_iterative(Node* start) {
    int count = 0;
    Node* current = start;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}
int main() {
    Node* start = NULL;
    append(&start, 1);
    append(&start, 3);
    append(&start, 1);
    append(&start, 2);
    append(&start, 1);
    cout << "Node count using iterative approach: " << count_iterative(start) << endl;
    cout << "Node count using recursion: " << count_recursive(start);
}

実行結果

Node count using iterative approach: 5
Node count using recursion: 5

両アプローチの比較

どちらの手法も時間計算量は O(n) で同じですが、空間計算量に違いがあります。

• 反復アプローチ： 空間計算量は O(1)。追加のメモリをほとんど消費せず、スタックオーバーフローの心配がないため、大きなリストに対しても安全に使えます。
• 再帰アプローチ： 呼び出しスタックを使用するため、空間計算量は O(n)。コードは簡潔で読みやすい反面、リストが非常に長い場合はスタックオーバーフローを引き起こすリスクがある点に注意が必要です。

実務では安全性と効率の観点から反復アプローチが推奨されることが多いですが、再帰の考え方を理解しておくことは、木構造などより複雑なデータ構造を扱う際にも役立ちます。