【C言語入門の次】 第04回 連結リスト

https://youtu.be/93uVys5N3_Q

$\textcolor{pink}{四国めたん: }$教師役ですわ

$\textcolor{lime}{ずんだもん: }$生徒役なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ こんにちは。四国めたんです

$\footnotesize \textcolor{lime}{ずんだもん:}$ ずんだもんなのだ。こんにちはなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回の データ構造 は、 連結リスト ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 連結リスト ？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、リストとしては、かなりポピュラーですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ 配列リスト とは異なり、データの挿入や削除が容易におこなえますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ その辺りを詳しく教えて欲しいのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ わかりましたわ

連結リストとは

$\footnotesize \textcolor{pink}{四国めたん:}$ 前回の 配列リスト では、データの挿入、削除で、多くのデータの移動が発生していましたわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ たしかに...

$\footnotesize \textcolor{pink}{四国めたん:}$ データ数が少なければいいのですが、10万件、100万件とかのデータサイズとなると、それなりの負荷がかかりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 結構、時間がかかって煩わしいのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ また、配列のサイズが足りなくならないよう、予め大きなサイズの配列を準備しなければなりませんでしたわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ メモリの利用効率を大きく下げることとなるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ これら 配列リスト のデメリットを解消するのが 連結リスト ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

連結リストの構造

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは 連結リスト の構造についてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 実は 連結リスト の構造は至って簡単ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、データを保持する構造体に、次のデータを指すポインタを追加するだけですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ データの項目を1つだけ増やせばいいのなら、簡単なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、このポインタを使って、チェーンのようにデータを 連結 していきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 連結リスト では、これらのデータを ノード と云いますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ノード ...わかったのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ チェーンの最後の ノード のポインタにはNULLを指定して、ノードが最後であることを示しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 例えば、student構造体を 連結リスト にする場合には、このように定めますわ

typedef struct student {
  unsigned int id;
  char name[20];
  struct student* pnext;
} student;

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところで、構造体中で次のノードへの型はstudentへのポインタではなく、struct studentへのポインタとしているが、なぜなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ これは、typedefによるstudent型の定義が不完全な状態なので、student型の指定ができないためですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ もし、studentへのポインタにしたい場合には、事前にstudent型の定義をおこなう必要がありますわ

typedef struct student student;
struct student {
  unsigned int id;
  char name[20];
  student* pnext;
};

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところで 連結リスト のイメージがわかないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ イメージ的にはこのようになりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお"pnext"には、次のノードの先頭のメモリアドレスを代入しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

実際に連結リストを使ってみよう

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず 連結リスト を作って使ってみましょう

students.h

#pragma once
#ifndef _INC_STUDENTS
#define _INC_STUDENTS

#include <stdio.h>

#define NAME_SIZE (20)

typedef struct student {
  unsigned int id;
  char name[NAME_SIZE];
  struct student* pnext;
} student;

typedef struct {
  student* pstudents;
  size_t num;
} student_list;

int init_student_list(student_list* plist);

void final_student_list(student_list* plist);

student* at(student_list* plist, size_t idx);

int delete(student_list* plist, size_t idx);

int insert(student_list* plist, size_t idx, unsigned int id, char name[]);

int push(student_list* plist, unsigned int id, char name[]);

int pop(student_list* plist);

#endif  // _INC_STUDENTS

$\footnotesize \textcolor{pink}{四国めたん:}$ まずstudent構造体を定義しているヘッダーファイルですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ student_list構造体は何なのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ リストを管理するための構造体ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ 必要なのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、リストの現在の要素数などを保存しておくなど、利便性がいいので使っていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ヘッダーファイルでは、リストの初期化や終了処理、ノードの挿入、削除、参照のための関数の宣言をおこなっていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、全ての関数は、第1引数にstudent_list構造体へのポインタを指定していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

students.c

#include "students.h"

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

student* get_student(int id, char name[]) {
  student* pstudent = (student*)malloc(sizeof(student));
  if (pstudent != NULL) {
    pstudent->id = id;
    snprintf(pstudent->name, NAME_SIZE, "%s", name);
    pstudent->pnext = NULL;
  }
  return pstudent;
}

int init_student_list(student_list* plist) {
  plist->pstudents = get_student(0, "");
  plist->num = 0;
  return (plist->pstudents == NULL) ? -1 : 0;
}

void final_student_list(student_list* plist) {
  student* pstudent = plist->pstudents;
  student* pnext = NULL;
  while (pstudent != NULL) {
    pnext = pstudent->pnext;
    free(pstudent);
    pstudent = pnext;
  }
  plist->num = 0;
  plist->pstudents = NULL;
  return;
}

student* at(student_list* plist, size_t idx) {
  student* pstudent = NULL;
  if (idx < plist->num) {
    pstudent = plist->pstudents->pnext;
    for (size_t i = 0; i < idx; i++) {
      pstudent = pstudent->pnext;
    }
  }
  return pstudent;
}

int delete(student_list* plist, size_t idx) {
  int rc = -1;
  if (idx < plist->num) {
    student* pstudent = plist->pstudents;
    for (size_t i = 0; i < idx; i++) {
      pstudent = pstudent->pnext;
    }
    if (pstudent->pnext != NULL) {
      student* p2delete = pstudent->pnext;
      pstudent->pnext = p2delete->pnext;
      free(p2delete);
      plist->num--;
      rc = 0;
    }
  }
  return rc;
}

int insert(student_list* plist, size_t idx, unsigned int id, char name[]) {
  int rc = -1;
  if (idx <= plist->num) {
    student* pstudent = plist->pstudents;
    for (size_t i = 0; i < idx; i++) {
      pstudent = pstudent->pnext;
    }
    student* pnew_student = get_student(id, name);
    if (pnew_student != NULL) {
      pnew_student->pnext = pstudent->pnext;
      pstudent->pnext = pnew_student;
      plist->num++;
      rc = 0;
    }
  }
  return rc;
}

int push(student_list* plist, unsigned int id, char name[]) {
  int rc = insert(plist, plist->num, id, name);
  return rc;
}

int pop(student_list* plist) {
  int rc = -1;
  if (plist->num > 0) {
    rc = delete (plist, plist->num - 1);
  }
  return rc;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは関数の定義をおこないましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

初期化関数

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、初期化の関数としてinit_student_listを定義しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 初期化関数ではどのようなことをおこなうのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ 名前の通りstudent_listの初期化ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 具体的には？

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、get_student関数で、"id"が0、"name"が空欄のstudentのノードを取得しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ get_student関数？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、"id"と"name"を指定して、新規のノードであるstudent構造体のメモリ領域を生成して返す関数ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ 新規のノードのメモリ領域の取得はmalloc関数を用いているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、メモリ領域の取得が成功すれば、引数で渡された"id"と"name"を配列の要素にコピーしていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 次のノードへのポインタ"pnext"は、NULLで初期化しているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、作成したノードは 連結リスト の先頭として"pstudents"にセットしていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ "id"が0、"name"が空欄のノードをセットする意味があるのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、これはダミーのノードで、 連結リスト の操作を簡単にするための工夫ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ 一般的には ダミーノード と呼ばれ、ダミーを表すデータを格納しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 今回は"id"を0、"name"を空欄にしたのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに ダミーノード を作成せず、"pstudents"にNULLをセットすることも可能ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ ただ、"pstudents"にNULLがセットされている場合に特別な処理をおこなう必要があるので少し面倒ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は ダミーノード を使いますわ

終了関数

$\footnotesize \textcolor{pink}{四国めたん:}$ つぎはstudent_listの終了処理をおこなうfinal_student_list関数を定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ この関数では"pstudents"にセットされた 連結リスト のノードを順番にfree関数で開放していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 具体的には？

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、開放するデータへのポインタを"pstudent"にセットしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ ループ内では、次に開放するノードへのポインタを"pstudent->pnext"から"pnext"に退避しておきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、free関数で"pstudent"にセットしたノードのメモリ領域を開放しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に退避していた次のノードへのポインタ"pnext"を次に開放するノードへのポインタとして"pstudent"に移しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして全てのノードを開放するまでループを継続しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ループの終了条件は、"pstudents"がNULLになった時、つまり 連結リスト の最後のノードが開放された時となっているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ その通りですわ

データ取得関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次はデータを取得する関数atの定義ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ データを取得するとは？

$\footnotesize \textcolor{pink}{四国めたん:}$ student_listの 連結リスト から指定のインデックスのstudentデータを取得する関数ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、 連結リスト は 配列リスト とは異なり、各データはメモリ上にバラバラに配置されていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 配列リスト では、インデックスを指定するだけで配列からデータを取り出せたのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ですが、 連結リスト では、インデックスを指定するだけではデータを取り出せませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 連結リスト の場合は、地道に先頭からノードのリンクを辿っていって指定のノードを見つけるしかありませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 連結リスト のデメリットなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは動作について簡単にお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ おねがいするのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最初に引数に指定したインデックスがノードの数未満であることを確認しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ インデックスがノード数以上であれば、データが無いとしてNULLを返すのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に"student_list"の 連結リスト の先頭のノードへのポインタを"pstudent"にセットしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ダミーノード はスキップしているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次にループを使って、"pstudent"に"pstudent->pnext"を代入し、リストを辿っていきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ インデックスの数だけノードを辿れば指定のデータを取得できるのだ

データ削除関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次は指定のインデックスの位置のデータを削除する関数 delete の定義ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 連結リスト の指定のインデックスの部分からstudentデータのノードを取り除くのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、まずat関数と同様の手法で、インデックスの1つ手前のノードを取得し、"pstudent"に代入しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、指定のインデックスがノード数以上の場合にはstudentデータのノードの削除はおこないませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところでstudentデータの削除はどうするのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、削除するstudentデータのノードへのポインタ"pstudent->pnext"を"p2delete"として退避しておきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、"pstudent->pnext"を次の次のstudentデータのノードへのポインタ"p2delete->pnext"に置き換えますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ これで 連結リスト から指定のインデックスのstudentデータのノードを切り離すことができましたわ

$\footnotesize \textcolor{pink}{四国めたん:}$ あとは切り離したstudentデータのメモリ領域をfree関数で開放し、ノード数を減らしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

データ挿入関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次は指定のインデックスの位置にデータを追加する関数insertの定義ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 連結リスト の指定のインデックスの部分にstudentデータを挿入するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、まずat関数と同様の手法で、インデックスの1つ手前のノードを取得し、"pstudent"に代入しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、指定のインデックスがノード数を超える場合にはデータの挿入は失敗しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次にget_student関数を使って、新しいstudentデータを取得し"pnew_student"に代入しておきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 新しいstudentデータのノードへの挿入はどうするのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、"pstudent"が指す、次のノードへのポインタ"pstudent->pnext"を、"pnew_student"の指す次のノードへのポインタ"pnew_student->pnext"にコピーしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、"pstudent"が指す次のノードへのポインタ"pstudent->pnext"を新しいノードへのポインタ"pnew_student"に置き換えますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ あとはノード数を増やして、指定のインデックスの部分へのstudentデータの挿入は完了ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

pushとpop

$\footnotesize \textcolor{pink}{四国めたん:}$ push関数は 連結リスト の最後にstudentデータのノードを追加する関数ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ また、pop関数は 連結リスト の最後からstudentデータのノードを削除する関数ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ いずれもstudent_listの中のノード数を表す要素"num"からインデックスを取得していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そのインデックスでinsert関数やdelete関数を呼び出しているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ その通りですわ

メイン関数

$\footnotesize \textcolor{pink}{四国めたん:}$ それではメイン関数で 連結リスト を使ってみましょう

main.c

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

#include "students.h"

int main(int argc, char* argv[]) {
  student_list list;
  int rc = init_student_list(&list);
  if (rc == 0) {
    push(&list, 1, "佐藤紬");
    push(&list, 2, "鈴木陽翔");
    push(&list, 3, "高橋翠");
    push(&list, 4, "田中朝陽");
    push(&list, 5, "伊藤凛");
    delete (&list, 2);
    insert(&list, 2, 6, "渡辺暖");
  }

  for (size_t i = 0; i < list.num; i++) {
    student* pstudent = at(&list, i);
    printf("学生番号: %d, 名前: %s\n", pstudent->id, pstudent->name);
  }

  final_student_list(&list);

  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数内では、まずstudent_list型の"list"をinit_student_list関数で初期化していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次にpush関数で5人分のデータを追加していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、delete関数でインデックス2のデータを削除し、insert関数でインデックス2の位置に新たなデータを追加していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 後はループを使って人数分のデータを出力していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ studentデータの取得はat関数を使用しているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最後にfinal_student_list関数で終了処理をおこなっていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 終了処理はたいせつなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず実行してみましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ 問題なくデータが表示されているのだ

まとめ

$\footnotesize \textcolor{pink}{四国めたん:}$ お疲れさまでした

$\footnotesize \textcolor{lime}{ずんだもん:}$ おつかれさまなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 以上で 連結リスト を終了しますわ