C++でソート済み単方向リンクリストを実装する方法【アルゴリズムとサンプルコード付き】

リンクリスト（連結リスト）とは

データ構造におけるリンクリスト（連結リスト）とは、データ要素を線形につなげたコレクションです。リストの各要素（ノード）は、「データ本体」と「次のノードへの参照」という2つの項目で構成されており、末尾のノードはnullを参照します。また、リストへの入り口となる先頭ノードは「ヘッド（head）」と呼ばれます。

単方向リンクリストでは、各ノードは自分の内容と、リスト内の次のノードへのポインタ（参照）だけを保持します。前のノードを指すポインタは持たないため、逆方向へたどれない点が双方向リンクリストとの大きな違いです。

この記事では、ノードを挿入するたびに自動的に昇順へ並び替えられる「ソート済み単方向リンクリスト」をC++で実装する方法を、アルゴリズム・サンプルコード・実行結果とともに解説します。

アルゴリズム

Begin
    関数 createnode()：リストへノードを挿入する
        リストが空かどうかを判定する。
        空の場合は、そのノードを先頭要素として配置し、head を更新する。
        next ポインタを NULL で初期化する。
        リストが空でない場合は、
        新しいノード（newnode）を生成し、そのデータフィールドに値を格納する。
        newnode は、リンクリストが常にソートされた状態を保てる位置に挿入される。
        末尾に挿入された場合は、newnode は NULL を指す。
        先頭に挿入された場合は、そこがリンクリストの起点となる。
End

Begin
    関数 display()：n 個のノードを持つリストの内容を出力する
        c = 0 を初期化する。
        ポインタ変数を先頭アドレスで初期化する。
        while (c <= n)
            ノードの情報を出力する
            ポインタ変数を更新する
            c をインクリメントする
End

サンプルコード

#include<iostream>
using namespace std;
struct nod {
    int d;
    nod *n;
}
*p = NULL, *head = NULL, *q = NULL, *np = NULL;
int c = 0;
void createnode(int n) {
    np = new nod;
    np->d = n;
    np->n = NULL;
    if (c == 0) {
        head = np;
        p = head;
        p->n = head;
        c++;
    } else if (c == 1) {
        p = head;
        q = p;
        if (np->d < p->d) {
            np->n = p;
            head = np;
            p->n = np;
        } else if (np->d > p->d) {
            p->n = np;
            np->n = head;
        }
        c++;
    } else {
        p = head;
        q = p;
        if (np->d < p->d) {
            np->n = p;
            head = np;
            do {
                p = p->n;
            }
            while (p->n != q);
            p->n = head;
        } else if (np->d > p->d) {
            while (p->n != head && q->d < np->d) {
                q = p;
                p = p->n;
                if (p->n == head) {
                    p->n = np;
                    np->n = head;
                } else if (np->d < p->d) {
                    q->n = np;
                    np->n = p;
                    break;
                }
            }
        }
    }
}
void display(int i) {
    nod *t = head;
    int c = 0;
    while (c <= i ) {
        cout<<t->d<<"\t";
        t = t->n;
        c++;
    }
}
int main() {
    int i = 0, n, a;
    cout<<"enter the no of nodes\n";
    cin>>n;
    while (i < n) {
        cout<<"\nenter value of node\n";
        cin>>a;
        createnode(a);
        i++;
    }
    cout<<"sorted singly link list"<<endl;
    display(n);
}

実行結果

enter the no of nodes
5
enter value of node
6
enter value of node
4
enter value of node
7
enter value of node
3
enter value of node
2
sorted singly link list
2 3 4 6 7 2

コードのポイント

createnode() 関数は、挿入する値を既存ノードと順に比較しながら適切な位置を探し、先頭・中間・末尾のいずれかにノードを挿入します。これにより、値をどのような順序で入力しても、リスト全体が常に昇順にソートされた状態に保たれます。

なお、この実装では末尾ノードの next が head を指して戻る（環状になる）構造になっており、display() のループ条件が c <= i となっているため、出力例のように先頭の値が最後にもう一度表示されます。純粋な単方向リンクリストとして扱いたい場合は、ループ条件を c < i に変更するなど、用途に応じた調整を行ってください。