リスト構造をC言語プログラムの実例を用いて解説

データ構造やアルゴリズムなどを学習していると必ず出てくるのがリスト構造です。色々考えてみたのですが、ポインタを理解する上でリスト構造ってかなりいいテーマだなと思います。「動的にメモリ領域を確保してポインタで指す」、「リストの次の要素をポインタで指し示して要素のつながりを持たせる」、「リストの終端はNULLかどうかで判断する」等がリスト構造のプログラムのポイントであり、リスト構造のプログラムを作成するだけでこれらに触れることができます。

ポインタの概念をまだ理解できていない!という人は下のページでポインタについて解説していますので、こちらも是非ご参照ください。

ポインタ解説ページのアイキャッチ徹底図解!C言語ポインタを初心者向けに分かりやすく解説

このページではリスト構造の概要の説明とリスト構造のC言語プログラムの実例・その解説を行なっていきたいと思います。

リスト構造とは

リスト構造とは下記のようなデータ構造のことです。会員情報を登録するデータベースみたいなものを実例として下に示しています。

リスト構造の特徴は次の2つです

  • 各要素は実データ(会員番号・名前などの管理したいデータ)とポインタから構成される
  • ポインタは次の要素を指す
    (双方向ポインタの場合は前の要素も指す)

リスト構造では他の要素をポインタで指すことでデータが繋がります。ですので、データの追加や削除が容易であるというメリットがあります。

リストへの要素の追加は次の手順で可能です。

  1. 新しい要素を追加(malloc)
  2. 新しい要素の「次要素へのポインタ」に、新しい要素の1つ手前の要素の「次要素へのポインタ」が指しているアドレスを指させる
  3. 新しい要素の1つ手前の要素の「次要素へのポインタ」に新しい要素のアドレスを指させる

またリスト構造からの削除は次の手順で可能です。

  1. 削除したい要素の1つ手前の要素の「次要素へのポインタ」に、削除したい要素の「次要素へのポインタ」が指しているアドレスを指させる
  2. 削除したい要素を削除(free)

プログラム例

会員情報を登録・削除・表示するプログラムを実際に書いてみました。会員情報は構造体として定義し、上の絵と同じ3つのメンバ(会員番号・名前・次要素へのポインタ)を持たせています。

/* 会員情報を登録する構造体 */

struct LIST{
  unsigned int number;
  char name[256];
  struct LIST *next;
} ;

プログラムの動きの流れは下記の通りです。

  1. 行いたい操作を取得(”1″ であれば会員情報の登録・”2″ であれば会員情報の削除・”それ以外” であればプログラム終了)
  2. 登録の場合、「名前」を取得し、その名前を持つ会員情報の要素をリストの最後に追加
  3. 削除の場合、「会員番号」を取得し、その会員番号を持つ会員情報の要素を削除
  4. 上記どちらかを実行したらリスト全体の情報を表示
  5. A. に戻る

全体のプログラムは下記の通りです。

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

/* 会員情報を登録する構造体 */

struct LIST{
  unsigned int number;
  char name[256];
  struct LIST *next;
} ;

/* 会員情報を全て表示する関数 */
int displayList(struct LIST *list){
  while(list != NULL){
    printf("%d:%s\n", list->number, list->name);
    list = list->next;
  }
  return 0;
}

/* 会員情報を全て削除する関数 */
struct LIST* deleteAllList(struct LIST *list){
  struct LIST *tmp;

  while(list != NULL){
    tmp = list->next;
    free(list);
    list = tmp;
  }

  return NULL;
}


/* 会員情報をリストの最後に追加し、リストの先頭アドレスを返却する関数 */
struct LIST* addList(struct LIST *list, char *name, unsigned int number){
  struct LIST *item;
  struct LIST *top;

  top = list;

  item = (struct LIST*)malloc(sizeof(struct LIST));
  item->number = number;
  strcpy(item->name, name);
  item->next = NULL;


  /* リストが空の場合は先頭に追加して終了 */
  if(list == NULL){
    list = item;
    return list;
  }

  /* リストのnextを辿ってリストの最後を探す */
  /* リストの最後とは、nextがNULLの要素 */
  while(list->next != NULL){
    list = list->next;
  }
  list->next = item;

  /* ここでreturnする場合は先頭アドレスは変わらない */
  return top;
}

/* 会員情報を削除し、リストの先頭アドレスを返却する関数 */
struct LIST* deleteList(struct LIST *list, unsigned int number){
  struct LIST *tmp;
  struct LIST *top;
  top = list;

  /* 先頭ノードの場合だけ別処理 */
  if(list != NULL && list->number == number){
    tmp = list->next;
    free(list);

    /* 次の要素のアドレスをリストの先頭アドレスとして返却 */
    return tmp;
  }

  /* リストを辿って指定された会員番号の要素を探す */
  while(list != NULL){
    if(list->next->number == number){
      tmp = list->next->next;
      free(list->next);
      list->next = tmp;
      return top;
    }
    list = list->next;
  }
  printf("Number %d not found!\n", number);

  return top;
}

int main(void){
  int operation;
  unsigned int inputnumber = 1;
  unsigned int number = 1;
  char inputname[256];

  struct LIST *list = NULL;

  /* 会員登録情報に対する操作 */
  while(1){
    printf("operation(1:add, 2:delete, etc:exit) = ");
    scanf("%d", &operation);

    if(operation == 1){
      /* 1が入力されれば必要な情報を取得してリストに追加 */
      printf("add name = ");
      scanf("%s", inputname);

      list = addList(list, inputname, number);
      number++;
    } else if(operation == 2){
      /* 2が入力されれば必要な情報を取得してリストから削除 */
      if(list == NULL){
        printf("list is empty\n");
      } else {
        printf("delete number = ");
        scanf("%d", &inputnumber);
        list = deleteList(list, inputnumber);
      }

    } else {
      /* それ以外はwhileを抜ける */
      break;
    }

    displayList(list);

  }

  list = deleteAllList(list);

  return 0;
}

スポンサーリンク

プログラムの解説

それではプログラムで実際何を行なっているのかを解説していきたいと思います。

main 関数

main 関数で行なっているのは「ユーザーからの値の入力取得」と「その入力結果に応じた処理の振り分け」です。

「ユーザーからの値の入力取得」は scanf関数 で行なっています。

そして scarf 関数で取得された値が “1” の時は addList 関数、”2″ の時は deleteList 関数を実行します。”1″ でも “2” でもない場合は deleteAllList 関数を実行してプログラムを終了させています。

main 関数内の LIST 構造体 list は常にリストの先頭アドレスを指させています。登録情報がなくてリストが空の場合は NULL を指させています。

リストへの追加(addList関数)

次にリストに要素を追加する addList 関数について説明していきます。

引数として渡される変数は下記の3つになります。

  • list:リストの先頭要素のアドレス
  • name:追加する人の名前
  • number:現在のリスト登録要素数(これを会員番号とする)

addList 関数では主に下記の2つの処理を行なっています。

①要素の追加とデータの登録

要素の追加というのは単純に malloc 関数を行うことです。malloc 関数で LIST 構造体1つ分のメモリを確保することで、要素が一つ増えたことになります。メモリ上のどこに配置されたかは item ポインタに指させておいて覚えさせています。

続いて item ポインタが指す LIST 構造体の各メンバに、会員番号と引数で指定された名前を代入しています。

要素の追加先はリストの最後ですので、あらかじめ次の要素を指す next には NULL を設定しています。

②リストへの追加

さらに、リストの先頭要素から順に next を辿っていき、next が NULL(リストの最後)の要素を見つけたら、NULL の代わりに先ほど動的追加した要素のアドレス(item ポインタの指す先)を代入する事でリストへの追加を完了します。最後に リストの先頭アドレスを返却して関数を終了します。

このプログラムでは main 関数でリストの先頭アドレスを知っておきたいため、addList 関数はリストの先頭アドレスを返すようにしています。

リストが空の場合以外は、要素を追加してもリストの先頭アドレスは変わりませんので、第一引数で指定されたアドレス(top 変数に覚えさせているアドレス)が返却値となります。

しかしリストが空の場合は追加した要素がリストの先頭になりますので、追加した要素のアドレス(malloc の戻り値)を引数で list により指定されたアドレスを返却する事になります。

addList の関数部分のみを再掲しておきます。

/* 会員情報をリストの最後に追加し、リストの先頭アドレスを返却する関数 */
struct LIST* addList(struct LIST *list, char *name, unsigned int number){
  struct LIST *item;
  struct LIST *top;

  top = list;

/* ここから①の処理 */
  item = (struct LIST*)malloc(sizeof(struct LIST));
  item->number = number;
  strcpy(item->name, name);
  item->next = NULL;
/* ここまで①の処理 */

/* ここから②の処理 */
  /* リストが空の場合は先頭に追加して終了 */
  if(list == NULL){
    list = item;
    return list;
  }

  /* リストのnextを辿ってリストの最後を探す */
  /* リストの最後とは、nextがNULLの要素 */
  while(list->next != NULL){
    list = list->next;
  }
  list->next = item;
/* ここまで②の処理 */

  /* ここでreturnする場合は先頭アドレスは変わらない */
  return top;
}

リストへ要素が追加される様子

リストに要素が追加されていく様子を図を使って見ていきましょう。

リストが空の状態で「会員番号:1・名前:太郎」の会員情報を追加する場合、malloc してメンバに代入した直後のメモリ配置は下記のようになっています。矢印の出ていない●は NULL を表しています。

(かなり簡略化したイメージ図になります。実際は会員番号や名前を格納するためのメンバの箱の大きさは大きく異なります。イメージしやすくするための簡略化ですのでご了承ください)

item が動的に追加された要素のアドレスを指しています。

次にこの要素をリストに追加します。今回はリストが空なので、リストの先頭アドレスを指す list に追加した要素のアドレス(item ポインタ)をセットします。

これが一つ目の要素を追加するときのメモリ観点で見た流れです。

次に「会員番号:2・名前:花子」追加してみましょう。malloc してメンバに代入した後は下図のような状態になります。list はリストの先頭アドレスを、item は追加された要素の先頭アドレスを指しており、この二つに現状繋がりはありません。

次に行うのがリストの最後に要素を追加する処理です。まず、リストの先頭要素(list が差している要素)から、next が NULL のものを探し出します。今回は先頭要素がそれにあてはまります。その next に NULL ではなく新しく追加した要素のアドレスを入れてやると下の図のようになり、ポインタが他の要素を指す事でリスト上の要素同士が繋がります

さらに要素を追加する場合も同様の流れで、malloc で動的に要素を追加し、追加された要素のアドレスをリストの最後の要素の next に指させてやることで、どんどんリストを長くしていくことができます。

今回はリストの最後に追加するプログラムを書いていますが、もちろん先頭や途中に追加するプログラムも作成可能です。

リストからの削除(deleteList関数)

次にリストから要素を削除する dleteList 関数について説明します。

引数として渡される変数は下記の2つになります。

  • list:リストの先頭要素のアドレス
  • number:削除する会員番号

addList 関数では主に下記の2つの処理を行なっています。

①引数で指定された会員番号の要素を探索

まず行うのは指定された会員番号を持つ要素の探索です。これは単純にリストの先頭 “list” から順に “next” をたどりながら “number(構造体のメンバの方)” の値と指定された会員番号 “number(引数の方)” が一致するかどうかを判断することで探索することが可能です。

②要素の削除

続いて一致した要素を削除します。

ただリスト構造の場合、単に要素を消すだけではダメなので注意が必要です。

下の図を見れば分かると思いますが、途中の要素を単に削除してしまうと、そこでリストが切れてしまいます。会員番号3の要素を指しているポインタが無くなったので、もはや会員番号3の要素にたどり着く事ができません。たどり着く事ができないので、その会員番号3の要素は見つけることもできませんし、消すこともできませんのでメモリリークとなります。

この要素削除時のリストの途切れを防ぐために重要なのは、要素を削除する前に削除する要素の next が指すアドレスを他の変数に退避しておくことです。

なので要素を削除する時のステップは下記のようになります。

・削除する要素の next の指すアドレスを退避

・要素を削除
・削除する要素の前の要素の next に退避したアドレスをセット

例えば下の図で緑色の要素を削除する場合は、一旦 temp に緑色の要素の next が指すアドレスを格納して退避させています。

退避した後に、緑色の要素を削除し、緑色の要素の前の要素である青色の要素の next に temp に退避させていたアドレスをセットします。これによりリストが途切れることなく要素の削除を行うことができます。

最後に deleteList 関数部分のみを再掲しておきます。

/* 会員情報を削除し、リストの先頭アドレスを返却する関数 */
struct LIST* deleteList(struct LIST *list, unsigned int number){
  struct LIST *tmp;
  struct LIST *top;
  top = list;

  /* 先頭ノードの場合だけ別処理 */
  if(list != NULL && list->number == number){
    tmp = list->next;
    free(list);

    /* 次の要素のアドレスをリストの先頭アドレスとして返却 */
    return tmp;
  }

  /* リストを辿って指定された会員番号の要素を探す */
  /* ここから①の処理 */
  while(list != NULL){
    if(list->next->number == number){
      /* ここから②の処理 */
      tmp = list->next->next;
      free(list->next);
      list->next = tmp;
      /* ここから②の処理 */
      return top;
    }
    list = list->next;
  }
  /* ここまで①の処理 */
  printf("Number %d not found!\n", number);

  return top;
}

久しぶりにリスト構造のプログラム作ってましたが、実はこの削除関数の作成は結構苦労しました…。でも図を描きながらプログラム書くと上手く行かないところも修正する事ができました。やっぱりポインタは図で理解して、図で考えるのが良いと思います。

リストの全削除(deleteAllList 関数)

最後にリストの要素を全削除する deleteAllAlist 関数について解説します。

引数は下記の通りです。

  • list:リストの先頭要素のアドレス

この関数で行なっていることは単純で、list で指定されたリストの先頭から順に要素を削除していくという処理になります。

next が NULL の要素がリストの終端ですので、この要素を削除したら関数を終了します。

ただこの関数においても deleteList 関数同様にいきなり要素を削除すると次の要素を辿れなくなってしまいますので、削除する前に一旦 tmp に削除する要素の次の要素のアドレスを退避するようにしています。

最後に deleteAllList 関数部分のみを再掲しておきます。

/* 会員情報を全て削除する関数 */
struct LIST* deleteAllList(struct LIST *list){
  struct LIST *tmp;

  while(list != NULL){
    tmp = list->next;
    free(list);
    list = tmp;
  }

  return NULL;
}

まとめ

  • リスト構造実装はポインタの理解を深めるのに最適
  • リストの各要素はポインタによって繋がれる
  • リストの要素の追加・削除をする処理を実装してポインタの動きの理解を深めよう

オススメ参考書

リスト構造のようなデータ構造を学ぶのであれば下記参考書がオススメです。データ構造についてはもちろんのこと、アルゴリズムについてもC言語プログラムを読んだり実際に作ったりしながら学ぶ事が可能です。

●新・明解 C言語で学ぶアルゴリズムとデータ構造

他のデータ構造について

キューの解説やC言語ソースコードも下記で解説しています。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です