構造体の配列を使いたいけど、要素数が未確定のため何回もreallocすることになって、処理が重たい。。。
という場面に遭遇したことはありませんか?
このような場合は、配列では無くリスト構造にするとreallocする必要がなくなり、要素の追加、削除、挿入の処理が速くなります。
目次
リスト構造とは?
構造体と構造体をポインタでリンクして、数珠繋ぎになっている構造のことをリスト構造もしくはチェーン構造と言います。
※配列とは異なるデータ構造です。
C言語の世界では良く使用するデータ構造のテクニックです。
以下、リスト構造のイメージです。
リスト構造のメリットとデメリット
メリット
- 要素の追加、削除、挿入が高速
- ツリー構造を表現できる
デメリット
- 要素のアクセス(巡回)が遅い
- 配列のように要素にダイレクトにアクセスできない
- 二分探索ができない
リスト構造の書き方と使い方
単純なリスト構造
単純なリスト構造の書き方について
構造体のメンバーに自身の型のポインタを定義します。
メンバ変数名はnextと付けるのが一般的です。
typedef struct _LIST{
int data1;
int data2;
struct _LIST *next; // 自身の型を指すポインタを定義
}LIST;
メンバ変数の*nextに数珠繋ぎにする構造体変数をセットして使用します。
リスト構造の使い方について
リスト構造の先頭と終端を示す変数を宣言します。
要素が必ず1つ存在する場合は、グローバル変数または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;
}
コメント