【C言語】リスト構造について分かりやすく解説【図解】

リスト構造の解説ページアイキャッチ

SHARE

このページにはプロモーションが含まれています

このページでは、データ構造の１つである “リスト構造” について解説していきます！

データ構造やアルゴリズムなどの授業で必ず学ぶのが、このリスト構造です。

色々考えてみたのですが、ポインタの理解を深める上でリスト構造ってかなりいいテーマだなと思います。

下記のあたりがリスト構造を実現する上でのプログラミングのポイントです。

これらは全てポインタに関連する処理であり、リスト構造のプログラムを作成するだけでこれらに触れることができます。

  • 次のノードをポインタで指すことでノード同士に繋がりを持たせる
  • ノードを作成する際に動的にメモリを確保する
  • ノードが不要になったら確保したメモリを解放する
  • リストの終端は NULL かどうかで判断する

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

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

このページでは、まずリスト構造の概要について解説します。ここでリスト構造の特徴や、配列との違いについて説明していきます。

その次に、リストのノードに対する操作の説明や、それらの操作を行う関数の作り方について解説し、最後にリスト構造を用いた C言語 のサンプルプログラムの紹介をしていきます。

もう既にリスト構造の概要をご存知の方や、早くリスト構造の実装の仕方を知りたいという方は、リストのノードへの操作 までスキップしていただければと思います。

リスト構造に関しても、ポインタ同様に図を使って考えるとわかりやすいです。このページでは図をたくさん使って分かりやすく解説していますので、是非図にも注目しながら解説を読んでいっていただければと思います！

リスト構造

では、まずはリスト構造の概要について解説していきたいと思います！

リスト構造とは

リスト構造はデータ構造の１つ（データの管理の仕方の１つ）で、図で表せば下の図のようなデータ構造になります。

リスト構造を１枚絵で表した図

上の図における、１つ１つの要素のことを “ノード” と呼びます。

ノードの説明図

より具体的に言えば、リスト構造とは下記の２つの特徴を持つデータ構造です。

  • 各ノードは “データ部” と “ポインタ部” の２つから構成される
  • “ポインタ部” を辿ることによって各ノードの “データ部” にアクセスできる

各ノードは “データ部” と “ポインタ部” の２つから構成される

リスト構造におけるノードは、主に下記の２つのデータから構成されます。

  • データ部
  • ポインタ部
    ノードがデータ部とポインタ部から構成されることを表した図

まず前者のデータ部には、リストで管理したいデータが格納されます。

例えばあなたがお店を経営していて、会員様の情報を管理したいのであれば、下記のようなデータがデータ部に格納されることになります。

  • 会員番号
  • 会員名
  • 電話番号
  • 住所

また、ポインタ部には次のノードを示すデータが格納されます。

このページでは、この “次のノードを示すデータ” としてアドレスを使用していきたいと思います。

アドレスを格納する変数はポインタですので、要は各ノードはポインタを持っていることになります。

そして、そのポインタに次のノードの先頭アドレスを格納することで、そのノードのポインタが次のノードを指すことになります。

各ノードがポインタで次のノードを指す様子

このように各ノードの持つポインタに次のノードを指させることで、各ノード同士が順序性を持って繋がることになります。この、ポインタ部によって繋がったノード全体をまとめて “リスト” と呼びます。

リストの説明図

イメージが付きやすいように、ここまで解説してきた内容を具体例を用いて振り返っていきたいと思います。

例えば、先程も例に挙げた会員情報の “会員番号” と “会員名” がデータ部に格納されるようなノードは、下記の構造体を定義することで表現することが可能です。

ノード構造体 
struct NODE {
    int number; /* 会員番号 */
    char name[256]; /* 会員名 */
    struct NODE *next; /* 次のノード */
};

number と name がデータ部にあたり、next がポインタ部にあたります。

さらに、この next は次のノードを指すポインタであり、指す対象のデータはノード構造体で表現される他のノードですので next の型は struct NODE * である必要があります。

例えば下記のように処理を行えば、node1 の次の位置に node2 が、node2の次の位置に node3 が存在するようなリストを作成することができます（head はリストの先頭ノードを指すポインタ）。

リストの作成例 
struct NODE node1, node2, node3;
struct NODE *head;

/* node1の次の位置にあるノードを設定 */
node1.next = &node2;

/* node2の次の位置にあるノードを設定 */
node2.next = &node3;

/* node3の次の位置にあるノードはなし */
node3.next = NULL;

/* リストの先頭ノードを設定 */
head = &node1;

上記実行後のリストは下の図のようになります。

リストの作成例を実行後のリストの様子を示した図

こんな感じで、各ノードをポインタで繋げていくところが、リスト構造におけるポイントの１つになります。

以降でも、ポインタ部はポインタであることを前提に解説していきます。

ですが、このポインタ部はポインタでなくてもリスト構造は実現可能です。例えば配列の添字でも良いです（これは配列そのものがリスト構造であると言っているわけではない点に注意してください）。

要は、ポインタ部によって次の位置のノードが分かるようになっていれば良いです。

また、ここまでの解説ではポインタで次の位置のノードを指すものとして解説してきましたが、ポインタに前の位置のノードを指させても良いですし、ポインタを２つ用意し、次の位置のノードと前の位置のノードの両方を指させるようにしても良いです。

特に、ノードの持つポインタによって次の位置のノードと前の位置のノードの両方を指すようなリストを “双方向リスト” と呼びます。

双方向リストの説明図

それに対し、一方向のみをポインタによって指させるようなリストを “単方向リスト” と呼びます。

単方向リストの説明図

双方向リストは単方向リストを応用すれば簡単に実現できますので、今回は基本となる単方向リストについて解説していきます（次の位置のノードのみを指す単方向リスト）。

“ポインタ部” を辿ることによって各ノードの “データ部” にアクセスできる

前述の通り、リスト構造におけるノードは “ポインタ部” であるポインタを持っており、このポインタで次の位置のノードを指すことで、ノード同士が繋がることになります。

ですのでリスト構造では、このポインタで各ノードを辿ることで、そのノードの “データ部” のデータにアクセス（取得したり変更したり）することが可能です。

例えば、ノードのデータ部に整数が格納されている下の図のようなリストにおいて、データ部が 3 であるノードを探索することを考えてみましょう。

ノードを辿っていく例１

この場合、リストの先頭から順にポインタを頼りにノードを辿っていきながら各ノードのデータ部が 3 であるかどうかを確認していくことで、データ部が 3 であるノードを見つけ出すことができます。

ノードを辿っていく例２

また、例えば先頭から N 番目のノードのデータ部を取得したいような場合も、リストの先頭から順にポインタでノードを辿っていくことで実現することができます。

このように、リスト構造においては、”ノード自体が持つ情報” から他のノードを辿って各ノードのデータ部にアクセスすることができます。

そしてこれを行うためには、ノードにはデータ部だけでなくポインタ部が必要になります。

スポンサーリンク

配列とのデータ構造の違い

ここまで解説してきたように、リスト構造におけるノードには “データ部” と “ポインタ部” が必要です。前述の通り、今回はポインタ部をポインタとしています。

その一方で、配列におけるノードが持つのはデータ部のみです（このページでは配列の要素のことをノードを呼ばせていただきます）。配列にはポインタ部は不要です。

なぜ配列では、ポインタ部は不要なのでしょうか？

その答えは、配列の各ノードはメモリの配置的に、”次のノードが必ず次のアドレス” に存在するという制約があるからです。要は、各ノードの先頭アドレスから 配列の型のサイズ 進んだアドレスに、そのノードの “次のノード” が必ず存在します。

配列のノードにポインタ部が不要であることを説明する図

つまり、どこに次のノードがあるかが分かりきっているので、わざわざポインタ部を設けて次のデータを指すようなことはしなくても良いのです。

ただ、アドレスで考えると複雑になりがちなので、配列では添字演算子（[]）を用いることで、上記のような位置関係のアドレスを自動的に算出して各ノードにアクセスできるようになっています。

配列でのノードへのアクセス 
int array[10];

/* "array[0]の先頭アドレス+int型のサイズ"
    のアドレスのノードのデータ部に100を格納 */
array[1] = 100;

/* "array[0]の先頭アドレス+5*int型のサイズ"
    のアドレスのノードのデータ部に200を格納 */
array[5] = 200;

その一方で、リスト構造におけるノードはノード自身がポインタ（次のノードを示すデータ）を持っています。

ですので、そのポインタを適切に設定さえすれば、各ノードがメモリの配置的にどのアドレスに存在したとしても各ノードに順序性を持たせることができます。

リスト構造の各ノードがアドレス的にどの位置にあっても問題ないことを示す図

ですので配列とは異なり、各ノードが配置されているアドレスに制約はありません（配列の場合は次のノードが次のアドレスに必ず存在する必要がある）。これにより、次に説明するように、ノードの追加やノードの削除が容易になるというメリットがあります。

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

前述の通り、リスト構造の各ノードはポインタを持っており、そのポインタで次のノードを指すことで、ノード同士に繋がり・順序性を持たせることが可能です。

次は、このポインタでノード同士に繋がり・順序性を持たせることによるメリットとデメリットについて解説していきます（主に配列に対して比較を行なった際の、メリットとデメリットについて解説していきます）。

メリット

まず、リスト構造には “データの追加や削除が容易” であるというメリットがあります。

例えば、下の図のように配列の途中にデータを追加したいような場合について考えてみましょう。

配列へのデータの追加に必要な処理を説明する図１

この場合、まず追加したい位置以降のデータを全て１つずつ後ろ側に移動する必要があります。そして移動した後に、追加したい位置に実際にデータを追加する必要があります。

配列へのデータの追加に必要な処理を説明する図２

上の図の場合、データ数が少ないのでそんなに処理は必要なさそうにも見えますが、データ数が多ければ多いほど処理量が増えて負荷が高くなってしまいます。

そのような処理をデータを追加するたびに繰り返すのは非効率です。

その一方でリスト構造の場合、追加したい位置の “前側にあるノードのポインタ” に追加するノードを指させ、さらに “追加するノードのポインタ” に追加したい位置の後ろ側のノードを指させるだけで、データの追加が完了します。

リストへのノードの追加に必要な処理を説明する図

データの個数に関係なくこの一連の処理のみで追加が完了するので、追加時の効率が高いです。

削除もほぼ同様の理由から、リスト構造の方が効率的に行うことができます。

デメリット

リスト構造のデメリットとしては、”ノードへのアクセスが遅い” ことが挙げられます。

前述の通り、配列ではノードが存在する位置が予め決まっています。

ですので、例えば配列の先頭から３番目のノードであれば必ず次のアドレスに存在します。

配列の先頭から３番目のノードのアドレス 
配列の先頭アドレス + 2 * (配列の型のサイズ）

図で示すと下の図のような位置に、先頭から３番目のノード（ノード３）は必ず存在します。

配列のノードが決まった位置に存在することを示す図

配列の場合は、どこに先頭から３番目のノードが存在するかが分かっているので、そのアドレスに直接アクセスするだけで先頭から３番目のノードにアクセスすることが可能です。

さらに C言語 では、配列に対して添字演算子（[]）を利用することで、上記のアドレスのノードにアクセスすることができます。

例えば、配列名を array とすれば、array[2] と記述するだけで、先頭から３番目のノードにアクセスすることができます（配列の先頭の添字は 0 なので、３番目のノードにアクセスする場合は [2] を指定する必要があります）。

上記のように、配列のノードがどの位置に存在するかが分かっているのは、配列には “次のノードが必ず次のアドレス” に存在するという制約があるからです。

その一方で、リスト構造の場合は上記の制約はなく、ノード自身が次のノードをポインタで指すことで、どのアドレスに存在するノードであっても繋がりを持たせることができます。

リストのノードが決まった位置に存在しないことを示す図

逆に考えると、リスト内のノードはどのアドレスにでも存在しうることになります。

なので、配列の時のように配列の先頭アドレスからノードのアドレスを算出したり、添字演算子を用いて直接ノードにアクセスするようなことはできません。

リストの場合、ノードのアドレスを知っているのは、その前の位置のノードだけです（ポインタで次のノードのみを指す単方向リストの場合）。

ノード４のアドレスを知っているのがノード３だけであることを示す図

したがって、特定のノードにアクセスしたい場合は、まずは一旦その前の位置にあるノードにアクセスする必要があります。

ノード４にアクセスするためには、事前にその前の位置のノード３にアクセスする必要があることを示す図

ただ、この前の位置にあるノードのアドレスを知っているのは、さらにその前側の位置にあるノードです。なので、まずはこのノードにアクセスする必要があります。

ノード３にアクセスするためには、事前にその前の位置のノード２にアクセスする必要があることを示す図

こんな感じで、特定のノードにアクセスしたい場合は、その前のノードにアクセスする必要があるため、結局リストの先頭のノードからノードを一つ一つ辿っていく必要があります。

特定のノードにアクセスする場合はリストの先頭からノードを辿っていく必要があることを示す図

このノードを辿っていくという処理が必要な分、配列に比べてリスト構造の方がノードへのアクセスは遅いです。

また、リストのノードにアクセスする場合、基本的には前述の通りリストの先頭ノードからノードを辿っていく必要がありますので、リストを使用する場合は “リストの先頭のノードを指すためのポインタ” を別途用意する必要があります。

リストの先頭ノードを指すポインタの説明図

リストのノードへの操作

大体リスト構造の概要については理解していただけたでしょうか？

次は、リストのノードに対する下記の操作について、C言語 のソースコードも使用しながら具体的に説明していきたいと思います。

  • ノードを探索する
  • ノードを追加する
  • ノードを削除する

まず前提として、ノードを表す構造体である NODE を定義したいと思います。この NODE は、リスト構造とは で例として挙げた下記を利用したいと思います。

ノード構造体 
struct NODE {
    int number; /* 会員番号 */
    char name[256]; /* 会員名 */
    struct NODE *next; /* 次のノード */
};

さらに、リストの先頭のノードを指すポインタ変数を下記の head としたいと思います（今回はこの head はグローバル変数として宣言しているものとして解説していきます）。

ノード構造体 
struct NODE *head;

リストにノードがある場合、head には先頭のノードを指させますが、もしリストが空の場合（ノードが１つもない場合）は、 head には NULL を指させることにしたいと思います（つまり head == NULL が成立するかどうかで、リストが空であるかどうかを判断できる）。

この head と各ノードの関係を図で表すと下図のようになります。

headと各ノードの関係図

ここで重要なのが、末尾のノードの next には必ず NULL を指させておくことです。なぜ重要なのかは、次の ノードを探索する で解説します。

また、各ノードの青色部分は “データ部” で、ここに NODE 構造体の number と name が存在します。さらに、オレンジ色部分は “ポインタ部” で、ここに NODE 構造体の next が存在します。

今後示す図においても、上の図のようにこれらの情報は省略していますのでご注意ください。

スポンサーリンク

では、リストのノードに対する操作について解説していきます。

最初は “ノードを探索する” 操作について解説します。おそらくリストに対する操作の中で一番簡単なのが、この “ノードを探索する” 操作です。

ここでは、ノードの会員番号が target であるノードを探索する例を用いて解説していきます。

先ほどもお見せした通り、リストの各ノードは head を用いて下図のような構成になっています。

headと各ノードの関係図

ですので、要はリストの先頭（つまり head が指すノード）から順番にノードを辿りながら、そのノードの会員番号（つまり number メンバ）が target と一致するかを調べていけば良いです。

より具体的には、下記のように、まずはポインタ変数 node に head が指すノードを指させ、node の number メンバが target と一致するかどうかを調べます（わざわざ node に head を指させているのは、以降の処理と処理を共通化するためです）。

先頭のノードを調べる 
struct NODE *node;

node = head;

if (node->number == target) {
    /* 探索したいノードが見つかった時の処理 */
}

node は head が指すのと同じノードを指していますので、上記の処理ではリストの先頭ノードの number が target と一致するかどうかの判断を行なうことになります。

nodeとheadが同じノードを指していることを示す図

もし一致すれば node の指すノード（つまりリストの先頭のノード）が目当てのノードとなりますので、この時点で探索終了です。

一致しなければ、次のノードの会員番号を調べていきます。

では、この次のノードが何であるかというと、これは node->next が指すノードですね！

node->nextが、nodeの次のノードであることを示す図

つまり、次のノードを辿るためには、node に node->next が指すのと同じノードを指させれば良いことになります。

より具体的には下記を実行すれば、node が現在指しているノードの、次の位置のノードを node に指させることができます。

次のノードを辿る 
node = node->next;

これにより、下の図のように node が次のノードを指したことになります。

nodeが指すノードが次の位置のノードに移動したことを示す図

ですので、再度下記を行えば、今度は先ほど調べたノードの次のノードを調べることができます。

次のノードを調べる 
if (node->number == target) {
    /* 探索したいノードが見つかった時の処理 */
}

一致すれば、この node が探索したいノードと判明するので探索は終了です。

一致しなかった場合は、先ほどと同様に node = node->next を実行して node に次のノードを指させて同様の処理を行なっていけば良いです。

後はこの繰り返しで、リスト内のノードをポインタで辿りながらデータを探していくことになります。

このノードをポインタで辿りながらデータを探していく処理は、下記のようなループで実現することが可能です（target と一致する number メンバを持つノードのアドレスを返却するようにしています）。

ノードを探索する無限ループ 
node = head;

while (1) {

    if (node->number == target) {
        /* 探索したいノードが見つかった */

        return node;
    }

    /* 次のノードを辿る */
    node = node->next;

}

ただし上記の場合、もし target と一致する number メンバを持つノードがリスト内に存在しなければ、無限にループが続けられてしまうことになります。

ですので、target と一致する number メンバを持つノードがリスト内に存在しない場合でも、リストの全てのノードを調べ終わったらループを終了させるための対応が必要です。

このために重要になるのが、リストの末尾のノードの next メンバに NULL を指させておくことです。

末尾のノードのnextがNULLを指していることを示す図

これにより、node が末尾のノードを指した状態で node = node->next を実行すると自動的に node が NULL に設定されるようになります。

さらに、node が末尾のノードを指した状態で node = node->next を実行して次のノードを辿ろうとしているということは、この時点でリストのノード全てを調べ終わっていることになります。

つまり、node が NULL かどうかで、リストの全てのノードを調べ終わったかどうかを判断することができるようになります。

したがって、リストの末尾のノードの next メンバに NULL を指させるようにし、上記のループ処理を次のように書き換えれば（while (1) を while (node != NULL) に変更）、リストのノードを全て調べ終わった時に自動的にループが終了するように制御することが可能です。

ノードを探索するループ 
node = head;

while (node != NULL) {

    if (node->number == target) {
        /* 探索したいノードが見つかった */

        return node;
    }

    /* 次のノードを辿る */
    node = node->next;

}

ただし、もし、リストの末尾のノードの next メンバに NULL を指させていなかった場合、上記のループは無限に続いてしまうことになるので、この NULL を指させることを欠かさず行う必要があります。

MEMO

ソースコード的には無限に続きますが、実際には、そのうちアクセスしてはいけないメモリにアクセスしてメモリ違反が発生してプログラムが異常終了します

といっても、末尾のノードに NULL を指させるのは、今解説している探索時ではなく、リストにノードを追加するときやノードを削除した時になります。

これらについては ノードを追加する と ノードを削除する で解説していきます。

また、先ほども紹介した下記のようなノードを辿っていくループは今後もいろんなところで登場しますので、是非動作を理解しておいてください。

ノードを探索するループ 
node = head;

while (node != NULL) {

    /* 何かしらの処理 */

    /* 次のノードを辿る */
    node = node->next;

}

ノードの探索を行う関数

ここまでの解説を踏まえた、引数 target と一致する number メンバを持つノードを探索する search 関数は次のようになります。

search 
struct NODE * search(int target){
    struct NODE *node; /* 今注目しているノードのアドレス */

    /* リストの先頭のノードに注目 */
    node = head;

    while (node != NULL) {

        if (node->number == target) {
            /* 探索したいノードが見つかった */

            return node;
        }

        /* 次のノードを辿る */
        node = node->next;

    }

    /* targetを持つノードが見つからなかった */
    return NULL;
}

head はグローバル変数であることを想定した関数になっています（以降に紹介する関数も同様になります）。

ちなみに、ここまで説明を省いてきましたが、ソースコード中に現れる -> はアロー演算子と呼ばれる演算子になります。

このアロー演算子については、下記ページで詳しく解説していますので、使い方がよく分からないという方は是非下記ページを読んでいただければと思います。

C言語のアロー演算子（->）を分かりやすく、そして深く解説

ノードを追加する

続いてリストに “ノードを追加する” 操作について解説していきます。

この “ノードを追加する” 操作と、次に説明する “ノードを削除する” 操作では、ノード同士がしっかり繋がるようにポインタの設定を行うところが最大のポイントになります。

ここでは、会員番号を number、会員名を name とするノードを追加する例を用いて説明していきたいと思います

このノードを追加する操作は、大きく分けると下記の２つの手順により実現することができます。

  • ノードを作成する
  • ノード間のポインタを設定する

前者については、下記の処理により実現することができます。

ノードの作成 
struct NODE *new;

new = (struct NODE*)malloc(sizeof(struct NODE));

new->number = number;
strcpy(new->name, name);

１行目では malloc 関数を利用して NODE 構造体のサイズ分のメモリを確保しています。このメモリを new に指させることで、この new の指すメモリを NODE 構造体の変数同様に扱うことができます（これは new が struct NODE * 型のポインタだからです）。

mallocで確保したメモリをnewに指させる様子

さらに、この new の指す NODE 構造体の各メンバに number と name を格納すれば、ノードが作成されたことになります（name は文字列なので strcpy を利用して格納しています）。

後は、この追加したノードおよび周辺のノードのポインタを設定すればノードの追加は完了なのですが、このポインタの設定は下記の２つの場合でやり方が異なるので、その点に注意が必要です。

  • ノードを追加する位置がリストの “先頭以外” の場合
  • ノードを追加する位置がリストの “先頭” の場合

ノードを追加する位置がリストの “先頭以外” の場合

まずはノードを追加する位置がリストの “先頭以外” の場合のポインタの設定の仕方について解説していきます。

この場合、例えばリストの下の図の位置にノードを追加するのであれば、

ノードを追加する位置を示す図

ノードを追加した後に、下の図のように各ポインタが他のノードを指すようにする必要があります。

ノード追加後の各ノードのポインタの指す先を示した図

このようなポインタの設定は、追加するノードを指すポインタ変数を new、追加する位置の前側に存在するノードを指すポインタ変数を prev、追加する位置の後ろ側に存在するノードを指すポインタ変数を node とすれば、下記を行うことで実現することができます。

ノード追加時のポインタの設定（先頭以外） 
prev->next = new;
new->next = node;

図で表すと下の図のようになります。

ノード追加時に変更したポインタを示す図

ここで重要になるのが、追加する位置の前側と後ろ側のノード２つを指すためのポインタ変数が必要であると言う点です（書き方を工夫すればポインタ変数１つでもおそらく上手くいくとは思います）。

例えばですが、リストの各ノードが number メンバに対して昇順に並ぶようにノードを追加する場合、ノードを探索する と同じ要領で、下記のように node->number > new-> number を満たすまでポインタを辿っていけばノードを追加すべき位置が分かります。

昇順を満たす位置を探索する 
struct NODE *node;

node = head;

while (node != NULL) {
    if (node->number > new->number) {
        break;
    }

    node = node->next;
}

この場合、ループ終了時の node の前側に new を追加すれば、リストの各ノードが number メンバに対して昇順に並んだ状態を維持したままノード（new）を追加することができます。

ただ、これだと追加後に new の前側に存在すべきノードがどれだか分かりません…。ノードからは次の位置のノードは分かりますが、前の位置のノードは分からないのです…。

つまり、先程の解説で登場した prev 相当の情報がありません。ですので、これだけだとノードの追加を行うことができません。

これを解決する単純な解決法は、下記のようにポインタ変数 prev を用意し、この prev に node の１つ前のノードを指させるようにすることです。

nodeの前のノードを覚えておく 
struct NODE *node;
struct NODE *prev;

node = head;

while (node != NULL) {
    if (node->number > new->number) {
        break;
    }
    prev = node;
    node = node->next;
}

この場合、ループ終了時の node の１つ前のノードを prev が指していることになります。

また、new は node の１つ前のノードとして追加することになるので、要は prev と node の間に new を追加することになります（prev は new 追加前の node の前のノード）。

ですので、上記で node と prev を決めた後に、前述でも示した下記を実行することで new の指すノードの追加が完了します。

ノード追加時のポインタの設定（先頭以外） 
prev->next = new;
new->next = node;

ノードを追加する位置がリストの “先頭” の場合

続いてノードを追加する位置がリストの  “先頭” の場合のポインタの設定の仕方について解説していきます。

この場合、例えばリストが下の図のようなノードから構成されるのであれば、

ノードを追加する位置を示す図

ノードを追加した後に、下の図のように各ポインタが他のノードを指すようにする必要があります。

ノード追加後の各ノードのポインタの指す先を示した図

head はリストの先頭のノードを指すポインタ変数ですので、このようなポインタの設定は、追加するノードを指すポインタ変数を new とすれば、下記を行うことによりノードの追加が完了することになります。

ノード追加時のポインタの設定（先頭） 
new->next = head;

head = new;

まず１行目で new->next に head が指しているのと同じノードを指させ、

new->next=headの処理の意味の解説図

２行目でリストの先頭ノードを new を設定しています。

head=newの処理の意味の解説図

ポイントは、上記の２つの処理のうち、必ず new->next = head の方を先に実行しなければならないという点です。

head は元々リストの先頭ノードを指しているポインタですが、head = new を先に行ってしまうと、その head が new を指してしまい、リストの先頭ノードを指しているポインタが無くなってしまいます。

先にhead=newを実行したときの問題点を示す図

そうなると、new->next がどこを指せば良いかが分からなくなってしまいます。

ただ、下記のように、他のポインタ変数で head が指すノードを覚えておくようにすれば、head = new を先に実行しても問題ないです。

リストの先頭を他のポインタで覚えておく 
struct NODE *tmp;

tmp = head;

head = new;

new->next = tmp;

こんな感じで、ポインタの設定を行う場合は順番も重要になることも多いので気をつけてください。

ノードの追加を行う関数

ここまでの解説を踏まえたノードの追加を行う add 関数は次のようになります。追加するノードのデータ部は、引数 number と引数 name で与えられるものとしています。また、リストの全ノードが number に対して昇順に並ぶようにノードの追加を行なっています。

add 
int add(int number, char *name){
    struct NODE *new; /* 追加するノードのアドレス */
    struct NODE *node; /* 今注目しているノードのアドレス */
    struct NODE *prev; /* nodeの前のノードのアドレス */

    /* ノードを新規追加 */
    new = (struct NODE*)malloc(sizeof(struct NODE));
    if (new == NULL) {
        return -1;
    }

    new->number = number;
    strcpy(new->name, name);

    /* リストの先頭のノードに注目 */
    node = head;

    /* ノードを追加する位置を決める */
    while (node != NULL) {
        if (node->number > new->number) {
            /* 追加する位置が見つかった */
            break;
        }

        /* nodeを前のノードとして覚えておく */
        prev = node;

        /* 次のノードを辿る */
        node = node->next;
    }

    if (node == head) {
        /* 追加する位置がリストの先頭の場合 */

        /* 元々先頭だったノードをnewの次のノードにする */
        new->next = head; /* リストが空の場合はheadはNULL */

        /* リストの先頭をnewとする */
        head = new;

    } else {
        /* 追加する位置がリストの先頭以外の場合 */

        /* prevとnodeの間にnewを追加 */
        prev->next = new;
        new->next = node; /* 追加する位置が末尾の場合ははnodeはNULLになっている */
    }

    return 0;
}

この add 関数は、追加に成功した場合は 0 を、削除に失敗した場合は -1 を返却するようにしています。-1 を返却するのは malloc 関数に失敗した場合（つまり、もうメモリが取得できなくなった場合）のみです。

ノードを探索する で、リストの末尾のノードの next に NULL を指させることが大事と言っていたわりに、NULL を設定する箇所がないので拍子抜けした方もおられるかもしれません。

確かに上記の add 関数では明示的には NULL を設定していませんが、それでもリストの末尾のノードの next には NULL が設定されるようになっています（一応コメントでその点を補足しているつもりです）。

また、今回はリストの先頭ノードを指す head をグローバル変数としているので問題ないのですが、もし head を引数で受け取るような場合は注意してください。

特に、下記のように head を struct NODE * 型の引数にしてしまうと、ノードの追加に失敗します。

add（headを引数とする場合のダメな例） 
int add(struct NODE *head, int number, char *name) {
    /* 略 */
    head = new; /* 関数呼び出し元に反映されない */
    /* 略 */
}

この場合、head = new を行ったとしても、関数呼び出し側の変数は変更されません。関数呼び出し側の変数を変更したいのであれば、下記のように struct NODE ** 型の引数にする必要があります。

add（headを引数とする場合の良い例） 
int add(struct NODE **head, int number, char *name) {
    /* 略 */
    *head = new; /* 関数呼び出し元に反映される */
    /* 略 */
}

要はポインタのポインタとして引数で受け取る必要があります。この head を引数として受け取る場合の注意点に関しては、次に紹介するノードを削除する delete 関数においても同様です。

ポインタのポインタについては下記ページで解説していますので、ポインタのポインタについて詳しく知りたい方は是非読んでみてください。

ポインタのポインタ解説ページアイキャッチ 【C言語】ポインタのポインタ（ダブルポインタ）を解説【図解】

上記の add 関数では、リストの各ノードが number に対して昇順に並んだ状態を維持するように位置を決めてノードを追加していますが、while (node != NULL) のループ部分を変更することでノードを追加する位置を変更することも可能です。

例えば降順に並んだ状態を維持したいのであれば、if (node->number > new->number) を if (node->number < new->number) に変更すれば良いです（比較を > ではなく < で行うようにする）。

毎回必ずリストの末尾にノードを追加したい場合は、この if 文そのものを削除すれば良いですし、毎回必ずリストの先頭にノードを追加したい場合は、while (node != NULL) のループそのものを削除すれば良いです。

ノードを削除する

最後にリストから “ノードを削除する” 操作について解説していきます。

ここでは、会員番号が target であるノードを削除する例を用いて説明していきたいと思います

このノードを削除する操作は、大きく分けると下記の２つの手順により実現することができます。

  • ノード間のポインタを設定する
  • ノード自体を削除する

後者の “ノード自体を削除する” については、今回ノードの作成を malloc 関数でメモリを確保することで行っていますので、そのメモリを解放することで実現することができます。要は free 関数を実行すれば良いです。

ですので、削除したいノードをポインタ変数 node が指しているのであれば、下記によりノード自体を削除することができます。

ノード自体を削除する 
free(node);

ただし、ノード自体の削除だけを行ってしまうと、その削除されたノードの前後のノードに繋がりがなくなってしまうので注意してください。これらのノードのポインタを設定した後に、ノード自体の削除を行う必要があります。

また、このポインタの設定は、ノード追加時同様に下記の２つの場合でやり方が異なります。

  • 削除するノードがリストの “先頭以外” の場合
  • 削除するノードをリストの “先頭” の場合

削除するノードがリストの “先頭以外” の場合

まずは、削除するノードがリストの “先頭以外” の場合のポインタの設定の仕方について解説していきます。

この場合、例えば下の図の node が指すノードを削除するのであれば、

削除するノードを示す図

ノードを削除した後に、下の図のように各ポインタが他のノードを指すようにする必要があります。

ノード削除後の各ノードのポインタの指す先を示した図

このようなポインタの設定は、削除するノードを指すポインタ変数を node、削除するノードの前側に存在するノードを指すポインタ変数を prev とすれば、下記を行うことにより実現することができます。

ノード削除時のポインタの設定（先頭以外） 
prev->next = node->next;

ノードを追加する時同様に、削除するノードだけでなく、その削除するノードの前側に存在するノードを指すポインタ変数も必要であることに注意してください（上記における prev）。

この点に関しては、ノードを追加する で解説していますので、詳しく知りたい方は コチラ を参照していただければと思います。

削除するノードがリストの “先頭” の場合

続いて削除するノードがリストの “先頭” の場合のポインタの設定の仕方について解説していきます。

この場合、例えば下の図の node が指す先頭ノードを削除するのであれば、

削除するノードを示す図

ノードを削除した後に、下の図のように各ポインタが他のノードを指すようにする必要があります。

ノード削除後の各ノードのポインタの指す先を示した図

この場合はわかりやすいですね！

削除するノードを指すポインタ変数を node とすれば、リストの先頭を指すポインタ変数 head に node->next を指すようにすれば良いだけです。

ノード削除時のポインタの設定（先頭） 
head = node->next;

ノードの削除を行う関数

ここまでの解説を踏まえた、引数 target を会員番号とするノードを削除する delete 関数は次のようになります（number を会員番号とするノードが複数リスト内に存在する場合、先に見つけた方を削除します）。

delete 
int delete(int target){
    struct NODE *node; /* 今注目しているノードのアドレス */
    struct NODE *prev; /* nodeの前のノードのアドレス */

    if (head == NULL) {
        /* リストが空なら何もしない */

        return -1;
    }

    /* リストの先頭のノードに注目 */
    node = head;

    if (node->number == target) {
        /* 削除対象がリストの先頭のノードの場合 */

        /* リストの先頭をnodeの次のノードにしてnodeを削除 */
        head = node->next;
        free(node);

        return 0;
    }

    while (node != NULL) {

        if (node->number == target) {
            /* 削除対象のノードが見つかった */

            /* prevの次のノードをnodeの次のノードに設定 */
            prev->next = node->next;

            /* 削除対象のノードを削除して終了 */
            free(node);

            return 0;
        }

        /* nodeを前のノードとして覚えておく */
        prev = node;

        /* 次のノードを辿る */
        node = node->next;

    }

    /* targetを持つノードが見つからなかった */
    return -1;
}

この delete 関数は、削除に成功した場合は 0 を、削除に失敗した場合、つまり target を会員番号とするノードをが見つからなかった場合は -1 を返却するようにしています。

注意点は、必ず free を行う前にポインタの設定を行う必要があるという点です。

例えば下記のように、free を行った後にポインタの設定を行うのはダメです。

メモリアクセス違反が発生する例 
free(node);
prev->next = node->next;

C言語 では、free を行ったポインタの先のメモリへのアクセスはご法度です（上記の場合、node->next がダメ）。プログラムが落ちる可能性もあります。ですので、必ずポインタの設定を行なった後に free を実行するようにしましょう。

スポンサーリンク

その他の操作

以上が、リストのノードに対する下記の３つの操作の解説になります。

  • ノードを探索する
  • ノードを追加する
  • ノードを削除する

これらはリストのノードに対する基本的な操作であり、他にも例えば下記のような操作が必要となる場合もあります。

  • 末尾のノードの “データ部” を取得して末尾のノードを削除する
  • 先頭から N 番目のノードを削除する
  • 先頭から N 番目の位置にノードを追加する

ただ、おそらくこれらは今回解説した操作を応用すれば簡単に作成できるのではないかと思います。

このページではこれらの操作については解説しませんが、興味のある方はぜひ自身で上記の操作を行う関数を作成してみてください。

リスト構造を利用したプログラムの例

最後に、ここまで解説してきた内容のおさらいとして、リスト構造を利用した会員情報の登録・削除・探索を行うプログラムを紹介しておきます。

このプログラムのソースコードは下記のようになります。

会員情報をリストで管理するプログラム 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

/* 会員情報を登録する構造体 */
struct NODE {
    int number; /* 会員番号 */
    char name[256]; /* 会員名 */
    struct NODE *next; /* 次のノード */
};

void print(void);
void finalize(void);
int add(int , char *);
int delete(int);
struct NODE * search(int);

/* リストの先頭を指すポインタ */
static struct NODE *head = NULL;

/******************************
 * 全てのノードのデータを表示する関数
 ******************************/ 
void print(void){
    struct NODE *node;

    node = head;
    while (node != NULL) {
        printf("%d:%s\n", node->number, node->name);
        node = node->next;
    }
}

/******************************
 * 全てのノードを削除する関数
 ******************************/ 
void finalize(void){
    int target;

    while (head != NULL) {
        /* まだリストが空でない場合 */
        
        /* 先頭のノードを削除 */
        target = head->number;
        delete(target);
    }
}


/******************************
 * リストにノードを追加する関数
 * number：追加するノードの会員番号
 * name：追加するノードの会員名
 * 返却値：0（成功時）
 *      ：-1（失敗時）
 ******************************/ 
int add(int number, char *name){
    struct NODE *new; /* 追加するノードのアドレス */
    struct NODE *node; /* 今注目しているノードのアドレス */
    struct NODE *prev; /* nodeの前のノードのアドレス */

    /* ノードを新規追加 */
    new = (struct NODE*)malloc(sizeof(struct NODE));
    if (new == NULL) {
        return -1;
    }

    new->number = number;
    strcpy(new->name, name);

    /* リストの先頭のノードに注目 */
    node = head;

    /* ノードを追加する位置を決める */
    while (node != NULL) {
        if (node->number > new->number) {
            /* 追加する位置が見つかった */
            break;
        }

        /* nodeを前のノードとして覚えておく */
        prev = node;

        /* 次のノードを辿る */
        node = node->next;
    }

    if (node == head) {
        /* 追加する位置がリストの先頭の場合 */

        /* 元々先頭だったノードをnewの次のノードにする */
        new->next = head; /* リストが空の場合はheadはNULL */

        /* リストの先頭をnewとする */
        head = new;

        

    } else {
        /* 追加する位置がリストの先頭以外の場合 */

        /* prevとnodeの間にnewを追加 */
        prev->next = new;
        new->next = node; /* 追加する位置が末尾の場合ははnodeはNULLになっている */
    }

    return 0;
}

/******************************
 * リストからノードを削除する関数
 * targetr：削除するノードの会員番号
 * 返却値：0（成功時）
 *      ：-1（失敗時）
 ******************************/ 
int delete(int target){
    struct NODE *node; /* 今注目しているノードのアドレス */
    struct NODE *prev; /* nodeの前のノードのアドレス */

    if (head == NULL) {
        /* リストが空なら何もしない */

        return -1;
    }

    /* リストの先頭のノードに注目 */
    node = head;

    if (node->number == target) {
        /* 削除対象がリストの先頭のノードの場合 */

        /* リストの先頭をnodeの次のノードにしてnodeを削除 */
        head = node->next;
        free(node);

        return 0;
    }

    while (node != NULL) {

        if (node->number == target) {
            /* 削除対象のノードが見つかった */

            /* prevの次のノードをnodeの次のノードに設定 */
            prev->next = node->next;

            /* 削除対象のノードを削除して終了 */
            free(node);

            return 0;
        }

        /* nodeを前のノードとして覚えておく */
        prev = node;

        /* 次のノードを辿る */
        node = node->next;

    }

    /* targetを持つノードが見つからなかった */
    return -1;
}

/******************************
 * リストからノードを探索する関数
 * target：探索するノードの会員番号
 * 返却値：見つかったノードのアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
struct NODE * search(int target){
    struct NODE *node; /* 今注目しているノードのアドレス */

    /* リストの先頭のノードに注目 */
    node = head;

    while (node != NULL) {

        if (node->number == target) {
            /* 探索したいノードが見つかった */

            return node;
        }

        /* 次のノードを辿る */
        node = node->next;

    }

    /* targetを持つノードが見つからなかった */
    return NULL;
}

int main(void){
    int operation;
    int inputnumber;
    int number;
    char inputname[256];
    struct NODE *node;
    int ret;

    srand(time(NULL));

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

        if(operation == 1){
            /* 必要な情報を取得してリストにノード追加 */

            printf("add name = ");
            scanf("%s", inputname);

            /* 会員番号をランダムに決定 */
            number = rand() % 10;

            /* リストに追加 */
            ret = add(number, inputname);
            if (ret == -1) {
                printf("add error!\n");
            }

        } else if (operation == 2) {
            /* 必要な情報を取得してリストからノード削除 */
            
            printf("delete number = ");
            scanf("%d", &inputnumber);

            /* 指定された会員番号を持つノードを削除 */
            ret = delete(inputnumber);
            if (ret == -1) {
                printf("delete error!\n");
            }

        } else if (operation == 3) {
            /* 必要な情報を取得してリストからノード探索 */
            
            printf("search number = ");
            scanf("%d", &inputnumber);

            /* 指定された会員番号を持つノードを探索 */
            node = search(inputnumber);
            if (node == NULL) {
                printf("search error!\n");
            } else {
                printf("name is %s\n", node->name);
            }

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

        print();

    }

    finalize();

    return 0;
}

プログラムをコンパイルして実行すれば、下記のようなメッセージが表示されます。

operation(1:add, 2:delete, 3:search, etc:exit) =

ここで、1 or 2 or 3 or それ以外の数字 の入力後にエンタキーを入力すれば、入力された数字に応じて下記の処理が行われます。

  • 1：会員情報の追加
  • 2：会員情報の削除
  • 3：会員情報の探索
  • それ以外の数字：終了処理

1・2・3 が入力された場合は必要な情報の入力が促されたりしますが、要は 1 が入力された場合は add 関数、2 が入力された場合は delete 関数、3 が入力された場合は search 関数が実行されてノードに対して操作が行われるようになっています。

また、これらの操作が行われた際には、リストで保持している全ノードのデータ部（会員番号と会員名）を表示するようになっています。

この辺りの入力受付や、入力値に応じた処理の振り分けは main 関数で行っていますので、詳しくは main 関数を読んでいただければと思います。

rand 関数や srand 関数を使用していますが、これらの関数をご存知ない方は、下記ページで解説していますので下記ページを参照していただければと思います。

C言語で乱数を扱う方法の解説ページアイキャッチ C言語で乱数を扱う方法（rand関数とsrand関数）

また、このプログラムで扱うノードを表現する NODE 構造体や、リストのノードに対して操作を行う関数 search・add・delete は リストのノードへの操作 で紹介しているものと全く同じです。

他には下記の関数を用意していますが、これらの関数で行っていることは、リストのノードへの操作 で解説した内容で網羅できていると思いますので、ここでの解説は省略させていただきます。

  • print：全ノードのデータ部（会員番号と会員名）を表示する関数（リストの先頭のノードから順に表示）
  • finalize：リストを空にする関数（リストの全ノードを削除する）

まとめ

このページでは、データ構造の１つであるリスト構造について解説しました！

リスト構造のポイントは “ノード同士を繋げる必要がある” ところです。そして、そのノード同士はポインタによって繋げることができます。

このノード同士を繋げる必要がある点は面倒でもあるのですが、ノード同士を適切に繋げてやりさえすれば、各ノードがメモリ上のどの位置にあっても良いため、ノードの追加や削除の処理効率が高いというメリットもがあります。

ポインタに慣れていない方にとっては、リスト構造を理解するのは大変かもしれません。ですがその分、リスト構造の実現方法を理解したり実際に実装したりすることでポインタに慣れることが出来ると思います！

特に今回はノードをポインタが指す様子を図で表現してきましたが、ポインタを利用した実装に悩んだ時は、こんな感じで図を書くとポインタの動作を整理しやすくなりますので、この点も参考にしていただければと思います！

リスト構造同様に、基本的なデータ構造として木構造があります。その木構造の特に二分探索木についての解説やプログラムの作り方は下のページで解説していますので、こちらも是非読んでみてください！

二分探索木解説ページのアイキャッチ C言語で二分探索木（木構造・ツリー構造）をプログラミング

リスト構造よりもちょっと難易度は高いですが、その分プログラムを作ってみるとさらに C言語 やポインタの理解を深めることができるはずです。

また、スタックやキュー（これらもデータ構造）についても、下記ページで解説していますので、こちらも是非読んでみていただければと思います！おそらくこっちはリスト構造よりも簡単だと思います！

スタックとキューの配列での実装方法解説ページアイキャッチ 【C言語/データ構造】スタックとキューの配列での実装方法

さらに、キューはポインタで実現することが可能であり、この方法については下記ページで解説しています！こちらはかなりリスト構造に近いので、リスト構造の復習にも是非ご活用ください！

キューのポインタでの実装方法解説ページアイキャッチ 【C言語】キューのポインタでの実装方法

オススメ参考書（PR）

リスト構造のようなデータ構造を学ぶのであれば下記 の 新・明解C言語で学ぶアルゴリズムとデータ構造 参考書がオススメです。

データ構造についてはもちろんのこと、アルゴリズムについてもC言語プログラムを読んだり実際に作ったりしながら学ぶ事ができます。

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

posted with ヨメレバ
柴田望洋 SBクリエイティブ 2021年05月20日頃
楽天ブックス
Amazon
7net

同じカテゴリのページ一覧を表示

4 COMMENTS

Kちゃん

structを毎回省略したくて、下記の書き方にしたけど、通りませんでした。構造体を再帰的に使用する場合、structを省略して、LIST型の変数を作るのはできないのでしょうか。

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

daeu

Kちゃんさん

コメントありがとうございます。
struct 毎回書くの面倒ですよね…。

下記のように書くのはいかがでしょうか？

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

構造体定義の時に一緒に typedef するとコンパイル通らないですが、
上記のように別々に記述するとコンパイル通るはずです（一応コンパイル通ること確認してます）。

また何か不明点などありましたら、ご気軽にコメントいただければと思います！

Kちゃん

ご回答ありがとうございます！
新たな型を宣言するtypedefは、型の中身を後で定義することができるんですね。
型宣言についての曖昧だったところ含めてクリアになりました！
ありがとうございます^^

daeu

Kちゃんさん

コメントありがとうございます！
上手くいったようでよかったです。
また何か不明点などありましたら気軽にコメントしていただけると幸いです。

現在コメントは受け付けておりません。

次の記事

【C言語/データ構造】スタックとキューの配列での実装方法
スタックとキューの配列での実装方法解説ページアイキャッチ