C++で配列を循環双方向リンクリストに変換する方法を徹底解説

はじめに

本記事では、配列を循環双方向リンクリスト(循環 doubly linked list)に変換するC++ プログラムの実装方法を、コード例とともにわかりやすく解説します。

課題の内容はシンプルです。入力として与えられた配列の各要素をノード化し、それらを連結して循環双方向リンクリストを構築します。

循環双方向リンクリストとは?

通常の双方向リンクリストでは、各ノードが「次のノード(next)」と「前のノード(prev)」へのポインタを持っています。これに対して循環双方向リンクリストでは、末尾ノードの next が先頭ノードを指し、先頭ノードの prev が末尾ノードを指すため、リスト全体がリング状につながっています。

アルゴリズムの流れ

• 配列の各要素に対して malloc を使って新しいノードを動的に生成します。
• 最初の要素の場合は、そのノードを先頭(*start)とし、next と prev を自分自身に向けて初期化します。
• 2番目以降の要素の場合は、(*start)->prev で現在の末尾ノードを取得し、その後ろに新しいノードを挿入します。
• すべての要素を追加したら、print_list 関数でリストの中身を出力して結果を確認します。

ここでのポイントは、循環リストでは先頭ノードの prev ポインタが常に末尾ノードを指しているため、末尾をたどるために別途トラバーサルを行う必要がない点です。

C++ 実装例

#include<iostream>
using namespace std;
//双方向リンクリスト用のノード構造体
struct node{
    int data;
    struct node *next;
    struct node *prev;
};
//新しいノードの生成
struct node* getNode(){
    return ((struct node *)malloc(sizeof(struct node)));
}
//リストの内容を表示する関数
int print_list(struct node *temp){
    struct node *t = temp;
    if(temp == NULL)
        return 0;
    else {
        cout<<"List: ";
        while(temp->next != t) {
            cout<<temp->data<<" ";
            temp = temp->next;
        }
        cout<<temp->data;
        return 1;
    }
}
//配列を循環双方向リンクリストに変換する関数
void convert_array(int arr[], int n, struct node **start) {
    //使用するポインタの宣言
    struct node *newNode,*temp;
    int i;
    //配列の全要素を順に処理
    for(i=0;i<n;i++){
        newNode = getNode();
        newNode->data = arr[i];
        if(i==0) {
            //最初の要素は先頭ノードとなり、自分自身を指す
            *start = newNode;
            newNode->prev = *start;
            newNode->next = *start;
        } else {
            //末尾ノードを取得して新しいノードを接続
            temp = (*start)->prev;
            temp->next = newNode;
            newNode->next = *start;
            newNode->prev = temp;
            temp = *start;
            temp->prev = newNode;
        }
    }
}
int main(){
    int arr[] = {1,2,3,4,5};
    int n = sizeof(arr) / sizeof(arr[0]);
    struct node *start = NULL;
    convert_array(arr, n, &start);
    print_list(start);
    return 0;
}

実行結果

List: 1 2 3 4 5

コードのポイント解説

1. ノード構造体の定義

struct node は、格納する値(data)と、次・前のノードへのポインタ(next・prev)を持つシンプルな構造です。

2. 挿入時のリンク更新

新しいノードを末尾に追加する際には、次の4つのポインタ操作が必要です。

• 旧末尾ノードの next を新ノードに向ける
• 新ノードの next を先頭ノードに向ける(循環を維持)
• 新ノードの prev を旧末尾ノードに向ける
• 先頭ノードの prev を新ノード(=新しい末尾)に更新する

3. 計算量

先頭ノードの prev が常に末尾を指しているおかげで、末尾への挿入は O(1) で行えます。配列全体の変換は O(n) で完了します。

まとめ

このように、配列から循環双方向リンクリストへの変換は、「先頭ノードの初期化」と「末尾への挿入時のポインタ更新」を正しく行うことで簡単に実装できます。循環リストは、バッファ管理やターンベースのゲームロジックなど、データを環状に扱いたい場面で活用される重要なデータ構造なので、ぜひマスターしておきましょう。