配列の限界

並んでいることの利点と代償

前章までで、学生の一覧は struct Student * の動的配列で持てるようになりました。配列は要素が隙間なく並んでいるので、list[3] は先頭から要素3個分だけ番地を進めれば届きます。何番目でも一発で届くのが配列の強みです。

代償は、その「隙間なく並んでいる」という約束を、要素を出し入れするたびに自分で守り直さなければならないことです。

途中に1人入れると、後ろが全部動く

点数の高い順に並んだ一覧があるとします。

ここに85点の佐藤さんを入れるなら、入る場所は鈴木さんの手前です。ところが配列に空き地はないので、鈴木・伊藤・山本の3人を1つずつ後ろへ動かして、空いた枠に佐藤さんを書き込むことになります。

このループは後ろから前へ回します。前から回すと、まだ動かしていない要素を上書きしてしまい、同じ人が並ぶからです。

動かす回数は「入れた場所より後ろにいる人数」です。末尾に足すなら0回で済みますが、先頭に入れると全員が動きます。1000人の名簿の先頭に1人足すだけで999回のコピーが起きるということです。削除も裏返しで、抜けた穴を埋めるために後ろの全員を1つずつ前へ詰め直します。

覚えておいたポインタが別人を指す

もう1つ困ることがあります。要素が動くということは、&list[3] のようにして控えておいたポインタが、挿入や削除のあとで別人を指すようになるということです。realloc で領域ごと引っ越した場合は、そのポインタが有効ですらなくなります。前章で「動的配列を持つなら、要素の番地ではなく添字で覚える」と書いたのはこのためでした。

本当にやりたいのは1か所の割り込みだけ

やりたいことは「佐藤さんを鈴木さんの手前に置く」だけで、ほかの4人の位置関係は変わっていません。それでも詰め直しが必要になるのは、順番を配列の並び順そのものに担わせているからです。

順番を並び順ではなく「次はこの人」という矢印で持てば、割り込みは矢印の付け替え2本で済みます。これが連結リストの考え方で、次回からその形を組み立てていきます。

リストにも代償はある

矢印でつなぐ形にすると、今度は「5番目の人」に一発では届かなくなります。先頭から矢印を5回たどるしかありません。配列が得意なことをリストは苦手にし、配列が苦手なことをリストは得意にする、という関係です。成績管理のように出し入れが多く、番号で引く場面が少ないものはリスト向きです。どちらが優れているかではなく、どちらの代償を払うかを選ぶ話になります。

まずは詰め直しが何回起きるかを自分の手で数えて、重さを数字で見ておきましょう。

1. 入る場所は「自分より点数が高い人が続くあいだ進む」で決める
2. 後ろから前へ向かうループでずらす
3. ずらした回数を数えて「ずらした回数は3回です」の形で表示する
4. そのあと6人を「田中 95点」の形で1人1行ずつ表示する