C++で実装するソート済み循環単方向リンクリスト｜アルゴリズムとサンプルコードを解説

データ構造におけるリンクリスト（連結リスト）とは、データ要素を線形につなぎ合わせたコレクションのことです。リストの各要素（ノード）は「データ本体」と「次のノードへの参照（ポインタ）」という2つの情報で構成され、最後のノードは null を参照します。また、リストへの入り口となる先頭ノードは「ヘッド（head）」と呼ばれます。

単方向リンクリストでは、各ノードは自分の内容と次のノードへのポインタだけを持ちます。前のノードを指すポインタは保持しないため、リストの走査は基本的に先頭から一方向に行われます。

本記事で扱うのはソート済み循環単方向リンクリストです。これは、要素が常に昇順に並ぶよう管理されるうえ、末尾のノードが再び先頭（ヘッド）を指すことで環状構造になったリンクリストです。

以下に、このソート済み循環単方向リンクリストをC++で実装するプログラムを紹介します。

アルゴリズム

Begin
　　関数 createnode()：リストへノードを挿入する
　　　　リストが空かどうかを確認する。空の場合は、そのノードを最初の要素として登録し、head を更新する。
　　　　リストが空でない場合は、
　　　　新しいノード newnode を生成し、そのデータフィールドに値を格納する。
　　　　リンクリストが常にソートされた状態を保てるように、newnode を適切な位置へ挿入する。
　　　　末尾に挿入した場合は、newnode が head を指すようにする。
　　　　先頭に挿入した場合は、そこがリンクリストの起点となる。
End
Begin
　　関数 display()：n 個のノードを持つリストの内容を出力する
　　　　c = 0 で初期化する。
　　　　ポインタ変数を先頭アドレスで初期化する。
　　　　while (c <= n)
　　　　　　ノードの情報を出力する
　　　　　　ポインタ変数を更新する
　　　　　　c を1増やす
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 circularly 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 circularly singly link list
2 3 4 6 7 2

実装のポイント

• 先頭への挿入： 新しい値が現在のヘッドの値より小さい場合、新ノードが新しいヘッドになります。循環リストなので、末尾ノードの next ポインタを付け替えて新しいヘッドを指す必要があります。
• 中間・末尾への挿入： ヘッドより大きい値の場合は、挿入位置が見つかるまでリストを順にたどります。適切な位置が見つかればその間に挿入し、見つからなければ末尾に追加してヘッドへの参照を張ります。
• 計算量： 挿入のたびに挿入位置を線形探索で探すため、時間計算量は O(n) となります。
• 表示： display() はノード数 + 1 回ループするため、出力の最後にもう一度先頭の値が現れます。上記の出力例でも末尾に「2」が再登場しており、リストが循環していることが確認できます。