今回は≪線形リストの挿入を学ぼう≫というテーマで記事をまとめています。
今回解説する『ノードの挿入』と次回解説予定の『ノードの削除』を習得すれば、ポインタの真理にかなり近づいたといっても過言ではありません。頑張りましょう！
「線形リスト」の基礎（基礎概念と表示）を習得していない場合、まずは次の記事で学習してきてください。
尚、現在執筆中のC言語入門記事は以下の人を対象としています。
- プログラミング未経験の人
- C言語プログラミングの学習をこれから始めたい人
- C言語プログラミングの学習を始めたばかりの人
線形リストの挿入を学ぼう
ノード挿入の基本ロジック
まずはノード挿入の基本ロジックを解説します。今回は、次の線形リストのノード①の後ろにノード③を挿入したいと思います。
尚、ノード①は何かしらの方法で取得できた体で話を進めさせてもらいます。
１．ノード③を生成
struct mydata* pdata3 = NULL; pdata3 = (struct mydata*)malloc( sizeof(struct mydata) ); pdata3->data = 3; pdata3->next = NULL; /* 生成時に必ずNULLを代入しましょう */
２．一時保存用ポインタにノード①の次ポインタを代入
/* ※ノード①は何かしらの方法で取得したものとする */ struct mydata* ptmp = NULL; ptmp = pdata1->next;
３．ノード①の次ポインタにノード③のアドレスを代入
pdata1->next = pdata3;
４．ノード③の次ポインタに一時保存用ポインタを代入
pdata3->next = ptmp;
まとめ
上記のコードをまとめると次のようになります。
struct mydata* pdata1 = NULL;
struct mydata* pdata3 = NULL;
struct mydata* ptmp = NULL;
/* ～ ノード①のアドレス取得処理 ～ */
pdata3 = (struct mydata*)malloc( sizeof(struct mydata) );
pdata3->data = 3;
pdata3->next = NULL; /* 生成時に必ずNULLを代入しましょう */
ptmp = pdata1->next;
pdata1->next = pdata3;
pdata3->next = ptmp;
さて、１点だけ補足をしておきます。
一時保存用ポインタにノード①の次ポインタを代入していますが、何故でしょう？
その理由は、処理②でノード①の次ポインタが上書きされてしまうからです。つまり、ノードの入れ替えを行うには、一度別の変数にノードを待避する必要があるということです。
この「ノードの入れ替えを行う処理」についてデジャヴを感じている方がいると思います。
そうですね、swap関数と同じ原理です。
「swap関数とはなんぞや？」という方は下記記事を元に学習することをオススメします。
【ノードの挿入処理を拡張】先頭に挿入するには？
さて、ノードの挿入方法の基本を学んでいただいたところで、ふと疑問に思う方もいるでしょう。
「『"新規ノード"と"挿入したいノードの次ポインタ"と入れ替えを行う』なんて言うけど、先頭に挿入する場合は"次ポインタ"が存在しないよ。・・どうしたらいいの？」
答えは簡単です。"ダブルポインタを使用"して挿入するのです。
ダブルポインタについての理解に自信がない方は、まずこちらの記事を参考に学習してみてください。
ダブルポインタを使用
それでは、ダブルポインタを使って挿入する方法を解説します。
ダブルポインタで参照するのは『先頭ポインタ』または『挿入先ポインタの次ポインタ』です。
入れ替えロジックそのものは変わりません。ソースコードは次のようになります。
struct mydata** pptgt = NULL; /* 挿入先ダブルポインタ */ struct mydata* pnew = NULL; /* 新規ポインタ */ struct mydata* ptmp = NULL; /* ～ 新規ノードの生成 ～ */ /* ～ 挿入先ノードのアドレス取得処理 ～ */ /* 例① pptgt = &root; */ /* 例② pptgt = &(pdata1->next); */ ptmp = *pptgt; *pptgt = pnew; pnew->next = ptmp;
【参考】挿入先ポインタの取得方法
ノードの挿入方法は概ね理解してもらえたかとと思います。
しかし、挿入先ポインタの取得方法について、具体的なコードのイメージが湧かないと思うので簡単な例を紹介します。
今回紹介するのは「挿入位置（番号）を指定して挿入先ポインタを取得する」処理です。
指定位置に０を指定した場合は先頭に、１以上を指定した場合は該当する番号の後ろに挿入するようにポインタを取得します。
struct mydata* root = NULL; /* 先頭ポインタ */
struct mydata** pptgt = NULL; /* 挿入先ポインタ */
int i = 0;
int insPos = 0; /* 挿入位置 */
/* 挿入位置をユーザ入力 */
printf("挿入位置:");
scanf("%d", &insPos);
/* 先頭ポインタのアドレス取得 */
pptgt = &root;
/* 線形リストが空でない場合は検索 */
if( *pptgt != NULL ){
/* 入力された挿入位置に該当するノードを検索 */
for (i = 0; i < insPos; i++) {
if (*pptgt == NULL) {
/* 次ポインタがない */
pptgt = NULL;
break;
}
pptgt = &( (*pptgt)->next );
}
}
else{
if(insPos > 0){
/* 線形リストが空なのに1以上が入力された */
pptgt = NULL;
}
}
if( pptgt != NULL ){
/* ～ 挿入処理を実行 ～ */
}
else{
printf("挿入可能範囲外です。\n");
}
サンプル
それでは、ここまでのお話をまとめたサンプルを用意しました。実行してみてください。
#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;
};
/* 挿入先ポインタの取得（挿入先が見つからなかった場合、NULL） */
struct person_info_node** getInsNode(struct person_info_node** pproot, int insPos) {
int i = 0;
struct person_info_node** pptgt = NULL;
/* 先頭ポインタのアドレスを設定 */
pptgt = pproot;
/* 線形リストが空でない場合は検索 */
if (*pptgt != NULL) {
/* 入力された挿入位置に該当するノードを検索 */
for (i = 0; i < insPos; i++) {
if (*pptgt == NULL) {
/* 次ポインタがない */
pptgt = NULL;
break;
}
pptgt = &((*pptgt)->next);
}
}
else {
if (insPos > 0) {
/* 線形リストが空なのに1以上が入力された */
pptgt = NULL;
}
}
return pptgt;
}
/* 新しいノードを作成 */
struct person_info_node* createNewNode() {
struct person_info_node* node = NULL;
node = (struct person_info_node*)malloc(sizeof(struct person_info_node));
printf("名前:");
scanf("%s", node->name);
printf("年齢:");
scanf("%d", &(node->age));
node->next = NULL; /* 新規ノードのnextにはNULLを設定しておく */
return node;
}
/* ノードの挿入 */
void insert(struct person_info_node** pptgt, struct person_info_node* node) {
struct person_info_node* tmp;
tmp = *pptgt;
*pptgt = node;
node->next = tmp;
}
/* 全てのノード情報を表示 */
void dispAll(struct person_info_node* root) {
struct person_info_node* node = NULL;
int cnt = 1;
printf("## 全情報表示\n");
node = root;
while (node != NULL) {
printf("No.%d\n", cnt);
printf("name = \"%s\"\n", node->name);
printf("age = %d\n", node->age);
printf("\n");
node = node->next;
cnt++;
}
}
void main() {
struct person_info_node* root = NULL;
struct person_info_node* node = NULL;
struct person_info_node** pptgt = NULL;
int insPos = 0;
printf("####### 挿入処理 #######\n");
printf("挿入位置と登録情報を入力してエンターキーを押してください。(0未満を入力で終了)\n");
printf("\n");
while(1) {
printf("## 新規登録\n");
printf("挿入位置:");
scanf("%d", &insPos);
/* 0未満を入力した場合は挿入処理終了 */
if (insPos < 0) {
break;
}
/* 挿入先ポインタの取得 */
pptgt = getInsNode(&root, insPos);
if( pptgt != NULL ){
/* 新規登録するノードを作成 */
node = createNewNode();
/* 挿入 */
insert(pptgt, node);
}
else{
printf("挿入可能範囲外です。\n");
}
printf("\n");
/* 追加の度に全データ表示 */
dispAll(root);
}
/* 追加の度に全データ表示 */
printf("\n####### 最終結果 #######\n\n");
dispAll(root);
}
まとめと次回予告
今回、線形リストの基礎編②として『ノードの挿入』を学んでもらいました。
重要であり、当たり前の技術なので理解度に自信がない方は本記事を読み返す・ソースコードをいじってみる、などをしてしっかり理解度を深めておくことをオススメします。
次回は線形リスト基礎編③として、『ノードの削除』を予定しています。『ノードの削除』まで習得できれば、「線形リストは習得済み」と胸を張って言えるでしょう！
ご期待ください。