データ構造（配列・リスト・スタック・キュー・木構造）｜出し入れの順と根・節・葉【ITパスポート】

ITパスポート 現行の範囲 テクノロジ系g36　データ構造最終更新 2026-10-20

データ構造は、たくさんのデータをどんな形に並べ、どの順で出し入れするかの決め方で、処理の手順（アルゴリズム）はこの形を前提に組み立てます。

データの型と、配列・レコード・ファイル

プログラムは、値を変数に入れて扱います。変数は、名前を付けた値の入れ物です。 入れてよい値の種類を型（タイプ）といい、整数だけを入れる整数型、小数も入れられる実数型、文字を入れる文字型、真か偽かを入れる論理型などがあります。 表の1つの項目（フィールド）にも、同じように型を決めます。点数のフィールドは整数、氏名のフィールドは文字、のようにです。 型を決めておくと、点数の欄に文字が入る、といった誤りを防げます。

値が1つなら変数1つで足りますが、40人分の点数を40個の変数で持つのは不便です。そこで使うのが次の3つの形です。

配列とレコードの違いは、並べる値の型がそろっているかどうかです。 同じ型の値を番号で並べるのが配列、型の違う項目を1件分まとめるのがレコードです。 表にたとえると、レコードが横の1行、ファイルが表全体にあたります（関係データベースの表・レコード・フィールドは 17-1 データベース方式）。 配列は番号を2つ使って、行と列の表のように並べることもできます。これを2次元配列といいます。

配列の強みは、番号が分かればその場所をすぐ取り出せることです。 一方で、値が詰めて並んでいるので、途中に1つ入れるには、そこから後ろの値をすべて1つずつ後ろへずらす必要があります。 1,000個並んだ配列の先頭に1つ入れると、1,000個を動かすことになります。この弱点を補うのが次のリストです。

リスト ── 次を指す情報でつなぐ

リストは、データの1つ1つに次のデータがどこにあるかという情報を持たせ、それをたどって順につなぐ形です。 次を指すこの情報をポインタといいます。最後のデータには「次は無い」という印を入れておきます。

A→B→D とつながったリストの B と D のあいだに C を入れるときは、C をどこか空いた場所に置き、 B のポインタを C に向け、C のポインタを D に向けるだけです。A や D は1つも動きません。 削除も同じで、B を外したければ、A のポインタを B の次の C に向け直せば、たどる道から B が消えます。

その代わり、リストは「先頭から5番目」をすぐには取り出せません。ポインタを先頭から順にたどるしかないからです。 途中への挿入や削除が多ければリスト、番号ですぐ取り出したければ配列、と向きが分かれます。 なお、次だけでなく前のデータを指すポインタも持たせると、どちらの向きにもたどれます。これを双方向リストといいます。

スタックとキュー ── 取り出す順番の決まり

データを1つずつ入れて、1つずつ取り出す入れ物を考えます。取り出す順番の決め方で、2つの形に分かれます。

スタックは、皿を上へ積み重ねるのと同じで、取れるのはいちばん上の皿だけです。 Web ブラウザーは、開いたページを順にスタックへ積み、「戻る」を押すたびにいちばん上を取り出すので、直前に見たページからさかのぼれます。 キューは店の行列と同じで、先に並んだ人から呼ばれます。

出し入れが続くときは、頭の中だけで追わず、1回の操作ごとに中身を書き出します。 空の入れ物に A、B、C を順に入れ、1つ取り出し、D を入れ、また1つ取り出す、という同じ操作を、両方で追ってみます。

スタック（中身は下から上の順に書く）
A を入れる → A
B を入れる → A、B
C を入れる → A、B、C
取り出す → C が出る。残り A、B
D を入れる → A、B、D
取り出す → D が出る。残り A、B

キュー（中身は先頭から順に書く）
A を入れる → A
B を入れる → A、B
C を入れる → A、B、C
取り出す → A が出る。残り B、C
D を入れる → B、C、D
取り出す → B が出る。残り C、D

同じ操作でも、スタックは C、D の順、キューは A、B の順に出てきます。

スタックはいちばん新しいもの、キューはいちばん古いものが、次に出てきます。 取り出す前に「いま残っている中で、いちばん新しいのはどれか（スタック）」「いちばん古いのはどれか（キュー）」と考えれば、迷いません。

木構造と2分木

木構造は、1つのデータから枝分かれして、下へ広がっていく階層の形です。木を逆さにした形で、上から下へ描きます。 会社の組織図（社長の下に部、部の下に課）や、パソコンのフォルダの階層がこの形です。

たとえば、社長の下に営業部があり、営業部の下に第1課と第2課がある組織図なら、根は社長です。 営業部は下に第1課と第2課が続くので節、第1課と第2課は下に何もつながっていないので葉です。 節か葉かは、名前や種類ではなく、その下に枝が続いているかどうかで決まります。

パソコンのフォルダ（ディレクトリ）とファイルの階層も、同じ決め方で読めます。手がかりになる事実は2つです。 ファイルの中には、別のファイルやフォルダを入れられません。フォルダは、中に何かを入れることも、空のまま置いておくこともできます。 この2つに「下に枝が続くかどうか」を当てはめれば、節になりうるもの、葉になりうるものが決まります （ファイルとディレクトリの仕組みは 14-3 コンピュータの構成要素）。

どの節も子を2つまでしか持たない木を2分木といいます。子は「左の子」「右の子」と区別します。 よく使われるのが、どの節でも左の子から下には自分より小さい値、右の子から下には自分より大きい値だけを置くという決まりを付けた2分木で、 値を探すときに根から比べて左か右へ進めば、見なくてよい枝を丸ごと飛ばせます。

上の2分木で 40 を探す
根の 50 と比べる → 40 は小さい → 左の子へ
30 と比べる → 40 は大きい → 右の子へ
40 と比べる → 一致。見つかった（比べたのは3回）

50 の右側にある 70 と 80 は、一度も見ていません。

まとめ

この節で解ける公開問題

令和4〜8年度の公開問題のうち、この節の知識が決め手になる問題は次の1問です。

同じ分野の過去問を続けて解く（アルゴリズムとプログラミング 17問） →

教科書の一覧（現行の試験の順）教科書の一覧（新しい試験の順）過去問

Udemy の ITパスポート講座を、受講者数・★評価・口コミで比べたページです（広告を含みます）。

出典：IPA「ITパスポート試験 シラバス Ver6.5」。 練習問題は当サイトが説明のために作ったものです。