連結リストの構造とポインタ操作
連結リスト（データ部＋ポインタ部）と配列の長所・短所を見分け、双方向リストや配列で作ったリストに要素を挿入したとき「どのポインタが書き換わるか」を自力で答えられるようになる。
配列とリストの違いは、科目Aで形を変えながら何度も出る定番です（観測値で本試験系5回・免除8回）。ポインタの付け替えは科目Bの擬似言語問題でもそのまま使うので、ここで手順を体に入れておくと両方で得点できます。
このレッスンで稽古する（用語チェック・過去問）結論：リストは「データ＋次の場所」を数珠つなぎにしたもの
**線形リスト（連結リスト）**は、各要素が データ部（値そのもの）と ポインタ部（次の要素が置いてある場所＝アドレス）の2つを持つデータ構造です。要素はメモリ上でバラバラに置かれていてよく、ポインタをたどって順番に読みます。最後の要素のポインタには「次は無い」ことを示す値（0やNULL）を入れます。
たとえるなら宝探しのメモです。1枚目のメモに「宝その1」と「次のメモは本棚の上」と書いてあり、そこへ行くと次のメモがある、という具合です。途中のメモは、前から順にたどらないと見つかりません。
配列とリストの比較（ここが一番出る）
配列は、同じ型のデータを連続した領域に並べ、添字（何番目かを表す番号）で直接アクセスする構造です。リストとは長所と短所がちょうど逆になっています。
| 観点 | 配列 | 連結リスト（ポインタで実現） |
|---|---|---|
| k番目の要素を読む | 添字で直接アクセス（要素数によらず一定時間） | 先頭から順にたどる（要素数に比例） |
| 途中への挿入・削除 | 後ろの要素をずらす必要あり（要素数に比例） | ポインタの付け替えだけ（位置が分かっていれば一定時間） |
| 2分探索 | 向いている（真ん中に直接飛べる） | 向いていない（真ん中に飛べない） |
| 領域 | 最大長分を先に確保→未使用領域が出やすい | 必要な分だけ確保。ただしポインタ部の領域が余分に要る |
覚え方は1つだけです。「配列は読むのが得意、リストは書き換えるのが得意」。選択肢がどちらの長所を述べているかを判定すれば、ほぼ解けます。
単方向リストと双方向リスト
ポインタが「次」だけのものを単方向リスト、「次」と「前」の2つを持つものを双方向リストと呼びます。双方向は逆向きにもたどれる代わりに、挿入・削除で書き換えるポインタが増えます。
| 種類 | ポインタ | 間に新要素Gを入れるとき既存要素で変わるもの |
|---|---|---|
| 単方向リスト | 次ポインタのみ | 前の要素の次ポインタだけ（1か所） |
| 双方向リスト | 次ポインタ＋前ポインタ | 前の要素の次ポインタと、後ろの要素の前ポインタ（2か所） |
どちらの場合も、新要素G自身のポインタは「新しく書き込む」もので、既存要素の値が変わるわけではありません。設問が「追加前と比べて値が変わるポインタ」を聞いているときは、既存要素だけを数えます。
flowchart LR
A["A（前の要素）"] -->|"次: Gへ書き換え"| G["G（新要素）"]
G -->|"次: K"| K["K（後ろの要素）"]
K -.->|"前: Gへ書き換え"| G
G -.->|"前: A"| A
挿入の基本手順（単方向・双方向共通の考え方）
挿入は必ず**「新要素のポインタを先に決める → 前の要素のポインタを新要素へ向ける」**の順で考えます。先に前の要素を書き換えると、元の「次」がどこだったか分からなくなるからです。
- 新要素の「次」＝ 前の要素が元々指していた場所
- 前の要素の「次」＝ 新要素の場所
- （双方向なら）後ろの要素の「前」＝ 新要素の場所、新要素の「前」＝ 前の要素の場所
削除は逆で、消したい要素の前の要素の「次」を、消したい要素の「次」に付け替えるだけです。
配列2本でリストを作る問題
ポインタが使えない場面を想定し、**値を入れる配列（box）と次の要素の添字を入れる配列（next）**の2本でリストを表すことがあります。このとき next の値は「アドレス」ではなく「添字」ですが、考え方はポインタとまったく同じです。
最大の落とし穴は、リストの順番は添字の順ではないことです。必ず先頭（next[0]など）から next をたどって、1番目・2番目…を書き出してから挿入位置を決めます。
メモリ割当て失敗に備える（1〜2文で十分）
リストの要素は実行中に領域割付け関数（動的にメモリを確保する関数）で作ることが多く、メモリ不足などで失敗する場合があります。そのためコーディング規約では「割付けに失敗したときの処理を必ず書く」と定めるのが適切です。
試験での問われ方
- 配列とリストの特徴を入れ替える：「配列は挿入・削除が効率的」「リストは任意の要素に直接アクセスできる」「リストは2分探索が得意」はすべて誤り。
- 他のデータ構造と混ぜる：「ポインタから次の要素をハッシュ関数で求める」（ハッシュ表の話）、「先頭を根とした木」（木構造の話）は誤り。
- ついでに他の構造の定義をずらす：「スタックは先入れ先出し」（正しくは後入れ先出し）、「2分木は全ての節が2つの子を持つ」（子は最大2つ、0や1でもよい）。
- 双方向リストの書き換え箇所を多めに見せる：前の要素の「前ポインタ」や後ろの要素の「次ポインタ」まで変わるように見せる選択肢がある。
- next配列の順番の取り違え：添字順にリストが並んでいると思わせる。
双方向リストで社員Aと社員Kの間に社員Gを入れる
| アドレス | 社員名 | 次ポインタ | 前ポインタ |
|---|---|---|---|
| 100 | 社員 A | 300 | 0 |
| 200 | 社員 T | 0 | 300 |
| 300 | 社員 K | 200 | 100 |
| アドレス | 社員名 | 次ポインタ | 前ポインタ |
|---|---|---|---|
| 100 | 社員 A | a | b |
| 200 | 社員 T | c | d |
| 300 | 社員 K | e | f |
| 400 | 社員 G | x | y |
ア a，b，e，f
イ a，e，f
ウ a，f
エ b，e
出典：令和5年度 基本情報技術者試験 科目A 公開問題 問2
解き方と答えを見る
- まず今の並びを確認する。A(100)の次=300(K)、K(300)の次=200(T)、T(200)の次=0(終わり)。よって順番は A → K → T。
- 前ポインタも確認する。A(100)の前=0(先頭)、K(300)の前=100(A)、T(200)の前=300(K)。
- 新要素G(アドレス400)をAとKの間に入れる。Gの次=300(K)、Gの前=100(A)。これは新しく書く x, y なので、設問の a〜f には含まれない。
- 前の要素Aの次ポインタ a：300 → 400 に変わる。
- 後ろの要素Kの前ポインタ f：100 → 400 に変わる。
- 変わらないものを確認する。Aの前ポインタ b=0 のまま、Kの次ポインタ e=200 のまま、Tの c=0・d=300 もそのまま。
- 変わるのは a と f だけ。
答え：ウ（a，f）
box/next の2配列リストで3番目と4番目の間にHを入れたときの next[8]
ア 3
イ 5
ウ 7
エ 8
解き方と答えを見る
- 先頭から next をたどって順番を書き出す。next[0]=1 → 1番目は添字1(A)。
- next[1]=5 → 2番目は添字5(E)。
- next[5]=3 → 3番目は添字3(C)。
- next[3]=7 → 4番目は添字7(G)。
- next[7]=2 → 5番目は添字2(B)。next[2]=0 なのでここで終わり。順番は A → E → C → G → B。
- Hは添字8に入っている。3番目(C, 添字3)と4番目(G, 添字7)の間に入れる。
- 新要素の次を先に決める：next[8] = Cが元々指していた先 = next[3] の元の値 = 7。
- 前の要素を新要素へ向ける：next[3] = 8。
- よって next[8] の値は 7。
答え：ウ（7）
要点（試験直前に読む）
- 線形リスト＝データ部＋ポインタ部（次の要素の格納先）。
- 配列は「読むのが得意」（添字で直接アクセス・2分探索向き）、リストは「書き換えが得意」（ポインタ付け替えで挿入・削除）。
- 配列で作ったリストは最大長分を先に確保するので未使用領域が出る。リストはポインタ部の領域が余分に要る。
- 双方向リストで間に挿入すると、既存で変わるのは「前の要素の次」と「後ろの要素の前」の2つだけ。
- next配列の問題は、先頭から必ずたどって順番を書き出す。新要素のnextは前の要素が元々指していた値。
- 領域割付け関数を使うときは、失敗したときの処理を書く。
ひっかけ
- 「配列は挿入・削除が効率的」「リストは任意の要素に直接アクセスできる」→長所と短所が逆。「配列は読む、リストは書き換え」で判定する。
- 「リストは2分探索が効率的」「ハッシュ関数で次の要素を求める」→2分探索は配列向き、ハッシュは別の構造。
- 双方向リストで、前の要素の前ポインタや後ろの要素の次ポインタまで変わると思わせる→間の側を向いたポインタだけが変わる。
- next配列で添字の順番をそのままリストの順番と思い込む→先頭からnextをたどって並べ直す。
- 新要素のnextに前の要素の番号を入れる→入れるのは前の要素が元々指していた「次」の番号。
用語（15）
要素を一直線の順序でつなぎ、各要素がデータ部と次の要素を指すポインタ部を持つデータ構造。
⚠ 配列は連続した領域に並べて添字で直接アクセスする。リストはポインタをたどる。
ポインタで要素同士をつないだリストのことで、試験では線形リストとほぼ同じ意味で使われる。
リストの各要素のうち、値そのものを入れる部分。
⚠ ポインタ部は値ではなく「次の要素の場所」を入れる部分。
リストの各要素のうち、次（双方向なら前も）の要素の格納先を入れる部分。
⚠ ハッシュ関数で次の場所を計算するわけではない。値をそのまま保持している。
データが置かれているメモリ上の場所（アドレス）を指し示す値。
⚠ 添字は配列の中での番号。配列2本で作るリストでは、next に入る添字がポインタの役割をする。
各要素が次の要素へのポインタだけを持ち、先頭から後ろへの一方向にしかたどれないリスト。
⚠ 双方向リストは前ポインタも持つので逆向きにもたどれる。
各要素が次の要素と前の要素の両方へのポインタを持つリスト。
⚠ 挿入時に変わる既存ポインタは、前の要素の次ポインタと後ろの要素の前ポインタの2つ。
同じ型のデータを連続した領域に並べ、添字で任意の要素に直接アクセスできるデータ構造。
⚠ 途中への挿入・削除は要素の移動が要るので苦手。ポインタの付け替えだけで済むのはリスト。
配列の何番目の要素かを表す番号。
⚠ リストの並び順と添字の順は一致するとは限らない。
位置を指定するだけで、前から順にたどらずに任意の要素を読めること。
⚠ 順次アクセスは先頭から順にたどる方式で、リストはこちら。
整列済みのデータの真ん中と比べて探す範囲を半分ずつ絞る探索法。
⚠ 真ん中に直接飛ぶ必要があるので配列向き。リストでは効率が悪い。
最後に入れたデータを最初に取り出す（後入れ先出し・LIFO）データ構造。
⚠ 先入れ先出し（FIFO）はキュー。
最初に入れたデータを最初に取り出す（先入れ先出し・FIFO）データ構造。
⚠ スタックはLIFO。
各節が持つ子が最大2つの木構造。
⚠ 「全ての節が2つの子を持つ」は誤り。子が0個や1個の節があってもよい。
プログラム実行中に必要な分のメモリ領域を確保する関数。
⚠ 必ず成功するわけではないので、失敗時の処理を書くことがコーディング規約の適切な規定。
このレッスンの過去問
- 線形リストの構造(データ部とポインタ部)基本情報技術者試験 科目A免除 修了試験 20260726 実施分 問5
- 連結リストと配列の特徴比較平成29年度 春期 基本情報技術者試験 午前 問4
- 双方向連結リストへの挿入操作令和5年度 基本情報技術者試験 科目A 公開問題 問2
- 配列で実現したリストへの要素挿入(next更新)平成30年度 春期 基本情報技術者試験 午前 問6
- メモリ割当て失敗時のエラー処理平成30年度 秋期 基本情報技術者試験 午前 問7