データ構造

ねらい

プログラムがデータをどのような形で持つかを学びます。このレッスンを終えると、配列とリストの得意・不得意を比較でき、スタックとキューの出し入れの規則を使い分け、木構造の用語と2分探索木の仕組みを説明できるようになります。

データ構造とは

プログラムが扱うデータについて、目的に合わせて整理して格納する形をデータ構造といいます。同じデータでも、持ち方によって「探すのが速い」「追加が楽」といった得意分野が変わります。アルゴリズムとデータ構造は表裏一体で、適切な構造を選ぶことがプログラムの性能を左右します。

配列とリスト：並べ方の2つの流儀

配列：番号で一発アクセス

配列は、同じ型のデータを連続した領域に並べ、番号（添字）で参照するデータ構造です。番号さえ分かれば何番めの要素でも一発で読み書きできるのが強みです。行と列のように複数の番号で参照するものを多次元配列といいます。また、大きさをあらかじめ固定する静的配列と、実行中に大きさを変えられる動的配列があります。

配列の弱点は、途中への挿入と削除です。要素を1つ差し込むには、それより後ろの要素をすべて1つずつずらす必要があります。

リスト：つなぎ替えで柔軟に

リストは、各要素が「次の要素の場所」を指す情報を持ち、数珠つなぎでデータを保持するデータ構造です。直線状につながるものを線形リストといい、つなぎ方で3種類に分かれます。

1. 単方向リストは、次の要素への参照だけを持ちます。
2. 双方向リストは、次と前の両方への参照を持ち、どちら向きにもたどれます。
3. 環状リストは、末尾が先頭を指し、輪になっています。

リストの強みは挿入と削除です。参照のつなぎ替えだけで済むため、後ろの要素をずらす必要がありません。その代わり、目的の要素へは先頭からたどる必要があり、番号での一発アクセスはできません。配列とリストは、この点でちょうど得意と不得意が逆になっています。

スタックとキュー：出し入れの規則で区別する

スタック：後入れ先出し（LIFO）

スタックは、最後に入れたデータを最初に取り出すデータ構造です。この規則をLIFOといいます。冒頭のトレイの山がスタックです。データを積むことをプッシュ、取り出すことをポップと呼びます。プログラムでは、関数呼び出しの戻り先の管理やブラウザの「戻る」機能など、「直前のものへ戻る」場面で活躍します。

キュー：先入れ先出し（FIFO）

キューは、最初に入れたデータを最初に取り出すデータ構造です。この規則をFIFOといいます。冒頭の注文の列がキューです。印刷の順番待ちやメッセージの受け渡しなど、「来た順に公平に処理する」場面で使われます。

動かして確かめる

「追加」は同じ1つの操作です。取り出す端だけがスタックとキューで違うことを、実際に操作して確かめてみましょう。

木構造：枝分かれで階層を表す

フォルダの中にフォルダがあるように、階層のあるデータを表すのが木構造です。木構造は、いちばん上の節である根、下に子を持たない節である葉、節と節を結ぶ枝からできています。

2分木と2分探索木

各節の子を2つまでに限った木を2分木といい、葉以外のすべての節に子が2つそろい、どの葉も同じ深さにある木を完全2分木といいます。

2分探索木は、「左の子孫はどれも自分より小さく、右の子孫はどれも自分より大きい」という約束で値を配置した2分木です。値を探すときは、根と比べて小さければ左へ、大きければ右へ進むだけでよく、比較のたびに探す範囲が半分に絞られていきます。ただし、偏った形に育つと効率が落ちるため、形の釣り合いを自動的に保つバランス木（AVL木など）や、データベースの索引に使われる多分木のB木といった発展形があります。

木のたどり方とヒープ

木のすべての節を漏れなく訪れる方法には、枝を行けるところまで深く進む深さ優先探索と、同じ深さの節を先に見終えてから下へ進む幅優先探索があります。深さ優先探索では、親を訪れるタイミングによって先行順、中間順、後行順という3つの巡回法を区別します。

また、「親は子より小さい（または大きい）」という約束だけを保つ2分木をヒープといい、最小値（または最大値）を素早く取り出せるため、優先度付きの処理や整列に使われます。

例題

次の問いに答えてください。

問1 空のスタックにA、B、Cの順にデータをプッシュし、続けてポップを2回行いました。取り出されたデータを順に答えてください。

問2 データの列の途中への挿入や削除について、後ろの要素をずらさずに行いたいとき、配列とリストのどちらが適していますか。

解答と解説

問1の答えは、CそしてBの順です。スタックは後入れ先出し（LIFO）なので、最後に積んだCが最初に取り出され、次にBが取り出されます。この時点でスタックにはAだけが残っています。

問2の答えはリストです。リストは参照のつなぎ替えだけで挿入と削除ができます。配列は途中に挿入すると、それより後ろの要素をすべてずらす必要があります。

応用

本試験を意識した問題を解いてみましょう。

問 最初に格納したデータを最初に取り出す、先入れ先出しのデータ構造はどれでしょうか。次の中から選んでください。

1. スタック
2. キュー
3. 2分探索木
4. 双方向リスト

解答と解説

答えは2のキューです。キューは先入れ先出し（FIFO）で、格納した順にデータを取り出します。1のスタックは後入れ先出し（LIFO）で、取り出しの順序が逆です。3の2分探索木は大小関係で値を配置して探索を速くする構造であり、出し入れの順序を定める構造ではありません。4の双方向リストは前後どちらにもたどれる線形リストであり、これも取り出しの順序を定める規則は持ちません。