リンクリスト

スポンサーリンク
スポンサーリンク
ライフスタイル関連のコンテンツ
お金 | 仕事 | 勉強 | プライベート | 健康 |
プログラミング関連のコンテンツ
C言語/C++入門 | Ruby入門 | Python入門 | プログラミング全般

リンクリストとは、配列よりもより柔軟なデータ構造です。
各項目が次の項目をポイントするという風に、項目が数珠繋ぎになったデータ構造のことを指します。
リンクリストのデータ構造をクラス宣言で表すと・・・

スポンサーリンク

#include <iostream>
#include <string>
 
class linklist {
public:
    class linklist_elem {
    public:
        std::string data;    // この要素のデータ
    private:
        linklist_elem *next_ptr;    // 次の要素へのポインタ
 
        friend class linklist;
    };
 
public:
    linklist_elem *first_ptr;    // リストの最初の項目
 
    // リンクリストの初期化。コンストラクタ
    linklist() {first_ptr = NULL;}
 
    // 要素を先頭に追加
    void add(const std::string& item);
 
    // 要素を検索
    bool find(const std::string& data);
};

となります。
リンクリストの先頭に要素を追加する場合の関数は・・・

void linklist::add(const std::string& item) {
    // リストの次の要素へのポインタ
    // 新しく挿入する要素を作成
    linklist_elem *new_ptr;
    new_ptr = new linklist_elem;
    
    // 新しい要素に項目を格納
    (*new_ptr).data = item;
    // 新しい要素に現時点の先頭の要素をポイントさせる
    (*new_ptr).next_ptr = first_ptr;
    // first_ptrに新しい要素をポイントする
    first_ptr = new_ptr;
}

と書くことで、リンクリストの先頭に、要素を追加できます。
また、要素を検索し、該当する要素があれば、trueを返す関数は以下の通り。
リンクリストに要素を追加する前にチェックを行うために用います。

bool linklist::find(const std::string& data) {
    // 検索対象となるデータ構造
    linklist_elem *current_ptr;
    // 現在の要素を先頭の要素に設定
    current_ptr = first_ptr;
    while (current_ptr != NULL) {
        // dataを検索し見つかったらbreak
        if (current_ptr->data == data)
            break;
 
        // 次の要素へ
        current_ptr = current_ptr->next_ptr;
    }
 
    // current_ptrがNULLの場合は、リストの最後まで到達しdataが見つからなかった
    return (current_ptr != NULL);
}
スポンサーリンク
 
スポンサーリンク