基本情報 令和5年度 科目A 問2：テクノロジ系に関する問題

答えは c「a, f」 です。

双方向リストは「次の人を指す矢印」と「前の人を指す矢印」を持つチェーン構造。電車の連結を想像してください。A→Kの間にGを割り込ませる場合:

• Aの“次=次の車両”はK→Gに変更(=ポインタa変わる)
• Kの“前=前の車両”はA→Gに変更(=ポインタf変わる)

T(別グループ)は今回いじらないのでb,c,d,eは変化なし。

👉 覚え方：割り込み箇所の両隣だけ、片方ずつ書き換わる。

ほかの選択肢: a b e f / a e f / b e はどれも変えなくていいポインタが混じってる。

なぜこれが正解か

正解は c (a, f)。追加前: A(次=K, 前=0) ⇄ K(次=T, 前=A) ⇄ T(次=0, 前=K)。A-K間にGを挿入するため変更されるのは(1)Aの次ポインタ(a): K→G、(2)Kの前ポインタ(f): A→G。

変更されないポインタ

• b(Aの前ポインタ): もともと0、変化なし。
• c(Tの次ポインタ): 変化なし。
• d(Tの前ポインタ): Kのままで変化なし。
• e(Kの次ポインタ): T(=200)のままで変化なし。

新規追加されるG(400番地)のポインタ

• x(Gの次)= 300(K)
• y(Gの前)= 100(A)

覚え方・ひっかけ注意

双方向リストの中間挿入では両隣ノードの“内側を向くポインタ”2本のみが書き換わる(=a,f)。端での挿入(先頭/末尾)・削除も同様に「変更箇所は最小」と覚える。問題文がリスト走査ではなくポインタの書き換えを問う場合、表を必ず手書きで矢印を引き直すと事故を防げる。

理論的背景

双方向連結リスト(Doubly Linked List)はノードがprev/nextの2ポインタを持つデータ構造。挿入・削除はO(1)(参照ノード判明時)、ランダムアクセスはO(n)。単方向リストと比較して、双方向は逆方向走査と任意ノード削除が容易な反面、ポインタ更新箇所が増え、競合時の整合性管理が複雑化する。番兵(sentinel/dummy)ノードを先頭・末尾に置く実装では境界条件の場合分けが不要になり、コードがシンプル化する常套テクニック。

実務での使われ方

LRUキャッシュ実装(双方向リスト+ハッシュマップ)は典型例で、Redis/MemcachedのLRU/LFU evictionアルゴリズムの基礎。LinuxカーネルではマクロベースのIntrusive Linked List(list.h)が遍在し、双方向循環リストでタスクキュー・メモリ管理・スケジューラ等を実装。GUI実装ではブラウザのDOM(Document Object Model)が双方向ツリー+リスト相当の構造で、parent/sibling/childポインタを持つ。並行プログラミングではロックフリー双方向リストの実装は極めて困難で、CAS(Compare-And-Swap)操作だけでは整合性確保が難しいためHazard Pointer・RCU(Read-Copy-Update)・Lock-Free Skip List等の代替手法が用いられる。

試験での位置づけ

FE科目AではC言語/疑似コードでのポインタ操作問題として頻出。具体的挿入手順:

```

G.next = A.next; // x = K

G.prev = A; // y = A の番地

A.next.prev = G; // K.prev = G (=f書換)

A.next = G; // (=a書換)

```

この順序が重要で、A.nextを先に書き換えるとK.prevが取得不能になりバグになる。応用情報・データベース試験では、Bツリー・B+ツリー・赤黒木・AVL木・スキップリスト・ハッシュテーブル(チェイン法/オープンアドレス法)等のデータ構造選定論点まで広がる。

選択肢の発展補足

単方向リストへの挿入であれば変更箇所は1ヶ所(直前ノードのnextのみ)だが、挿入位置を見つけるためにO(n)走査が必要。配列との比較では、挿入O(1) vs ランダムアクセスO(1)のトレードオフを理解する。本問のような“どのポインタが書き換わるか”を聞く問題は、まず追加前後の状態を表に書き出し、変化セルだけマークする手順を踏むと確実。試験本番では時間短縮のため、変化なしを先に消去する消去法も有効。