データの並べ方

並べ方は続けて置くだけじゃない。ばらばらの場所に置いて、「次はここ」という矢印を持たせるやり方もある。これが リスト（連結リスト・線形リスト）だよ。

この矢印にあたるものが ポインタ ＝ 次の要素がどこにあるかを書いた値だ。だからリストの1つぶんは、値の置き場と、次を指すポインタの置き場の2つを持つ。最後の要素のポインタは「もう次は無い」という印になっている。矢印を1本しか持たないものを 単方向リスト、前へ戻る矢印も持つものを 双方向リスト と呼ぶよ。

ここで配列との決定的な違いが出る。リストには添字が無いので、3番目が欲しければ先頭から矢印を3回たどるしかない。計算で場所が出る配列と違って、手前を全部通らないと目的地に着けないんだ。100番目なら100回たどる。だから参照はリストのほうが遅い。

この性質は「ランダムアクセスできない」「先頭から順番に要素をたどるので、要素数に比例した時間が必要」といった言い方で出てくる。どれも同じことを言っているよ。

では配列のほうが全部いいのか、というとそうでもない。途中に入れるときに差が逆転するよ。

配列はすきまなく並んでいるので、真ん中に1つ割りこませると後ろの要素を全部1つずつずらすことになる。消すときも同じで、空いた穴を埋めるために後ろを前に詰める。要素が多いほど重くなる。

リストはずらさない。矢印を数本つなぎ替えるだけだ。前の要素の「次」を新しい要素に向け、新しい要素の「次」をもとの続きに向ける。これで終わり。

しかもこの手間は要素が何個あっても変わらない。1000個の途中でも10個の途中でも、書き替える矢印は数本だよ。

整理しよう。読むのが多いなら配列、出し入れが多いならリスト。それだけだよ。

• 配列 … 参照が速い / 挿入と削除が重い / 最大の個数ぶん場所を先に取る
• リスト … 参照が遅い / 挿入と削除が軽い / ポインタのぶん場所が余分に要る

配列のもう1つの弱点が最後の行だ。あらかじめ最大の長さぶんを確保するので、実際に3個しか入っていなくても場所は空けたまま。使われない領域が出てしまうよ。

リスト側にも落とし穴がある。単方向リストで末尾の要素を消すときは、末尾を指すポインタを持っていても足りない。消したあとに「最後」になる1つ前の要素を書き替える必要があり、その1つ前は先頭からたどらないと分からないんだ。

ここからは、出し入れの順番にきまりを付けた並べ方を見ていく。1つ目が スタック だよ。

スタックは最後に入れたものが最初に出てくる。積み上げた本の山を思えばいい。上に置いて、上から取る。この性質を LIFO（Last In First Out）と呼ぶ。

操作の名前は2つだけ。積むのが push、取り出すのが pop だよ。JavaScript の配列の push と pop がそのまま同じ動きをする。

注意したいのは、pop は必ず一番上からということ。途中のものを抜き取ることはできない。

スタックの出番は、行った先から帰ってこないといけないときだよ。

代表が関数の呼び出しだ。関数 A から B を呼び、B から C を呼んだとする。C が終わったら B に、B が終わったら A に帰る。最後に呼んだところへ最初に帰るので、戻り先の番地（戻り番地）と作業中のデータをスタックに積んでおけばちょうど合うんだ。

もう1つが式の計算。(1 + 2) × 3 のように、途中の結果をいったん置いておいて、別の計算を済ませたあとで取り出して使う。置いた順の逆で必要になるから、これもスタックが向いている。

逆に「入れた順に取り出したい」ならスタックでは無理だし、「途中のものを直したい」「途中に割りこませたい」なら配列やリストの仕事だよ。

2つ目が キュー（待ち行列）。こちらは最初に入れたものが最初に出てくる。レジの行列そのままだよ。この性質は FIFO（First In First Out）と呼ぶ。

スタックと違って、入れる口と出す口が別なのがポイントだ。うしろから入れて、前から出る。

操作の名前は、入れるのが enqueue（試験では ENQ や enq と書かれる）、取り出すのが dequeue（DEQ や deq）だよ。

身のまわりでは、印刷の順番待ちや、順番に処理したい仕事の行列がキューになっている。割りこませないという性質がそのまま「公平さ」になるんだ。

試験ではスタックとキューを同時に置いて、行ったり来たりさせる問題がよく出る。文章だけで解けるので、落とさないでほしいところだよ。

コツは1つ。中身を紙に書いて、1操作ごとに書き替える。頭の中だけでやると必ずどこかで取り違える。

書くときは向きをそろえるのが大事だよ。スタックは「右端が上（次に出るところ）」、キューは「左端が先頭（次に出るところ）」と決めて崩さない。

そして取り出した値がどこへ行くのかを読み落とさないこと。enq(pop()) のように入れ子になっていたら、まずスタックから抜き、その値をキューに入れる、という2段の動きだよ。

並べ方には、1列ではなく枝分かれする形もある。それが 木構造 だよ。

言葉を4つ覚えよう。

• 節（ノード）… 1つ1つの点。データが入る
• 根（ルート）… いちばん上の、親を持たない節
• 葉（リーフ）… 子を持たない、行き止まりの節
• 枝（エッジ）… 節と節をつなぐ線

上下の関係は 親 と 子 と呼ぶ。そして根から数えた段数が 深さ（レベル）だよ。根を深さ 0 と数えるのがふつうで、いちばん深い葉までの段数を木の高さと呼ぶ。

木は階層関係を表すのに向いている。フォルダの中にフォルダがある構造も木だよ。

子の数を2つまでに限った木が 2分木 だよ。左の子と右の子しかないので、形が読みやすく扱いやすい。

2分木のうち、上から左から順にすきまなく埋まっているものを 完全2分木 と呼ぶ。途中に穴が空いていないので、配列にそのまま詰められるのが強みだよ。

配列に詰めると、親子の関係が計算だけで出る。1 から数える置き方なら、添字 i の子は 2i と 2i+1、逆に親は i を2で割った商だ。ポインタを1つも持たずに木を表せることになる。

ちなみに、節と親の関係は配列に親の番号を入れるやり方でも表せる。根の場所には「親なし」の印として 0 を入れておく。この形なら、どこからも親として指されていない節が葉だよ。

2分木に値の置き方のきまりを足すと、探しやすい形になる。

2分探索木 は、どの節でも左の子とその子孫は自分より小さく、右の子とその子孫は自分より大きいという木だよ。だから根と比べて「小さい → 左」「大きい → 右」と降りていけば、目当ての値まで一直線に着ける。

大事なのは自分の子だけでなく、その下の全部が条件を満たしていること。すぐ下だけ見て正しく並んでいても、孫の段で破れていたら2分探索木ではないよ。

もう1つの型が ヒープ。こちらは親と子の大小だけを決めた木で、「親は子より大きい（または小さい）」を全部の親子で守る。左右の兄弟どうしの順番は決めないのがポイントだよ。だから根には必ず最大（または最小）が来る。「いちばん大きいものを次々取り出したい」ときに向いている。

最後は場所を計算で決めてしまう並べ方だよ。

ハッシュ表 は、値のもとになるキーを ハッシュ関数 に通し、出てきた数をそのまま置き場所（添字）として使う。よく使われるのは「キーをある数で割った余り」だ。

うれしいのは、たどらなくても、探さなくても場所が分かること。キーを関数に通すだけなので、表がどれだけ大きくても手間は変わらない。ここが「表の大きさに比例する」やり方との違いだよ。

ただし問題が1つある。違うキーから同じ場所が出てしまうことがあるんだ。これを 衝突（コリジョン）、同じ場所になったキーどうしを シノニム と呼ぶ。

衝突は「起きないようにする」ものではなく、必ず起きるものとして備えるものだよ。ハッシュ関数の出せる値の数より、来るかもしれないキーの種類のほうがずっと多いのだから、避けようがない。空いている次の場所へずらす、その場所からリストをぶら下げる、といった逃がし方を用意しておく。