連結リスト

定義

各要素が次要素へのポインタを持つデータ構造。挿入・削除はO(1)で可能。

詳細解説

ノードがデータと次ノードへのポインタを持ち、メモリ上で不連続に配置できる。単方向リスト、双方向リスト、循環リストがある。先頭・末尾の要素挿入・削除はO(1)（参照を保持していれば）だが、任意位置の検索はO(n)。配列と異なりサイズが動的に変化し、連続領域を要しない利点があるが、ポインタ分のメモリオーバヘッドとキャッシュ効率の悪さが欠点。スタック、キュー、グラフの隣接リスト等の基盤として利用される。

「連結リスト」が出る問題

• スタックの動作原理として、正しいものはどれか。

• 配列とリストの特徴を比較したとき、リストの利点として正しいものはどれか。

• 要素数 n の配列に対するクイックソートの平均計算量と最悪計算量の組合せはどれか。

関連用語

よくある質問