C++で循環リンクリストのノード数をカウントする方法

ノードから構成される循環リンクリスト（Circular Linked List）が与えられ、そのリスト内に存在するノードの総数を求めるのが課題です。

循環リンクリストとは、連結リストの一種であり、最初の要素が最後の要素を指し、最後の要素が最初の要素を指すという特徴を持つデータ構造です。片方向リンクリスト（Singly Linked List）でも双方向リンクリスト（Doubly Linked List）でも、この循環リンクリストとして実装することが可能です。

以下のプログラムでは、片方向リンクリストを循環リンクリストとして実装し、その中に含まれるノード数をカウントする方法を紹介します。

具体例

入力 − ノード：20, 1, 2, 3, 4, 5
出力 − ノード数：6

入力 − ノード：20, 1, 2, 3, 4, 5, 7, 8, 9, 12
出力 − ノード数：10

アルゴリズムのアプローチ

以下のプログラムで採用している手順は次のとおりです。

• ノードが保持するデータと次ノードへのポインタ（アドレス）を含む、片方向リンクリスト用の構造体を定義します。
• ノードにデータを挿入するための push() 関数を作成します。
• 最後のノードに先頭ノードのアドレスを格納することで、片方向リンクリストを循環リンクリストとして機能させます。
• 循環リンクリスト内のノード総数をカウントする count_fun() 関数を作成します。ここでは do-while ループを使用し、再び先頭ノードに戻ってくるまで走査することで、無限ループを回避しながら正確にノード数を数えます。

サンプルコード

#include <stdio.h>
#include <stdlib.h>
/* ノードの定義 */
struct node {
    int data;
    struct node* next;
};
// 循環リストへのノード挿入
void push(struct node** head_ref, int data){
    struct node* ptr1 = (struct node*)malloc(sizeof(struct node));
    struct node* temp = *head_ref;
    ptr1->data = data;
    ptr1->next = *head_ref;
    // 新しい要素を挿入するため最後のノードまで移動
    if (*head_ref != NULL){
        while (temp->next != *head_ref){
            temp = temp->next;
        }
        temp->next = ptr1;
    } else{
        ptr1->next = ptr1; // 先頭ノードの場合は自分自身を指す
    }
    *head_ref = ptr1;
}
// ノード数をカウントする関数
int count_fun(struct node* head){
    struct node* temp = head;
    int result = 0;
    if (head != NULL){
        do {
            temp = temp->next;
            result++;
        } while (temp != head);
    }
    return result;
}
int main(){
    /* リストを空の状態で初期化 */
    struct node* head = NULL;
    push(&head, 10);
    push(&head, 20);
    push(&head, 30);
    push(&head, 40);
    printf("count of nodes are: %d", count_fun(head));
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

count of nodes are: 4

このように、push() 関数によって4つのノード（10, 20, 30, 40）が循環リンクリストに挿入され、count_fun() 関数が do-while ループで一周分の走査を行うことで、正しく「4」というノード数が出力されます。