C++で循環単方向リンクリストを実装する方法【サンプルコード付き】

循環単方向リンクリスト(Circular Singly Linked List)は、自己参照構造体を用いて作成されたノードから構成されるデータ構造の一種です。各ノードは「データ」と「次のノードへの参照(ポインタ)」という2つの部分で構成されています。

リンクリスト全体へアクセスするには、先頭ノードへの参照だけがあれば十分です。この先頭ノードは「ヘッド(head)」と呼ばれます。そして、リストの最後のノードは先頭ノード(ヘッド)を指します。このようにリストが輪のように閉じていることから、「循環リンクリスト」と呼ばれています。

以下に、循環単方向リンクリストを実装するC++プログラムの例を示します。

サンプルプログラム

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
   struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
   struct Node *ptr = head;
   newnode->data = newdata;
   newnode->next = head;
   if (head!= NULL) {
      while (ptr->next != head)
      ptr = ptr->next;
      ptr->next = newnode;
   } else
   newnode->next = newnode;
   head = newnode;
}
void display() {
   struct Node* ptr;
   ptr = head;
   do {
      cout<<ptr->data <<" ";
      ptr = ptr->next;
   } while(ptr != head);
}
int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The circular linked list is: ";
   display();
   return 0;
}

実行結果

The circular linked list is: 9 2 7 1 3

挿入は常に先頭(head)に対して行われるため、出力では最後に挿入した「9」が最初に表示され、最初に挿入した「3」が最後に表示されている点に注目してください。

プログラムの解説

Node構造体

上記のプログラムでは、Node構造体がリンクリストの1つのノードを表します。この構造体は、データ本体を格納する data フィールドと、次のノードを指すポインタ next を持っています。

struct Node {
   int data;
   struct Node *next;
};

insert()関数 ― 先頭への挿入

insert()関数は、リンクリストの先頭に新しいデータを挿入します。処理の流れは以下の通りです。

1. malloc()で新しいノード(newnode)を確保し、引数の値をdataフィールドに格納します。
2. headがNULL(空のリスト)の場合、newnodeは自分自身を指します。これにより、ノードが1つでも循環が保たれます。
3. headがNULLでない場合、whileループで最後のノードまで辿り、そのノードのnextをnewnodeに付け替えます。これにより、末尾→新ノード→旧先頭という循環が維持されます。
4. 最後にheadをnewnodeに更新し、新しいノードをリストの先頭とします。

void insert(int newdata) {
   struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
   struct Node *ptr = head;
   newnode->data = newdata;
   newnode->next = head;
   if (head!= NULL) {
      while (ptr->next != head)
      ptr = ptr->next;
      ptr->next = newnode;
   } else
   newnode->next = newnode;
   head = newnode;
}

なお、この実装では末尾ノードを見つけるために毎回リスト全体を走査する必要があるため、挿入操作の計算量はO(n)となります。末尾ノードへのポインタ(tail)を別途保持すれば、O(1)での挿入も可能です。

display()関数 ― リスト全体の表示

display()関数は、リンクリスト全体を表示します。まずポインタptrをheadに設定し、do-while文によって現在のノードのデータを出力しながらptrを次のノードへ進めていきます。ptrが再びheadに戻った時点で一周したことが分かるため、そこでループを終了します。通常のwhile文ではなくdo-while文を使うのは、ループ開始直後に終了条件を判定すると最初のノードが表示されないためです。

void display() {
   struct Node* ptr;
   ptr = head;
   do {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   } while(ptr != head);
}

main()関数 ― 動作確認

main()関数では、まずinsert()を5回呼び出して値(3、1、7、2、9)を順番に循環リンクリストへ挿入します。その後、display()を呼び出してリスト全体を表示しています。

int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The circular linked list is: ";
   display();
   return 0;
}

まとめ

循環単方向リンクリストは、末尾ノードが先頭ノードを指すことでリング状の構造を実現するデータ構造です。本記事では、Node構造体の定義、先頭への挿入を行うinsert()関数、全ノードを表示するdisplay()関数の実装を通じて、その基本的な仕組みを解説しました。循環構造を扱う際は、走査の終了条件を「NULLではなくheadへの到達」とする点が通常のリンクリストとの大きな違いであり、この点を押さえておくことが重要です。