基本情報技術者 2018年 春期 午前（科目A） 問06
問題文
リストを二つの1次元配列で実現する。配列要素box[i]とnext[i]の対がリストの一つの要素に対応し、box[i]に要素の値が入り、next[i]に次の要素の番号が入る。配列が図の状態の場合、リストの3番目と4番目との間に値がHである要素を挿入したときのnext[8]の値はどれか。ここで、next[0]がリストの先頭（1番目）の要素を指し、next[i]の値が0である要素はリストの最後を示し、next[i]の値が空白である要素はリストに連結されていない。
選択肢
ア：3
イ：5
ウ：7（正解）
エ：8
🔒 解説は解答すると表示されます
配列による単方向リスト挿入【午前解説】
正解の理由
配列表現の連結リストではnext[0] が先頭を示し，next[i]=0が末尾を示します。図より先頭はnext[0]=1で，辿ると1 → 5 → 3 → 7 → 2 → 0の順になります。
3番目の要素はインデックス3（値C），4番目はインデックス7（値G）です。値Hはindex 8に格納するので，挿入のために次の操作を行います：next[8] に元々3の次であった7を代入し，その後next[3] を8に変更します。したがってnext[8] の値は7であり，選択肢では ウ が正解です。
3番目の要素はインデックス3（値C），4番目はインデックス7（値G）です。値Hはindex 8に格納するので，挿入のために次の操作を行います：next[8] に元々3の次であった7を代入し，その後next[3] を8に変更します。したがってnext[8] の値は7であり，選択肢では ウ が正解です。
解法ステップ
- next[0] から始めてnextを辿り，現在の連結順を求める（1 → 5 → 3 → 7 → 2 → 0）。
- 3番目と4番目の要素を確認する（3番目はインデックス3、4番目はインデックス7）。
- 挿入するノードのインデックス（ここでは8）を決める（box[8]=H）。
- next[8] に元のprev（3）の次を代入する（next[8] = next[3] = 7）。
- prevのnextをnewに更新する（next[3] = 8）。これで3 → 8 → 7の連結が完成する。
選択肢別の誤答解説
- ア: 3
誤り。これはnext[8] をprev（挿入位置の直前ノード）にしてしまう誤解。正しくはprevの次を指す値をnewに代入するので3ではなく7です。 - イ: 5
誤り。5はリスト中の別ノード（2番目）への参照で，3と7の間の挿入とは無関係です。next[5] は既に3を指しています。 - ウ: 7
正解。挿入後new（8）の次は元々prev（3）が指していたノード7になるためnext[8]=7となります。 - エ: 8
誤り。self reference（自分自身を指す）はループを作り意図しない構造になります。挿入時はnewが元の次を指すべきで自己参照ではありません。
よくある誤解
- 「next[i]=0を未使用の意味と誤解」：ここではnext[i]=0がリストの末尾（NULL）を意味し，未使用セルは空白で示されています。
- 「挿入時の代入順を逆にする」：先にprevのnextをnewにしてしまうと元の次要素を失いnext[new] に正しい値を入れられません。
- 「要素番号と要素の順序を混同する」：k番目の要素の中身（箱の値）と配列インデックス（ノード番号）を取り違えるミスが多いです。
補足コラム
配列で連結リストを実装する方式は，ポインタの代わりに配列インデックスを使う古典的手法です。挿入操作の安全な手順は常に次の通りです：
- next[new] = next[prev]
- next[prev] = new
この順序を守ることでリンクを失う事故を防げます。空きセル管理（フリーリスト）を用いれば，削除したセルを再利用できます。
参考としてPython風の擬似コード（インデックス基準は図と同様）：
# next: リストのnext配列（0-9）
# new = 8, prev = 3
next[new] = next[prev] # next[8] = 7
next[prev] = new # next[3] = 8
FAQ
Q1: next[0] が先頭ポインタなのはなぜですか？
A1: 図や設問でそう定義されているためです。配列実装では特殊セル（ここではindex 0）を先頭ポインタに使う慣習がよくあります。
A1: 図や設問でそう定義されているためです。配列実装では特殊セル（ここではindex 0）を先頭ポインタに使う慣習がよくあります。
Q2: next[i]=0と空白はどう違いますか？
A2: next[i]=0は「リストの末尾（NULL）」を示し，空白は「その配列要素がリストに連結されていない（未使用）」ことを示します。
A2: next[i]=0は「リストの末尾（NULL）」を示し，空白は「その配列要素がリストに連結されていない（未使用）」ことを示します。
Q3: 空のリストに挿入するときはどうする？
A3: 先頭が空の場合（next[0] = 0等），新ノードのnextを0にしてnext[0] を新ノードのインデックスに設定します。
A3: 先頭が空の場合（next[0] = 0等），新ノードのnextを0にしてnext[0] を新ノードのインデックスに設定します。
関連キーワード: リスト、配列実装、連結リスト、挿入操作、ポインタ管理
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！