任意位置の挿入と削除
外したいノードの、前を知る必要がある
いよいよ本題です。連結リストを選んだ理由は、途中の出し入れを詰め直しなしで済ませたいからでした。
削除でやることは1つだけです。抜きたいノードの前にいるノードの矢印を、抜きたいノードの次へ付け替えます。
c
prev->next = target->next;これで並びから外れました。ほかのノードは1つも動いていません。配列なら後ろ全員を前へ詰めていたところが、代入1つになります。
問題は prev の入手です。ノードは自分の次しか知らないので、前を指す矢印はどこにもありません。前を知る唯一の方法は、先頭から歩きながら「1つ前」を自分で覚えておくことです。
c
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 自身を進めます。
c
if (prev == NULL) {
head = p->next;
} else {
prev->next = p->next;
}
free(p);この分岐を書き忘れると、先頭を消したときだけ NULL の中身に触れて落ちます。リストのコードで最初に踏むのはたいていここです。
外してから解放する
順番も大事です。free(p) を先にやってから p->next を読むと、返してしまった領域を読むことになります。運が良ければ正しい値が残っていて動いてしまうので、なおさら質が悪い間違いです。並びから外し、必要な値を読み終えてから解放する、と決めておきます。
割り込ませるほうも矢印2本
途中への挿入は、前になるノードが分かっていればさらに簡単です。
c
node->next = prev->next;
prev->next = node;やはりこの順です。逆にすると prev の元の次を見失い、そこから後ろが全部つながらなくなります。「新しいノードの行き先を先に決めてから、自分を指してもらう」と覚えると、先頭追加のときと同じ話だと分かります。
同じ名前が2人いたら
今回の削除は、先頭から歩いて最初に一致したノードだけを外します。同じ名前が2人いた場合、残った1人は次に呼んだときに消えます。全部消したいのか1人だけなのかは仕様の話なので、どちらにするかを決めて、決めたほうに合わせて動くようにしておきます。曖昧なまま書くと、使う側から見て「消えたり消えなかったりする関数」になります。
では、名前で削除する関数と、指定ノードの直後へ割り込ませる関数を書きましょう。
要件
- 削除は先頭から歩きながら1つ前のノードを覚えておく
- 先頭を削除する場合と途中を削除する場合を分ける
- 並びから外したあとに free する
- insert_after は新しいノードの next を先に決めてから prev の next を書き替える
- prev が NULL のときは何もしない
ヒント
