対象試験と出題頻度
データ構造（配列・リスト）は、ITパスポート・基本情報技術者・応用情報技術者のすべてで出題されるテーマです。
科目A（午前）では「配列とリストの特徴比較」が定番化しており、科目Bではリストを配列で実装する操作問題が繰り返し出題されています。
スタックやキュー、木構造といった上位のデータ構造を理解するための土台になるため、最優先で押さえるべき分野です。
詳細をクリックして確認
ITパスポート
基本情報技術者
応用情報技術者
★★★★☆
ランクA（重要）必ず覚えておくべき
用語の定義
情報処理試験を勉強していると、「配列とリストって結局何が違うの？」と混乱しがちです。
データ構造（Data Structure）とは、一言で言うと
「プログラムがデータをメモリ上にどのように格納・管理するかを定めた形式」
のことです。
その中でも最も基本的な2つが配列（Array）とリスト（Linked List）です。
イメージとしては、配列は「ロッカー」、リストは「しりとり」です。
ロッカーは番号順に並んでいて「3番を開けて」と指定すれば一発で中身を取り出せます。
ただし途中に新しいロッカーを割り込ませるのは大変です。一方、しりとりは「前の言葉→次の言葉」とつながりだけで成立しているので、途中に新しい言葉を差し込むのは簡単ですが、「5番目の言葉は？」と聞かれたら最初から順番に数える必要があります。
📊 配列とリストの基本情報
| 項目 | 配列（Array） | リスト（Linked List） |
|---|---|---|
| メモリ配置 | 連続した領域に並べて格納 | バラバラの領域にポインタでつなぐ |
| 要素へのアクセス | 添字（インデックス）で直接参照 → 高速 | 先頭から順にたどる → 要素数に比例 |
| 挿入・削除 | 後続要素をずらす必要あり → 遅い | ポインタの付け替えだけ → 高速 |
| メモリ効率 | 最大長分を事前に確保（未使用領域が生じうる） | 必要な分だけ確保（ポインタ分の追加領域が必要） |
詳細解説
配列とリストは、どちらも「複数のデータをまとめて扱う」ための構造ですが、内部のメモリ管理が根本的に異なります。この違いが、得意な操作・苦手な操作の差を生みます。
配列の仕組み
配列は、メモリ上の連続した領域に同じ型のデータを並べて格納します。各要素には0番、1番、2番…と添字（インデックス）が振られ、「先頭アドレス＋添字×1要素のサイズ」でアクセス先のアドレスを即座に計算できます。
この計算量は要素数に関係なく一定（O(1)）です。
▶ 配列のメモリ配置を図で確認（クリックで展開）
| 添字 | [0] | [1] | [2] | [3] | [4] |
| 値 | A | B | C | D | E |
| アドレス | 100番地 | 104番地 | 108番地 | 112番地 | 116番地 |
メモリ上に隙間なく並んでいるため、100 + 3 × 4 = 112番地 のように添字3の要素を一発で計算できます。要素1つが4バイトの場合の例です。
一方で、配列は宣言時に最大の要素数分のメモリをまとめて確保します。
実際に使う要素が少なければ残りの領域は無駄になります。また、途中に要素を挿入する場合はそれより後ろの要素をすべて1つずつ後方へ移動させる必要があり、要素数が多いほど処理コストが増大します。
リスト（連結リスト）の仕組み
リストは、各要素が「データ本体」と「次の要素の場所（ポインタ）」をセットで持ち、数珠つなぎに連結された構造です。メモリ上では要素がバラバラに散在していても、ポインタをたどることで論理的な順序を維持します。
▶ 単方向リストの構造を図で確認（クリックで展開）
各ノードが「データ」と「次のノードへのポインタ」を持ちます。末尾のポインタはNULLで終端を示します。
挿入・削除はポインタの付け替えだけで完了するため、要素数に関係なく一定時間（O(1)）で実行できます。
ただし「n番目の要素を参照したい」場合は先頭から1つずつたどる必要があり、要素数に比例した時間（O(n)）がかかります。
リストの種類
連結リストには用途に応じた派生型があります。
| 種類 | 特徴 |
|---|---|
| 単方向リスト | 各ノードが「次の要素」へのポインタのみを持つ。先頭から末尾への一方向にしかたどれない。 |
| 双方向リスト | 各ノードが「次」と「前」の両方へのポインタを持つ。前後どちらにもたどれるため、末尾からの探索や削除が効率的。 |
| 循環（環状）リスト | 末尾のポインタが先頭を指し、リングのようにつながる。末端がないため巡回処理に向く。 |
▶ 双方向リストの構造を図で確認（クリックで展開）
各ノードがprev（前）とnext（次）の2つのポインタを持つため、前後どちらにも移動できます。
R5秋期 応用情報 午前 問5では、この双方向リストへの要素挿入が出題されました。
配列でリストを実装するパターン
実際の試験問題では、リストをポインタではなく「2つの配列（値用とポインタ用）」で表現するケースが頻出します。box[i]にデータの値、next[i]に次の要素の添字を格納することで、配列だけで連結リストの動きを再現します。
▶ 配列によるリスト実装の図解（クリックで展開）
box[i]が値、next[i]が次の要素番号を格納します。next[0]が先頭要素を指し、next[i]=0が末尾を示します。
| i | box[i] | next[i] |
|---|---|---|
| 0 | − | 1 |
| 1 | A | 4 |
| 2 | D | 0 |
| 3 | C | 2 |
| 4 | B | 3 |
この場合の論理的な順序は：next[0]=1→box[1]=A → next[1]=4→box[4]=B → next[4]=3→box[3]=C → next[3]=2→box[2]=D → next[2]=0（末尾）。つまり A → B → C → D の順にたどれます。
ここだけは確実に押さえてください。配列は「添字で一発アクセス、挿入・削除は苦手」、連結リストは「挿入・削除が得意、ランダムアクセスは苦手」です。この対比がすべての出題の出発点になります。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 データ構造（配列・リスト）の核心を3行で
・配列はメモリ連続配置で添字アクセスがO(1)、挿入・削除は後続要素の移動が必要でO(n)
・連結リストはポインタで連結し挿入・削除がO(1)、n番目の参照は先頭からたどるためO(n)
・配列は「未使用領域が生じうる」、リストは「ポインタ分の追加メモリが必要」とメモリ特性も対照的
試験ではこう出る！
配列とリストに関する問題は、科目A（午前）の知識問題と科目B（午後）の操作問題の2種類に大別されます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE H25秋 午前 問6 |
リストを配列で実現した場合の特徴を選ぶ問題。 | ・「最大長分の領域を確保し未使用領域が生じうる」が正解 ・ポインタ実装の特徴がひっかけ選択肢 |
| FE H30春 午前 問6 |
2つの1次元配列でリストを実現し、要素を挿入したときのnext[i]の値を求める問題。 | ・box[i]とnext[i]の対でリストを構成するパターン ・挿入後のポインタ書き換えを正しくたどれるか |
| AP R4春 午前 問5 |
FE H25秋 問6と同一問題（流用）。リストを配列で実現した場合の特徴を選ぶ。 | ・FE→AP間で同一問題が出回る典型例 ・配列実装とポインタ実装の特徴を正確に区別できるか |
| AP R5秋 午前 問5 |
双方向リストを3つの配列で実現し、要素挿入後のnext[i]とprev[i]の値を求める問題。 | ・elem[i]、next[i]、prev[i]の3配列による双方向リスト ・挿入ノードのnextとprevに入る値を正確に特定できるか |
| FE 科目B サンプル問3 |
単方向リストにデータを追加する擬似言語プログラムの穴埋め問題。 | ・クラスで表現された連結リストの操作 ・ポインタの付け替え順序を正しく追えるか |
📝 IPA試験での出題パターン
パターン1：「配列実装 vs ポインタ実装の特徴を選べ」
4つの選択肢が並び、配列で実現したリストの特徴を選ぶ形式。ひっかけとしてポインタ実装の特徴（「先頭から順にたどる」「次の要素を指し示す領域が別途必要」）が混ざる。キーワードは「最大長に対応した領域を確保」「未使用領域」。
パターン2：「配列によるリスト操作でnext[i]の値を答えよ」
2つまたは3つの配列でリストを表現し、要素の挿入・削除後にポインタ（next/prev）がどう変化するかをトレースさせる。手を動かして1ステップずつたどれば確実に正解できる。
パターン3（科目B）：「擬似言語でリスト操作のプログラムを読む」
クラスで定義されたノード（dataとnextの属性を持つ）を操作する処理をトレースし、空欄を埋める形式。ポインタの付け替え順序を正しく追うことがカギになる。
試験ではここまででOKです。計算量O(1)やO(n)の表記を暗記するよりも、「配列は添字で一発、リストは先頭からたどる」「配列は挿入で後ろがずれる、リストはポインタ付け替えだけ」と言葉で説明できる状態を目指してください。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. リストを配列で実現した場合の特徴として、最も適切なものはどれでしょうか？
- A. 各要素は次の要素を指し示すポインタ領域を別途必要とし、要素を追加するたびにメモリを動的に確保する。
- B. 中間要素を参照するには先頭から順に要素をたどっていくため、要素数に比例した時間が必要となる。
- C. 実際の要素数にかかわらず最大長に対応した領域を確保するため、実際には使用されない領域が発生する可能性がある。
正解と解説を見る
正解：C
解説：
配列でリストを実現する場合、宣言時に最大要素数分のメモリ領域をまとめて確保します。格納する要素数が最大長より少なければ、残りの領域は未使用のまま残ります。FE H25秋 午前問6およびAP R4春 午前問5で、まさにこの選択肢が正解として出題されました。
選択肢Aはポインタで実現する連結リストの特徴です。配列実装では連続領域を事前に確保するため、要素追加のたびに動的確保を行う必要はありません。選択肢Bもポインタ実装の連結リストの特徴です。配列実装では添字から参照先アドレスを計算できるため、中間要素へも一定時間でアクセスできます。
よくある質問（FAQ）
Q. 配列とリスト、実務ではどちらを使う場面が多いですか？
現代のプログラミングでは、多くの言語が「可変長配列」（JavaのArrayList、PythonのList、JavaScriptのArray）を標準で提供しており、実務で純粋な固定長配列や生のポインタ連結リストを直接書く場面は減っています。ただし、これらの可変長配列は内部的に配列のサイズ拡張とコピーを行っているため、IPA試験で問われる配列の性質（連続領域確保、挿入時の要素移動）を理解しておくことは実務でも役立ちます。
Q. スタックやキューもデータ構造ですか？配列・リストとの関係は？
スタック（後入れ先出し）やキュー（先入れ先出し）は「データの出し入れルール」を定めた抽象データ型であり、その内部実装に配列や連結リストを使います。つまり配列とリストは「物理的な格納方法」、スタックとキューは「論理的な操作ルール」という関係です。逆ポーランド記法の計算でスタックが登場するのもこの仕組みです。
Q. 「二次元配列」はIPA試験で出題されますか？
出題されます。FE科目Bのサンプル問題（問4）では、二次元配列に格納された行列データを疎行列の形式に変換するプログラムが出題されました。二次元配列は「配列の配列」であり、行と列の2つの添字でアクセスする構造です。行列演算や表形式データの処理で登場するため、一次元配列の考え方を拡張して理解しておくと対応できます。
Q. 試験問題で「配列によるリスト操作」をトレースするコツはありますか？
紙に配列の表を書き、next[i]の値を矢印で図示するのが最も確実な方法です。挿入処理では「①挿入ノードのnextに、挿入位置の次の要素番号を代入する」「②挿入位置の手前のノードのnextに、挿入ノードの要素番号を代入する」という2ステップを順番に追えば間違えません。焦ってポインタを同時に書き換えようとするとミスの原因になります。
