今回は《線形リストの基礎を学ぼう》というテーマで記事をまとめます。
「線形リスト」は配列同様、複数の要素をひとまとめにするデータ構造です。「線形リスト」を習得すると、効率的なプログラムを作成することができます。
強力な技術であり、開発者としては必須の技術の１つなのでしっかり学んでいきましょう！
尚、現在執筆中のC言語入門記事は以下の人を対象としています。
- プログラミング未経験の人
- C言語プログラミングの学習をこれから始めたい人
- C言語プログラミングの学習を始めたばかりの人
線形リストの基礎を学ぼう
線形リストとは
線形リストとは、「データ部とポインタを持つ構造体」を用いてリスト形状に連結するデータ構造です（単に「リスト」と呼ぶこともあります）。配列は固定長でしたが、線形リストは可変長という特性を持ちます。
そして、線形リストにおける構造体のオブジェクト１つのことを『ノード』と呼びます。
実際のプログラムコードとそれに対応したノードのイメージは次のようになります。
そして、複数のノードを連結した線形リストのイメージは次のようになります。
まずはベタ書きで線形リストを作ってみよう！
まずは細かいことを考えずにベタ書きで下図のようなイメージを作成してみましょう。
１．先頭ポインタを用意
struct mydata* root = NULL;
２．ノード①を生成、先頭ポインタにアドレスを代入
struct mydata* pdata1 = NULL; pdata1 = (struct mydata*)malloc( sizeof(struct mydata) ); pdata1->data = 1; pdata1->next = NULL; /* 生成時に必ずNULLを代入しましょう */ root = pdata1; /* 先頭ポインタに代入 */
３．ノード②を生成、ノード①の次ポインタ（next）にアドレスを代入
struct mydata* pdata2 = NULL; pdata2 = (struct mydata*)malloc( sizeof(struct mydata) ); pdata2->data = 1; pdata2->next = NULL; /* 生成時に必ずNULLを代入しましょう */ pdata1->next = pdata2; /* ノード①の次ポインタに代入 */
▽まとめ
ここまでのお話をまとめました。
struct mydata* root = NULL; struct mydata* pdata1 = NULL; struct mydata* pdata2 = NULL; pdata1 = (struct mydata*)malloc( sizeof(struct mydata) ); pdata1->data = 1; pdata1->next = NULL; /* 生成時に必ずNULLを代入しましょう */ pdata2 = (struct mydata*)malloc( sizeof(struct mydata) ); pdata2->data = 2; pdata2->next = NULL; /* 生成時に必ずNULLを代入しましょう */ root = pdata1; /* 先頭ポインタに代入 */ pdata1->next = pdata2; /* ノード①の次ポインタに代入 */
線形リストのノード表示
次に、作成済みの線形リストに対して各ノードを表示する方法を解説します。
１．参照用ポインタを用意
struct mydata* ptr = NULL; /* 参照用ポインタ */
２．参照用ポインタに先頭ポインタ（ノード①のアドレス）を代入
ptr = root;
３．参照用ポインタ（ノード①）の情報を表示
printf( "data : %d\n", ptr->data );
４．参照用ポインタに次ポインタ（ノード②）を代入
ptr = ptr->next;
５．参照用ポインタ（ノード②）の情報を表示
printf( "data : %d\n", ptr->data );
まとめ
struct mydata* root = NULL; /* 先頭ポインタ */ /* ～線形リスト作成処理（割愛）～ */ struct mydata* ptr = NULL; /* 参照用ポインタ */ /* 参照用ポインタに先頭ポインタ（ノード①のアドレス）を代入 */ ptr = root; /* 参照用ポインタ（ノード①）のノードを表示 */ printf( "data : %d\n", ptr->data ); /* 参照用ポインタに、次ポインタ（ノード②のアドレス）を代入 */ ptr = ptr->next; /* 参照用ポインタ（ノード②）のノードを表示 */ printf( "data : %d\n", ptr->data );
【更に向こうへ】線形リストの全ノード表示
上記まとめの書き方では、線形リストに追加されているノードの数だけプログラムコードを書く必要があります。これでは不便でしょうがありませんね。
そこで、線形リストの全ノードを表示するサンプルを用意しました。
線形リストにノードを複数個追加した上で実行してみてください。全てのノードが表示されるハズです。
struct mydata* root = NULL; /* 先頭ポインタ */
/* ～線形リスト作成処理（割愛）～ */
struct mydata* ptr = NULL; /* 参照用ポインタ */
ptr = root;
while( ptr != NULL ){
printf( "data : %d\n", ptr->data );
ptr = ptr->next;
}
サンプル
それでは、サンプルを用意したので実行してみてください。
尚、本来であれば、malloc関数で確保したメモリを解放する必要がありますが、今回は省略します。
メモリの解放は、次回解説予定の『ノードの削除』を学習したあとにメジャーな実装方法を解説したいと思います。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
/* 構造体の定義 */
struct person_info_node {
char name[10];
int age;
struct person_info_node* next;
};
/* ノードの追加関数 */
void addNode(struct person_info_node** root, struct person_info_node* tgtNode, struct person_info_node* newNode) {
struct person_info_node* tmp = NULL;
if (*root == NULL) {
/* 線形リストが空（先頭ポインタがNULL）の場合、先頭に追加 */
*root = newNode;
}
else {
/* 対象ノードの後ろに追加 */
tgtNode->next = newNode;
}
}
/* 全てのノード情報を表示 */
void dispAll(struct person_info_node* root) {
struct person_info_node* node = NULL;
printf( "## 全情報表示\n" );
node = root;
while (node != NULL) {
printf( "name = \"%s\"\n", node->name );
printf( "age = %d\n", node->age );
printf( "\n" );
node = node->next;
}
}
void main() {
int i = 0;
int num = 0;
struct person_info_node* root = NULL;
struct person_info_node* node = NULL;
struct person_info_node* nodePre = NULL;
printf( "登録する人数を入力してエンターキーを押してください。:" );
scanf( "%d", &num );
printf( "\n" );
for( i = 0; i < num; i++ ){
/* 新規登録するノードを作成 */
node = (struct person_info_node*)malloc(sizeof(struct person_info_node));
printf( "登録データ No.%d\n", i + 1 );
printf( "名前:" );
scanf( "%s", node->name );
printf( "年齢:" );
scanf( "%d", &(node->age) );
node->next = NULL;
printf( "\n" );
/* 追加 */
addNode( &root, nodePre, node );
/* 前回追加したノード（末尾のノード）を保存しておく */
nodePre = node;
}
/* 全データ表示 */
dispAll( root );
/* 本来はmallocで確保したメモリをここで解放する必要がある */
/* （今回は省略します） */
}
まとめと次回予告
今回、線形リストの基礎として次の内容を学んでもらいました。
- 線形リストの基本構造
- ノードの追加
- ノードの表示
次回以降は線形リスト基礎編の続編として、次の２つを予定しています。
- ノードの挿入
- ノードの削除
上記を習得できれば、「線形リストは習得済み」と胸を張って言えるでしょう！
ご期待ください。