C++ 動的に連結リストを作成する

連結リストとは？

最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。
一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる。
連結リスト - Wikipedia

要するに、複数のデータを数珠つなぎに保持するデータ構造を「連結リスト」と呼びます。

C言語では、次のノードを指すポインタを定義した構造体を用意し、
数珠つなぎにするパターンが一般的です。

C++ でのサンプルプログラム

今回は、C++で連結リストを作成するサンプルプログラムを作成。

using namespace std;

struct RenketsuList {
    string key;
    RenketsuList *next;
};

int AddList(RenketsuList *&list)
{
    int ret = 0;

    list = new RenketsuList;
    if (list == nullptr)
    {
        cout << "No Memory.¥n";
        ret = -1;
    }

    list->next = nullptr;

    return ret;
}

void freeList(RenketsuList *&list)
{
    RenketsuList *tmp = list;
    RenketsuList *swap = nullptr;

    while(tmp)
    {
        swap = tmp->next;
        delete tmp;
        tmp = nullptr;
        tmp = swap;
    }
}

int main() {

    int ret = 0;

    cout << "Renketsu List Test Start!!" << endl;

    // テストデータ
    std::vector<std::string> keyList;
    keyList.push_back("Test01");
    keyList.push_back("Test02");
    keyList.push_back("Test03");

    RenketsuList *pList = nullptr;
    RenketsuList *pTmp = nullptr;
    bool isHead = true;

    // 連結リストを動的に作成するループ
    for(auto item : keyList)
    {

        if (isHead)
        {
            ret = AddList(pList);
            pTmp = pList;
        } else {
            ret = AddList(pTmp->next);
            pTmp = pTmp->next;
        }
        if (ret != 0)
        {
            // メモリ解放
            freeList(pList);
            return ret;
        }

        pTmp->key = item;

        if (isHead)
        {
            isHead = false;
        }
    }

    // データ確認
    int i = 0;
    RenketsuList *pChk = pList;
    while(pChk)
    {
        ++i;
        cout << i << "件目 key:" << pChk->key << endl;
        pChk = pChk->next;
    }

    // メモリ解放
    freeList(pList);

    cout << "Renketsu List Test End!!" << endl;

    return ret;
}