双方向リストとは？そうほうこうりすと
双方向リストとは、連結リストのうち、各要素が次への参照だけでなく前への参照も持つもの。ある要素を指す参照が手元にあれば、その前の要素を先頭からたどり直さずに特定できるので、削除や直前への挿入が定数時間で済む。代わりに参照1本ぶんの領域が要素ごとに増える、という釣合いの上に成り立っている。
最終更新：2026-10-06
この語が出る過去問を解く →背景
片方向リストは挿入・削除がポインタの張替えだけで済む点で配列に勝るが、前の要素を知る手段がないため、削除したい要素が分かっていても先頭から探し直さなければならない。そのぶん手続き全体がO(n)になり、挿入・削除が速いという利点が実際には出ない。双方向リストは、この穴を領域1本ぶんの追加で埋める設計である。
具体例
JavaのLinkedListやC++のstd::listは双方向リストで実装されており、イテレータの位置から前後どちらへも進める。OSのプロセス管理でも、実行可能状態のプロセスを双方向リストでつなぎ、任意の位置のプロセスをキューから外す操作を定数時間で行っている。
試験での引っ掛け
ポインタの張替えは前後2か所を必ず両方直す必要があり、片方だけ直す手順が誤答の選択肢として出る。先頭・末尾では相手側のポインタがナルになる（環状リストなら先頭と末尾がつながる）点、探索そのものは依然としてO(n)で速くなるのは削除・挿入の手続きだけである点も問われる。
関連用語
出た過去問
出典：令和5年度 秋期 応用情報技術者試験 午前 問5（IPA）
双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき、要素Dの次に要素Cを挿入した後のnex…
正解：next[6]=5, prev[6]=3
要点：双方向リスト挿入は前後2要素のリンクを張り替える
挿入前はnext[3]=5、prev[5]=3なので、要素D（要素番号3）の次は要素E（要素番号5）である。この間に新しい要素Cを配列末尾の要素番号6として挿入するので、Cの前はD、Cの後はEになる。したがってnext[6]=5、prev[6]=3となる（あわせてnext[3]とprev[5]も6に更新される）。
出典・参考
公式シラバスの1 基礎理論 ＞ 1. データ構造 ＞ (2) データ構造の種類に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。