C++でソート済み双方向リンクリストを実装するプログラムと解説

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

データ構造におけるリンクリスト（連結リスト）は、データ要素を線形に並べた集合です。リストの各要素（ノード）は「データ」と「次のノードへの参照（ポインタ）」という2つの項目で構成され、最後のノードはnullへの参照を持ちます。リンクリストへの入口となる先頭ノードは「ヘッド（head）」と呼ばれます。

双方向リンクリストとは

双方向リンクリスト（ダブルリンクリスト）は、ノードと呼ばれるレコードが順次連結されたデータ構造です。各ノードは3つのフィールドを持ちます。1つはデータフィールド、残りの2つはリンクフィールドで、それぞれノード列における「前のノード」と「次のノード」への参照を保持します。これにより、リストを前方向にも後ろ方向にもたどることができます。

ソート済み双方向リンクリスト

ソート済み双方向リンクリストでは、データフィールドの値に基づいて、リストが常にソートされた状態に保たれます。新しいノードを挿入する際には適切な位置を探索して挿入するため、リスト全体の順序が崩れることはありません。

アルゴリズム

始まり
    createnode() 関数：リストにノードを挿入する
        新しいノードを生成し、そのデータフィールドに数値を格納する。
        リストが空かどうかを判定する。空の場合は、そのノードを最初の要素として配置し、head を更新する。
        prev と next の両ポインタを NULL で初期化する。
        リストが空でない場合は、リスト全体がソートされた状態を保てるように、新しいノードを既存のリンクリストの適切な位置に挿入する。
        prev と next のポインタを適宜更新する。
終わり
始まり
    display_head() 関数：head からリストを表示する
        c = 0 で初期化する。
        ポインタ変数を head ノードのアドレスで初期化する。
        while (c <= i)
            ノードの情報を表示する
            ポインタ変数を更新する
            c をインクリメントする
終わり
始まり
    display_tail() 関数：tail からリストを表示する
        m = 0 で初期化する。
        ポインタ変数を tail ノードのアドレスで初期化する。
        while (m <= i)
            ノードの情報を表示する
            ポインタ変数を更新する
            m をインクリメントする
終わり

サンプルコード

以下は、C++でソート済み双方向リンクリストを実装したサンプルコードです。ノードを挿入するたびに適切な位置へ配置することで、リスト全体が常にソートされた状態に保たれます。

#include<iostream>
using namespace std;
struct nod {
   int d;
   nod *n, *p;
}
*p = NULL, *head = NULL, *r = NULL, *np = NULL, *tail = NULL;
int c = 0;
void createnode(int n) {
   np = new nod;
   np->d = n;
   np->n = NULL;
   np->p = NULL;
   if (c == 0) {
      tail = np;
      head = np;
      p = head;
      p->n = head;
      p->p = head;
      c++;
   } else if (c == 1) {
      p = head;
      r = p;
      if (np->d < p->d) {
         np->n = p;
         p->p = np;
         head = np;
         p->n = np;
         np->p = p;
         tail = p;
      } else if (np->d > p->d) {
         p->n = np;
         np->p = p;
         np->n= head;
         p->p = np;
      }
      c++;
   } else {
      p = head;
      r = p;
      if (np->d < p->d) {
         np->n = p;
         p->p = np;
         head = np;
         do {
            p = p->n;
         }
         while (p->n != r);
            tail = p;
            p->n = np;
            np->p = p;
      } else if (np->d > p->d) {
         while (p->n != head && np->d > p->d) {
            r = p;
            p = p->n;
            if (p->n == head && (p->d < np->d)) {
               p->n = np;
               np->p = p;
               np->n = head;
               tail = np;
               head->p = np;
               break;
            } else if (np->d< p->d) {
               r->n= np;
               np->p = r;
               np->n= p;
               p->p= np;
               if (p->n != head) {
                  do {
                     p = p->n;
                  }
                  while (p->n != head);
               }
               tail = p;
               break;
            }
         }
      }
   }
}
void display_head(int i) {
   nod *t = head;
   int c = 0;
   while (c <= i) {
      cout<<t->d<<"\t";
      t = t->n;
      c++;
   }
   cout<<endl;
}
void display_tail(int i) {
   nod *t = tail;
   int m = 0;
   while (m <= i) {
      cout<<t->d<<"\t";
      t = t->p;
      m++;
   }
   cout<<endl;
}
int main() {
   int i = 0, n, a, ch;
   cout<<"enter the no of nodes\n";
   cin>>n;
   while (i < n) {
      cout<<"\nenter value of node\n";
      cin>>a;
      createnode(a);
      i++;
   }
   cout<<"\nsorting Doubly Linked List head first\n";
   display_head(n);
   cout<<"\nsorting Doubly Linked List tail first\n";
   display_tail(n);
}

実行結果

enter the no of nodes
5
enter value of node
7
enter value of node
4
enter value of node
6
enter value of node
2
enter value of node
1
sorting Doubly Linked List head first
1 2 4 6 7 1
sorting Doubly Linked List tail first
7 6 4 2 1 7

このプログラムでは、head（先頭）から順に表示した結果と、tail（末尾）から逆順に表示した結果の両方を出力しています。なお、表示ループの条件が c <= i となっているため、要素数より1回多くループが回り、循環リストとして先頭の値が末尾に1つだけ続けて表示される点に注意してください。