情報科学 › アルゴリズムとデータ構造 › 基本的なデータ構造

連結リストの基本操作の計算量

命題 4.2（「基本的なデータ構造」§4）・ ✓公理まで証明済み

$n$ 個のノードからなる単方向連結リストについて、ワード RAM モデルの下で次が成り立つ。

ノード $p$ への参照が与えられているとき、 $p$ の直後への新しいノードの挿入、および $p$ の直後のノードの削除は、いずれも $\Theta(1)$ 時間で行える。
先頭から数えて $k$ 番目（ $0$ 始まり、 $0 \le k \le n-1$ ）のノードへ到達するには、 $\mathrm{next}$ の追跡がちょうど $k$ 回必要であり、 $\Theta(k)$ 時間かかる。最悪は $\Theta(n)$ である。
単方向連結リストでは、ノード $p$ への参照が与えられていても、 $p$ 自身の削除には最悪 $\Theta(n)$ 時間かかる。双方向連結リストであれば $\Theta(1)$ 時間で行える。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 1 件、定義なども含めて 4 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 4 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

単方向連結リスト定義 4.1・基本的なデータ構造
配列の基本操作の計算量✓命題 3.2・基本的なデータ構造
- 配列定義 3.1・基本的なデータ構造
配列定義 3.1・基本的なデータ構造
番兵ノード注意 4.4・基本的なデータ構造

これを使っている定理証明で参照している 1 件

括弧列の判定✓定理 6.2・基本的なデータ構造

関連するノック 2 問