データ構造の使い分け

構造を選ぶとは、何を速くするか選ぶこと

この章で、配列、スタック、キュー、連結リスト、木、ハッシュと一通りの入れ物を見てきました。最後にそれらを並べて、要件からどれを選ぶかを考えます。

万能の構造はありません。どの構造も、ある操作を速くするかわりに別の操作を犠牲にしています。ですから選ぶときに問うべきことは1つで、その処理でいちばん回数の多い操作は何か、です。1日1回しか起きない処理が少し遅くても困りませんが、毎秒何千回も起きる操作が遅ければ致命傷になります。

操作ごとの得手不得手

配列と連結リストは、ちょうど裏返しの関係にあります。配列は場所で並びが決まるので添字で一発ですが、途中に入れると後ろを全部ずらします。連結リストはつながりで並びが決まるので付け替えだけで挿入できますが、k 番目に行くには先頭からたどります。

スタックとキューは、取り出す順番そのものが要件になっている場合に使います。どちらも中身を見て回る用途には向きません。

二分探索木とハッシュは、どちらも探索を速くする構造ですが性格が違います。ハッシュは鍵が完全に一致するものを引くのが得意な一方で、並び順は保ちません。100 以上 200 以下をすべて取り出す、といった範囲の要求には答えられません。二分探索木は大小関係で並んでいるので、範囲の取り出しや最小値の取得が得意です。

要件文の読み方

問題文には手掛かりになる言い回しが必ず入っています。次のように読み替えると迷いません。

• 「最後に行った操作を取り消す」「直前の状態に戻る」ならスタックです
• 「受け付けた順に処理する」「先に登録した人から呼ぶ」ならキューです
• 「会員番号から会員情報を取り出す」ならハッシュです
• 「途中への追加と削除が頻繁に起きる」なら連結リストです
• 「番号を指定して読むだけで、件数は変わらない」なら配列です
• 「上位の分類から下位へたどる」「階層で表す」なら木です

複数の条件が並ぶときは、頻度が高いほうを優先します。たとえば、たまに追加があるが読み出しが圧倒的に多いなら配列で構いません。

試験での問われ方

科目Aでは、構造の説明文とその名前を対応させる問題が定番です。科目Bでは、擬似言語のどこかにこの章の構造が現れ、その動きを追った結果を答えさせます。どちらも、それぞれの構造が何を速くするために生まれたのかを言葉にできれば対応できます。名前と特徴の丸暗記ではなく、犠牲にしているものまで一緒に思い出せるようにしておきましょう。

次のレッスンの演習で、この章の内容を本試験と同じ形の小問で確かめます。