C++で単一連結リスト（片方向リンクリスト）から特定の要素を検索する方法

単一連結リスト（片方向リンクリスト）が与えられたとき、その中から特定の要素を検索するのが本記事のテーマです。要素が見つかった場合は「Present」、見つからなかった場合は「Not Present」を出力します。

入力例1

1→ 2→ 3→ 4→ 5→ 6

「7」を検索する場合

出力

Not Present

解説： 与えられた単一連結リストの中に「7」は存在しないため、「Not Present」を返します。

入力例2

1→ 2→ 3→ 4→ 5

「2」を検索する場合

出力

Present

解説： 与えられた単一連結リストの中に「2」が存在するため、「Present」を返します。

この問題を解くアプローチ

単一連結リスト内の特定の要素を検索するには、大きく分けて2つのアプローチがあります。ひとつは再帰的に要素の存在を確認する方法、もうひとつはループを使って反復的に確認する方法です。

再帰的なアプローチでは、リンクリストが空であればfalseを返し、現在のノードのデータ値が検索対象の要素と一致すればtrueを返します。反復的なアプローチでは、先頭ポインタから順に各ノードの値と比較していき、一致するかどうかに応じてtrueまたはfalseを返します。

• 入力を受け取り、ノードを挿入して単一連結リストを初期化します。

• ブール型の再帰関数 searchRecursive(node* head, int element) は、リンクリストの先頭ポインタと検索対象のキー要素を引数として受け取ります。

• まず、先頭ポインタがNULL（リンクリストが空）である場合はfalseを返します。

• 検索対象の要素が現在の先頭ノードのデータと一致する場合はtrueを返します。

• 一致しない場合は、次のノードを渡して同じ関数を再帰的に呼び出します。

なお、このアルゴリズムの時間計算量はO(n)、空間計算量はO(1)です（再帰呼び出しによるスタック消費を考慮するとO(n)）。リンクリストの長さに比例して処理時間が増加することに注意してください。

コード例

#include<iostream>
using namespace std;

class node{
public:
    int data;
    node* next;
    node(int d){
        data = d;
        next = NULL;
    }
};

void insertAt(node*& head, int data){
    node* n = new node(data);
    n->next = head;
    head = n;
}

bool searchRecursive(node* head, int key){
    if(head == NULL){
        return false;
    }
    if(head->data == key){
        return true;
    }
    else{
        return searchRecursive(head->next, key);
    }
}

void printNode(node* head){
    while(head != NULL){
        cout << head->data << "->";
        head = head->next;
    }
    cout << endl;
}

int main(){
    node* head = NULL;
    insertAt(head, 5);
    insertAt(head, 4);
    insertAt(head, 3);
    insertAt(head, 2);
    insertAt(head, 1);
    printNode(head);
    if(searchRecursive(head, 7)){
        cout << "Present" << endl;
    }
    else{
        cout << "Not Present" << endl;
    }
}

出力

上記のコードを実行すると、以下のような結果が出力されます。

1->2->3->4->5->
Not Present

与えられたリンクリスト 1→2→3→4→5 の中に要素「7」は存在しないため、「Not Present」が返されます。もし検索対象を「3」などリスト内に存在する値に変更すれば、「Present」と出力されることを確認できます。