連結リスト（リンクリスト）の長さを求めるC言語プログラム

連結リスト（リンクリスト）は動的メモリ割り当てを利用するデータ構造であり、要素の追加や削除に応じてサイズが柔軟に変化します。連結リストは「ノード」と呼ばれる要素の集合として定義され、各ノードはデータ部とリンク部（次のノードへのポインタ）の2つの部分で構成されています。

データ・リンク・連結リストの関係は、以下のように表現できます。

連結リストの種類

連結リストには主に以下の4種類があります。

• 単方向連結リスト（シングルリンクリスト）
• 双方向連結リスト（ダブルリンクリスト）
• 循環単方向連結リスト
• 循環双方向連結リスト

再帰を使って長さを求めるロジック

本記事では、再帰呼び出しを利用して連結リストの長さ（ノード数）を求める方法を紹介します。基本的な考え方はシンプルです。

• 現在のノードがNULL（リストの終端）であれば、それまでカウントした値を返す
• NULLでなければ、カウンタを1つ増やし、次のノードに対して同じ関数を再帰的に呼び出す

このロジックをコードにすると、次のようになります。

int length(node *temp){
   if(temp==NULL)
      return l;
   else{
      l=l+1;
      length(temp->next);
   }
}

C言語による完全なプログラム

以下は、ユーザーから入力を受け取って連結リストを構築し、その長さを再帰関数で求めるCプログラムの完全な例です。

#include <stdio.h>
#include <stdlib.h>
typedef struct linklist{
   int data;
   struct linklist *next;
}node;
int l=0;
int main(){
   node *head=NULL,*temp,*temp1;
   int len,choice,count=0,key;
   do{
      temp=(node *)malloc(sizeof(node));
      if(temp!=NULL){
         printf("\nenter the elements in a list : ");
         scanf("%d",&temp->data);
         temp->next=NULL;
         if(head==NULL){
            head=temp;
         }else{
            temp1=head;
            while(temp1->next!=NULL){
               temp1=temp1->next;
            }
            temp1->next=temp;
         }
      }else{
         printf("\nMemory is full");
      }
      printf("\npress 1 to enter data into list: ");
      scanf("%d",&choice);
   }while(choice==1);
   len=length(head);
   printf("The list has %d no of nodes",l);
   return 0;
}
//recursive function to find length
int length(node *temp){
   if(temp==NULL)
      return l;
   else{
      l=l+1;
      length(temp->next);
   }
}

プログラムのポイント

• malloc関数：新しいノードを作成するたびに動的にメモリを確保します。確保に失敗した場合は「Memory is full」と表示されます。
• 末尾への挿入：headから順にnextポインタをたどり、リストの最後尾に新しいノードを接続します。
• グローバル変数l：再帰関数内でノード数をカウントするために使用しています。

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

Run 1:
enter the elements in a list: 3
press 1 to enter data into list: 1
enter the elements in a list: 56
press 1 to enter data into list: 1
enter the elements in a list: 56
press 1 to enter data into list: 0
The list has 3 no of nodes
Run 2:
enter the elements in a list: 12
press 1 to enter data into list: 1
enter the elements in a list: 45
press 1 to enter data into list: 0
The list has 2 no of nodes

実行例1では3つのノード（3、56、56）、実行例2では2つのノード（12、45）が登録され、それぞれ正しくノード数が出力されていることが確認できます。