C++で循環双方向リンクリスト（Circular Doubly Linked List）を実装する方法

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

循環双方向リンクリスト（Circular Doubly Linked List）では、隣り合う2つの要素が previous（前）ポインタと next（次）ポインタによって相互に接続されています。さらに特徴的なのは、末尾のノードが next ポインタで先頭ノードを指し、先頭のノードも previous ポインタで末尾ノードを指すという点です。この仕組みにより、リストのどのノードからでも全要素へ巡回的にアクセスできるのが大きな利点です。

アルゴリズム

開始
　　circulardoublylist クラスを作成し、以下の関数を持たせる：
　　　nod *create_node(int) = ノード用のメモリを動的に確保する。
　　　insert_begin() = リストの先頭に要素を挿入する。
　　　　A) リストが空の場合、ノードを挿入し、next / previous ポインタを NULL に設定する。
　　　　B) リストが空でない場合、データを挿入し、next / previous ポインタを適切に設定・更新する。

　　　insert_end() = リストの末尾に要素を挿入する：
　　　　A) リストが空の場合、循環双方向リストとしてノードを作成する。
　　　　B) 末尾ノードを特定する。
　　　　C) ノードを動的に作成する。
　　　　D) 新しいノードの next を先頭ノードにする。
　　　　E) 新しいノードの previous を元の末尾ノードにする。
　　　　F) 元の末尾ノードの previous を新しいノードにする。
　　　　G) 元の末尾ノードの next を新しいノードにする。

　　　insert_pos() = リストの指定位置に要素を挿入する：
　　　　A) 挿入するデータを入力する。
　　　　B) 挿入位置を入力する。
　　　　C) リストが空の場合、先頭にノードを挿入する。
　　　　D) リストが空でない場合、指定位置のノードとその次のノードを探索する。
　　　　E) その2つのノードの間に新しいノードを挿入する。

　　　delete_pos() = リストの指定位置から要素を削除する：
　　　　A) リストが空の場合、何もせず処理を終了する。
　　　　B) 削除対象ノードの位置を入力する。
　　　　C) ノードが1つしかない場合、そのノードを削除し、next / prev ポインタを更新する。
　　　　D) ノードが複数ある場合、指定位置のノードを削除し、next / prev ポインタを更新する。

　　　search() = リスト内の要素を検索する：
　　　　A) リストが空の場合、何もせず処理を終了する。
　　　　B) 検索したい値を入力する。
　　　　C) 要素が見つかった位置を表示する。
　　　　D) 要素が見つからなかった場合は「見つかりません」を表示する。

　　　update() = 特定ノードの値を更新する：
　　　　A) リストが空の場合、何もせず処理を終了する。
　　　　B) 更新するノードの位置を入力する。
　　　　C) 新しい値を入力する。
　　　　D) ノードの値を更新する。
　　　display() = リストの内容を表示する。
　　　reverse() = リストを逆順に並べ替える。
終了

サンプルコード

以下は、上記のアルゴリズムを C++ で実装した完全なプログラムです。メニュー形式で操作を選択できる対話型の構造になっています。

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct nod {
   int info;
   struct nod *n;
   struct nod *p;
}*start, *last;
int count = 0;
class circulardoublylist {
   public:
      nod *create_node(int);
      void insert_begin();
      void insert_end();
      void insert_pos();
      void delete_pos();
      void search();
      void update();
      void display();
      void reverse();
      circulardoublylist() {
         start = NULL;
         last = NULL;
    }
};
int main() {
   int c;
   circulardoublylist cdl;
   while (1) //perform switch operation {
      cout<<"1.Insert at Beginning"<<endl;
      cout<<"2.Insert at End"<<endl;
      cout<<"3.Insert at Position"<<endl;
      cout<<"4.Delete at Position"<<endl;
      cout<<"5.Update Node"<<endl;
      cout<<"6.Search Element"<<endl;
      cout<<"7.Display List"<<endl;
      cout<<"8.Reverse List"<<endl;
      cout<<"9.Exit"<<endl;
      cout<<"Enter your choice : ";
      cin>>c;
      switch(c) {
         case 1:
            cdl.insert_begin();
         break;
         case 2:
            cdl.insert_end();
         break;
         case 3:
            cdl.insert_pos();
         break;
         case 4:
            cdl.delete_pos();
         break;
         case 5:
            cdl.update();
         break;
         case 6:
            cdl.search();
         break;
         case 7:
            cdl.display();
         break;
         case 8:
            cdl.reverse();
         break;
         case 9:
            exit(1);
         default:
            cout<<"Wrong choice"<<endl;
    }
  }
  return 0;
}
nod* circulardoublylist::create_node(int v) {
   count++;
   struct nod *t;
   t = new(struct nod);
   t->info = v;
   t->n = NULL;
   t->p = NULL;
   return t;
}
void circulardoublylist::insert_begin() {
   int v;
   cout<<endl<<"Enter the element to be inserted: ";
   cin>>v;
   struct nod *t;
   t = create_node(v);
   if (start == last && start == NULL) {
      cout<<"Element inserted in empty list"<<endl;
      start = last = t;
      start->n = last->n = NULL;
      start->p = last->p = NULL;
  } else {
      t->n = start;
      start->p = t;
      start = t;
      start->p = last;
      last->n = start;
      cout<<"Element inserted"<<endl;
  }
}
void circulardoublylist::insert_end() {
   int v;
   cout<<endl<<"Enter the element to be inserted: ";
   cin>>v;
   struct nod *t;
   t = create_node(v);
   if (start == last && start == NULL) {
      cout<<"Element inserted in empty list"<<endl;
      start = last = t;
      start->n= last->n = NULL;
      start->p = last->p= NULL;
  } else {
      last->n= t;
      t->p= last;
      last = t;
      start->p = last;
      last->n= start;
  }
}
void circulardoublylist::insert_pos() {
   int v, pos, i;
   cout<<endl<<"Enter the element to be inserted: ";
   cin>>v;
   cout<<endl<<"Enter the position of element inserted: ";
   cin>>pos;
   struct nod *t, *s, *ptr;
   t = create_node(v);
   if (start == last && start == NULL) {
      if (pos == 1) {
         start = last = t;
         start->n = last->n = NULL;
         start->p = last->p = NULL;
      } else {
         cout<<"Position out of range"<<endl;
         count--;
         return;
      }
  } else {
      if (count < pos) {
         cout<<"Position out of range"<<endl;
         count--;
         return;
      }
      s = start;
      for (i = 1;i <= count;i++) {
         ptr = s;
         s = s->n;
         if (i == pos - 1) {
            ptr->n = t;
            t->p= ptr;
            t->n= s;
            s->p = t;
            cout<<"Element inserted"<<endl;
            break;
        }
    }
  }
}
void circulardoublylist::delete_pos() {
   int pos, i;
   nod *ptr, *s;
   if (start == last && start == NULL) {
      cout<<"List is empty, nothing to delete"<<endl;
      return;
  }
   cout<<endl<<"Enter the position of element to be deleted: ";
   cin>>pos;
   if (count < pos) {
      cout<<"Position out of range"<<endl;
      return;
  }
   s = start;
   if(pos == 1) {
      count--;
      last->n = s->n;
      s->n->p = last;
      start = s->n;
      free(s);
      cout<<"Element Deleted"<<endl;
      return;
  }
   for (i = 0;i < pos - 1;i++ ) {
      s = s->n;
      ptr = s->p;
  }
   ptr->n = s->n;
   s->n->p = ptr;
   if (pos == count) {
      last = ptr;
  }
   count--;
   free(s);
   cout<<"Element Deleted"<<endl;
}
void circulardoublylist::update() {
   int v, i, pos;
   if (start == last && start == NULL) {
      cout<<"The List is empty, nothing to update"<<endl;
      return;
  }
   cout<<endl<<"Enter the position of node to be updated: ";
   cin>>pos;
   cout<<"Enter the new value: ";
   cin>>v;
   struct nod *s;
   if (count < pos) {
      cout<<"Position out of range"<<endl;
      return;
  }
   s = start;
   if (pos == 1) {
      s->info = v;
      cout<<"Node Updated"<<endl;
      return;
  }
   for (i=0;i < pos - 1;i++) {
      s = s->n;
  }
   s->info = v;
   cout<<"Node Updated"<<endl;
}
void circulardoublylist::search() {
   int pos = 0, v, i;
   bool flag = false;
   struct nod *s;
   if (start == last && start == NULL) {
      cout<<"The List is empty, nothing to search"<<endl;
      return;
  }
   cout<<endl<<"Enter the value to be searched: ";
   cin>>v;
   s = start;
   for (i = 0;i < count;i++) {
      pos++;
      if (s->info == v) {
         cout<<"Element "<<v<<" found at position: "<<pos<<endl;
         flag = true;
      }
      s = s->n;
  }
   if (!flag)
      cout<<"Element not found in the list"<<endl;
}
void circulardoublylist::display() {
   int i;
   struct nod *s;
   if (start == last && start == NULL) {
      cout<<"The List is empty, nothing to display"<<endl;
      return;
  }
   s = start;
   for (i = 0;i < count-1;i++) {
      cout<<s->info<<"<->";
      s = s->n;
  }
   cout<<s->info<<endl;
}
void circulardoublylist::reverse() {
   if (start == last && start == NULL) {
      cout<<"The List is empty, nothing to reverse"<<endl;
      return;
  }
   struct nod *p1, *p2;
   p1 = start;
   p2 = p1->n;
   p1->n = NULL;
   p1->p= p2;
   while (p2 != start) {
      p2->p = p2->n;
      p2->n = p1;
      p1 = p2;
      p2 = p2->p;
  }
   last = start;
   start = p1;
   cout<<"List Reversed"<<endl;
}

実行結果

このプログラムをコンパイルして実行すると、以下のような対話的な出力が得られます。各操作の動作確認に役立ててください。

1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 1

Enter the element to be inserted: 7
Element inserted in empty list
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 1

Enter the element to be inserted: 6
Element inserted
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 2

Enter the element to be inserted: 4
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 2

Enter the element to be inserted: 5
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 7
6<->7<->4<->5
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 6

Enter the value to be searched: 7
Element 7 found at position: 2
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 6

Enter the value to be searched: 2
Element not found in the list
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 4

Enter the position of element to be deleted: 4
Element Deleted
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 3

Enter the element to be inserted: 5

Enter the position of element inserted: 2
Element inserted
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 7
6<->5<->7<->4
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 8
List Reversed
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 7
4<->7<->5<->6
1.Insert at Beginning
2.Insert at End
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Display List
8.Reverse List
9.Exit
Enter your choice : 9

まとめ

本記事では、C++ を用いて循環双方向リンクリストを実装する方法を解説しました。先頭・末尾・任意位置への挿入、指定位置からの削除、要素検索、ノード更新、リスト表示、逆順ソートといった基本操作をすべて網羅しています。循環双方向リンクリストは、両方向への走査が可能で、末尾から先頭へのアクセスも O(1) で行えるため、キャッシュ管理やテキストエディタのバッファ管理など、双方向の巡回処理が必要な場面で特に有用なデータ構造です。ぜひ実際にコードを動かして、挙動を確認してみてください。