[C/C++] リスト構造体（チェーン構造）の書き方と使い方

2021年9月29日2024年9月7日

当ページのリンクには広告が含まれています。

構造体の配列を使いたいけど、要素数が未確定のため何回もreallocすることになって、処理が重たい。。。
という場面に遭遇したことはありませんか？
このような場合は、配列では無くリスト構造にするとreallocする必要がなくなり、要素の追加、削除、挿入の処理が速くなります。

リスト構造とは？

構造体と構造体をポインタでリンクして、数珠繋ぎになっている構造のことをリスト構造もしくはチェーン構造と言います。
※配列とは異なるデータ構造です。
C言語の世界では良く使用するデータ構造のテクニックです。

以下、リスト構造のイメージです。

リスト構造のメリットとデメリット

メリット

要素の追加、削除、挿入が高速
ツリー構造を表現できる

デメリット

要素のアクセス（巡回）が遅い
配列のように要素にダイレクトにアクセスできない
二分探索ができない

リスト構造の書き方と使い方

単純なリスト構造

単純なリスト構造の書き方について

構造体のメンバーに自身の型のポインタを定義します。
メンバ変数名はnextと付けるのが一般的です。

typedef struct _LIST{
	int data1;
	int data2;
	struct _LIST *next;	// 自身の型を指すポインタを定義
}LIST;

メンバ変数の*nextに数珠繋ぎにする構造体変数をセットして使用します。

リスト構造の使い方について

リスト構造の先頭と終端を示す変数を宣言します。
要素が必ず１つ存在する場合は、グローバル変数またはstatic変数で実体を持たせても良いです。
要素が0の場合もあるときは、ポインタで宣言します。

typedef struct _LIST{
	int data1;
	int data2;
	struct _LIST *next;
}LIST;
LIST *ListTop = NULL;	// リスト構造の先頭を示す変数をポインタで宣言
LIST *ListEnd = NULL;	// リスト構造の終端を示す変数をポインタで宣言

次に、要素を追加する関数を作成します。

// リスト構造に要素を追加する
_Bool ListPush(LIST *data)
{
	// エラーチェック
	if(data == NULL){
		return FALSE;
	}
	
	if(ListTop == NULL){
		// リストに登録されている要素数が0の場合
		ListTop = malloc(sizeof(LIST));
		if(ListTop == NULL){
			return FALSE;
		}
		ListEnd = ListTop;
	}else{
		// *nextに要素を追加
		ListEnd->next = malloc(sizeof(LIST));
		if(ListEnd == NULL){
			return FALSE;
		}
		ListEnd = ListEnd->next;
	}
	*ListEnd = *data;
	ListEnd->next = NULL;

	return TRUE;
}

次に全要素を削除（free）する関数を作成します。

// リスト構造の全要素を削除する
void ListClear(void)
{
	LIST *ListCur = ListTop;

	while(ListCur != NULL){
		LIST *temp = ListCur;
		ListCur = ListCur->next;
		free(temp);
	}
}

リスト構造に要素を追加する関数と、要素を削除する関数ができたので、それらを組み合わせて使用してみましょう。

int main(void)
{
	LIST data, *ListCur;

	// リスト構造にデータを追加
	data.data1 = 1;
	if(ListPush(&data) == FALSE){
		printf("要素の追加に失敗しました。\n");
	}

	data.data1 = 2;
	if(ListPush(&data) == FALSE){
		printf("要素の追加に失敗しました。\n");
	}

	data.data1 = 3;
	if(ListPush(&data) == FALSE){
		printf("要素の追加に失敗しました。\n");
	}

	// リスト構造のデータを表示
	printf("=== リスト構造のデータを表示 ===\n");
	for(ListCur=ListTop; ListCur!=NULL; ListCur=ListCur->next){
		printf("data1 = %d\n", ListCur->data1);
	}

	// リスト構造のデータを全削除
	ListClear();

	// リスト構造のデータを表示
	printf("=== リスト構造のデータを表示 ===\n");
	for(ListCur = ListTop; ListCur != NULL; ListCur = ListCur->next){
		printf("data1 = %d\n", ListCur->data1);
	}

	return 0;
}

実行結果

=== リスト構造のデータを表示 ===
data1 = 1
data1 = 2
data1 = 3
=== リスト構造のデータを表示 ===

最後にここまでのソースコードをまとめておきます。

#include <stdlib.h>
#include <stdio.h>

#define TRUE	(1)
#define FALSE	(0)

typedef struct _LIST{
	int data1;
	int data2;
	struct _LIST *next;
}LIST;
LIST *ListTop = NULL;	// リスト構造の先頭を示す変数をポインタで宣言
LIST *ListEnd = NULL;	// リスト構造の終端を示す変数をポインタで宣言

// リスト構造に要素を追加する
_Bool ListPush(LIST *data)
{
	// エラーチェック
	if(data == NULL){
		return FALSE;
	}
	
	if(ListTop == NULL){
		// リストに登録されている要素数が0の場合
		ListTop = malloc(sizeof(LIST));
		if(ListTop == NULL){
			return FALSE;
		}
		ListEnd = ListTop;
	}else{
		// *nextに要素を追加
		ListEnd->next = malloc(sizeof(LIST));
		if(ListEnd == NULL){
			return FALSE;
		}
		ListEnd = ListEnd->next;
	}
	*ListEnd = *data;
	ListEnd->next = NULL;

	return TRUE;
}

// リスト構造の全要素を削除する
void ListClear(void)
{
	LIST *ListCur = ListTop;

	while(ListCur != NULL){
		LIST *temp = ListCur;
		ListCur = ListCur->next;
		free(temp);
	}
	ListTop = NULL;
}

int main(void)
{
	LIST data, *ListCur;

	// リスト構造にデータを追加
	data.data1 = 1;
	if(ListPush(&data) == FALSE){
		printf("要素の追加に失敗しました。\n");
	}

	data.data1 = 2;
	if(ListPush(&data) == FALSE){
		printf("要素の追加に失敗しました。\n");
	}

	data.data1 = 3;
	if(ListPush(&data) == FALSE){
		printf("要素の追加に失敗しました。\n");
	}

	// リスト構造のデータを表示
	printf("=== リスト構造のデータを表示 ===\n");
	for(ListCur=ListTop; ListCur!=NULL; ListCur=ListCur->next){
		printf("data1 = %d\n", ListCur->data1);
	}

	// リスト構造のデータを全削除
	ListClear();

	// リスト構造のデータを表示
	printf("=== リスト構造のデータを表示 ===\n");
	for(ListCur=ListTop; ListCur!=NULL; ListCur=ListCur->next){
		printf("data1 = %d\n", ListCur->data1);
	}

	return 0;
}