アルゴリズム・プログラミング誤り発見
連結リスト（linked list）に関する記述のうち、誤っているものはどれか。
A.単方向連結リストでは、各ノードは次のノードへのポインタを持つ。
✓ この記述は正しい。単方向連結リストの各ノードは値とnextポインタを持つ基本構造である。
B.連結リストの先頭への要素挿入は、配列の先頭挿入と比べて一般的に高速である。
✓ この記述は正しい。連結リストの先頭挿入はO(1)で可能だが、配列はO(n)のシフトが必要である。
C.連結リストはランダムアクセスが配列と同等であり、任意のインデックスの要素をO(1)で取得できる。← 正解
✓ 正解です。この記述が誤りで、正しくは連結リストのランダムアクセスはO(n)であり、配列のO(1)と異なる。
D.双方向連結リストでは、各ノードは前後のノードへのポインタを持つ。
✓ この記述は正しい。双方向連結リストはprevとnextの2つのポインタを各ノードが保持する。