データ構造の基本

リストは、各要素が次の要素の位置を示すポインタを持ち、それをつないでデータを一列に並べるデータ構造である。

図の例では、先頭のりんごからポインタをたどると、みかん、ぶどうの順に読める。並び順はポインタが決めるので、記憶されている位置の順と一致していなくてもよい。途中に要素を加えたり外したりするときは前後のポインタを書き換えるだけで済み、ほかの要素を移動させる必要がない。

たとえ宝探しのメモのようなもの。1 枚目のメモに次のメモの隠し場所が書いてあり、順にたどれば最後まで行き着く。

覚え方英語の list は「一覧・名簿」。名簿の行どうしを「次はこちら」の矢印で結んだ形と覚える。

スタックは、データを積み重ねるように格納し、いちばん新しく入れたものから取り出す後入れ先出し (LIFO: Last In First Out) のデータ構造である。

格納する操作をプッシュ、取り出す操作をポップと呼び、どちらも常にいちばん上の 1 か所で行う。Web ブラウザの「戻る」で直前に見たページから順にさかのぼる動きは、この性質の身近な例である。

たとえ机に積んだ本の山のようなもの。新しい本は山の上に置き、手に取るのも上からなので、最後に置いた本が最初に戻ってくる。

覚え方英語の stack は「積み重ね」。干し草の山 (haystack) の stack と同じ語。

この用語の過去問 3 題 スタック →

キューは、格納した順にデータを取り出す先入れ先出し (FIFO: First In First Out) のデータ構造である。

データは列の末尾に加え、先頭から取り出す。格納する操作をエンキュー、取り出す操作をデキューと呼ぶ。プリンタが受け付けた印刷要求を到着順に処理する仕組みなどに使われる。

たとえ窓口の順番待ちの行列のようなもの。後から来た人は列の最後に並び、呼ばれるのは先に並んだ人からになる。

覚え方英語の queue は「順番待ちの列」。イギリス英語では列に並ぶことを queue up と言う。

この用語の過去問 1 題 キュー →

木構造は、データを表す節 (ノード) が親子の関係で枝分かれしながら、階層状につながるデータ構造である。

最上位にある親を持たない節を根 (ルート)、子を持たない末端の節を葉 (リーフ) と呼び、根以外の節はどれも親を 1 つだけ持つ。組織図やフォルダの階層のように、上下関係や包含関係を表すのに向いている。

たとえパソコンのフォルダのようなもの。1 つのフォルダの中に複数のフォルダが入り、その中にさらにフォルダやファイルが入っていく。

覚え方木を逆さにした形で描くので、根が上、葉が下に来る。

2分木は、各節の子が左の子と右の子の 2 つ以下に限られた木構造である。

左右の子は区別して扱い、子が 1 つだけの節や、子を持たない葉があってもよい。例えば、値の大小で左右に振り分けて格納しておくと、目的の値を探すときにたどる節の数を減らせる。

たとえはい / いいえで進む診断チャートのようなもの。1 つの質問から先は「はい」と「いいえ」の 2 方向までに分かれ、片方にしか続きがない質問や、そこで結果が出て終わる質問もある。

覚え方読みは「にぶんぎ」。二股に分かれる枝の形を思い浮かべる。