任意位置の挿入と削除｜コードで実践

外したいノードの、前を知る必要がある

いよいよ本題です。連結リストを選んだ理由は、途中の出し入れを詰め直しなしで済ませたいからでした。

削除でやることは1つだけです。抜きたいノードの前にいるノードの矢印を、抜きたいノードの次へ付け替えます。

prev->next = target->next;

これで並びから外れました。ほかのノードは1つも動いていません。配列なら後ろ全員を前へ詰めていたところが、代入1つになります。

問題は prev の入手です。ノードは自分の次しか知らないので、前を指す矢印はどこにもありません。前を知る唯一の方法は、先頭から歩きながら「1つ前」を自分で覚えておくことです。

struct Node *prev = NULL;
struct Node *p = head;
while (p != NULL && strcmp(p->name, name) != 0) {
    prev = p;
    p = p->next;
}

ループを抜けたとき、p が見つかったノード、prev がその1つ前です。見つからなければ p は NULL になっています。

先頭を消すときだけ形が違う

prev が NULL のままループを抜けたなら、消したいのは先頭です。前がいないので付け替える矢印もなく、代わりに head 自身を進めます。

if (prev == NULL) {
    head = p->next;
} else {
    prev->next = p->next;
}
free(p);

この分岐を書き忘れると、先頭を消したときだけ NULL の中身に触れて落ちます。リストのコードで最初に踏むのはたいていここです。

外してから解放する

順番も大事です。free(p) を先にやってから p->next を読むと、返してしまった領域を読むことになります。運が良ければ正しい値が残っていて動いてしまうので、なおさら質が悪い間違いです。並びから外し、必要な値を読み終えてから解放する、と決めておきます。

割り込ませるほうも矢印2本

途中への挿入は、前になるノードが分かっていればさらに簡単です。

node->next = prev->next;
prev->next = node;

やはりこの順です。逆にすると prev の元の次を見失い、そこから後ろが全部つながらなくなります。「新しいノードの行き先を先に決めてから、自分を指してもらう」と覚えると、先頭追加のときと同じ話だと分かります。

同じ名前が2人いたら

今回の削除は、先頭から歩いて最初に一致したノードだけを外します。同じ名前が2人いた場合、残った1人は次に呼んだときに消えます。全部消したいのか1人だけなのかは仕様の話なので、どちらにするかを決めて、決めたほうに合わせて動くようにしておきます。曖昧なまま書くと、使う側から見て「消えたり消えなかったりする関数」になります。

では、名前で削除する関数と、指定ノードの直後へ割り込ませる関数を書きましょう。

任意位置の挿入と削除