データ構造

基本の仕組み

A、B、Cの順に入れると、スタックはC、B、Aの順、キューはA、B、Cの順で取り出します。前者は後入れ先出し、後者は先入れ先出しです。

配列は添字で直接要素を参照しやすく、連結リストは次の要素への参照をたどります。木は親子関係を持ち、根から枝を選んで要素を探せます。

連結リストの途中への挿入が容易でも、挿入位置を探すコストが消えるわけではありません。操作の前提と全体の処理量を分けて考えます。

単方向リストは、各要素が次の要素への参照を持つ連結リストです。途中へ要素を挿入するには、新要素を従来の次要素へつなぎ、直前要素の参照を新要素へ変更します。先に参照を上書きして後続への道を失わないよう、更新順を追います。

構造を選ぶ条件

配列は添字による直接参照に向きます。連結リストは参照の付替えで挿入できますが、挿入位置を探す走査は必要です。スタックは後入れ先出し、キューは先入れ先出しで要素を取り出します。

木は親子関係を表す構造です。2分探索木は「左の子孫＜節＜右の子孫」となるよう値を置き、根から大小比較で左右へ進んで探します。ヒープは親が子以上（または以下）となる完全2分木で、最大値（最小値）を根から取り出せます。ハッシュ表はキーから計算した位置へ格納します。