はじめての C

lang

「リンクリスト 6」

リストを 適当な ところで 逆順に できれば、ときとして、役にたつ 使い方に なります。

線形リストを 逆順に することは とても 簡単で、リストを 渡っていって、元のリストの 前方から 削除していき、新しいリストの 前方へ 挿入することで、リストを 構築していきます。

結果は、次のような アルゴリズムに なります。

0:
Old: 1 -> 2 -> 3 -> 4 -> -
New: -

1:
Old: 2 -> 3 -> 4 -> -
New: 1 -> -

2:
Old: 3 -> 4 -> -
New: 2 -> 1 -> -

3:
Old: 4 -> -
New: 3 -> 2 -> 1 -> -

4:
Old: -
New: 4 -> 3 -> 2 -> 1 -> -

この アルゴリズムの 疑似コードを、想定して 書くのは やさしいですね。

sub reverse(list)
hold
done
todo

done = null
todo = list
while todo != null
hold = todo->next
todo->next = done
done = todo
todo = hold
loop

return done
end sub

また、双方向リストでは、prev ポインタも 考えに いれておかないと いけません。 そこで 注意深く 考えてみて、1行分だけ このアルゴリズムに つけ加えておきます。

C および C++ での、双方向リストにおける 逆順のための ソースは、次のとおりです。

List reverse(List list)
{
Element hold;
Element done;
Element todo;

done = NULL;
todo = list;
while (todo != NULL) {
hold = todo->next;
todo->next = done;
done = todo;
todo = hold;
done->prev = todo; /* Fix the prev link */
}
return done;
}