C++で再帰を使ったリンクリストへの挿入と走査の実装方法

整数値が与えられ、それらを使って連結リスト（リンクリスト）を構築します。ここでの課題は、再帰的なアプローチを用いて、まず単方向連結リストの末尾にノードを挿入し、その後リスト全体を走査（トラバース）して表示することです。

再帰による末尾へのノード追加

• headがNULLの場合 → 新しいノードをheadとして追加する

• それ以外の場合 → head->nextに対して再帰的に追加処理を呼び出す

再帰によるノードの走査

• headがNULLの場合 → NULLを出力して終了する

• それ以外の場合 → 現在のデータを出力し、head->nextに対して再帰的に走査を続ける

実行例

入力：1 - 2 - 7 - 9 - 10

出力：連結リスト：1 → 2 → 7 → 9 → 10 → NULL

入力：12 - 21 - 17 - 94 - 18

出力：連結リスト：12 → 21 → 17 → 94 → 18 → NULL

プログラムで使用するアプローチ

このアプローチでは、ノードを追加する関数とリストを走査する関数をそれぞれ定義し、次のノードに対して自分自身を再帰的に呼び出すことで処理を実現します。

• 整数型のdataメンバと、次ノードへのポインタSLLNode* nextを持つ構造体SLLNodeを定義します。

• 関数addtoEnd(SLLNode* head, int data)は、リストの先頭ポインタと挿入するデータを受け取り、連結リストの末尾にノードを追加します。

• headポインタがNULLの場合、リストは空であるため、新しいノードを作成してheadとして設定します。head->nextにはNULLを代入し、このノードへのポインタを返します。

• headがNULLでない場合は、head->next = addtoEnd(head->next, data)のように再帰呼び出しを行い、リストの末尾まで辿ってからノードを追加します。

• 関数traverseList(SLLNode* head)は、headから走査を開始し、各ノードの値を出力します。

• headがNULLの場合は「NULL」を出力して処理を終了します。

• それ以外の場合は現在のdataを出力し、traverseList(head->next)を呼び出して次のノードへ進みます。

• main関数内ではaddtoEnd()を使ってリストを構築し、traverseList()を使ってリスト全体を表示します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
struct SLLNode {
    int data;
    SLLNode* next;
};
SLLNode* addtoEnd(SLLNode* head, int data){
    if (head == NULL){
        SLLNode *nodex = new SLLNode;
        nodex->data = data;
        nodex->next = NULL;
        return nodex;
    }
    else{
        head->next = addtoEnd(head->next, data);
    }
    return head;
}
void traverseList(SLLNode* head){
    if (head == NULL){
        cout << "NULL";
        return;
    }
    cout << head->data << " -> ";
    traverseList(head->next);
}
int main(){
    SLLNode* head1 = NULL;
    head1 = addtoEnd(head1, 1);
    head1 = addtoEnd(head1, 8);
    head1 = addtoEnd(head1, 56);
    head1 = addtoEnd(head1, 12);
    head1 = addtoEnd(head1, 34);
    cout<<"Linked List is :"<<endl;
    traverseList(head1);
    return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

Linked List is :
1 -> 8 -> 56 -> 12 -> 34 -> NULL