アルゴリズムとプログラミングアルゴリズムとデータ構造

単方向連結リストの先頭にノードを1個挿入する操作の計算量として、適切なものはどれか。

ア.O(1)正解

イ.O(log n)

ウ.O(n)

エ.O(n²)

解説

連結リストの先頭挿入は「新ノードの next を旧先頭に向けて、先頭ポインタを新ノードに付け替える」だけ。要素数とは無関係に一瞬で終わります。

なぜアが正解か

先頭挿入は「new.next = head; head = new」の2命令で完了するため、リストの長さ n に依存せず常に O(1)。配列の先頭挿入が O(n)（全要素を後ろにずらす必要あり）と対照的で、ここが連結リストの最大の長所です。

なぜイは間違いか

O(log n) は二分探索や平衡木の操作で出てくる量。連結リストは「次へ次へ」とたどる線形構造なので、log は自然には現れません。

なぜウは間違いか

O(n) は末尾挿入や指定位置探索の計算量です。先頭挿入と取り違えた典型ミス——「リスト＝走査が遅い」のイメージだけで選ぶと落とし穴になります。

なぜエは間違いか

O(n²) はナイーブなソートで出る量。1ノード挿入ごときで二重ループが発生する状況はなく、過剰見積もりの極致です。

出典: AI生成問題（学習用）

← 前の問題

空のスタックに対して、push(1)、push(2)、push(3)、pop、push(4)、pop、pop の操作を順に行ったとき、最後に pop で取り出される値はどれか。

次の問題 →

ハッシュ法によるデータ管理において、異なるキーが同じハッシュ値を返す現象を何と呼ぶか。