はじめての C

「リンクリスト 7」

初めて リンクリストを 学んだときは、あるリストの 一部を 他に 繋げる - splice - という 発想自体が むずかしいものでした。

それは 想像も つかないような、長くて 複雑な アルゴリズムに 違いない、と 考えていました。

もちろん、繋ぐという ことが、単独の 項目を 挿入するのと、ほぼ 正確に、同じように 実現したときには、少し まごついて しまいましたが。

線形リストでの つなぎ方は ギコチなくって、実際 敬遠されがちです。

多くの アプリケーションで 使われてる、双方向リストの つなぎ方の ほうは、あっけないほど やさしいものです。

ごく小さな list splice 関数は こんな かんじです ▽

List splice(List list, Element pos, Element first, Element last, Direction dir)
{
assert(list != NULL);
assert(pos != NULL);
assert(first != NULL);
assert(last != NULL);

if (dir == BEFORE) {
first->prev = pos->prev;
last->next = pos;
}
else {
first->prev = pos;
last->next = pos->next;
}
if (first->prev != NULL)
first->prev->next = first;
if (last->next != NULL)
last->next->prev = last;

return list;
}

ここでは 条件文は、リストに 追加する際、その前 または 後の どちらに 挿入するかを 判断し、また null ポインタが ある 可能性についても 考えてあります。

例えば、リストの 前方へ 繋いでいくとすると、first->prev が null ですので、first->prev->next として セットすると、null ポインタを 参照することに なって、たぶん セグメンテーション違反が おきてしまいます。

チェック無しで、項目が 前に 挿入されると 仮定すると、こんな かんじです ▽

List splice(List list, Element pos, Element first, Element last)
{
first->prev = pos->prev;
last->next = pos;
first->prev->next = first;
last->next->prev = last;

return list
}

なぜ 私が まごついたのかを、わかって くれましたか ?

( ごへんじ-> ) はっきりいって よく わかってません ...