ソートされたリンクリストにノードを挿入する時間の複雑さ

Question

Javaのソート済みリンクリストにノードを挿入する時間の複雑さはどのくらいですか？複雑さが未満のアルゴリズムがありますか？O（n）？

Answer 1

あなたが持っているものはすべてリンクされたリンクであり、最悪の場合はリスト全体を繰り返して挿入ポイントを見つける必要があります。これは、O（n）最悪ケース時間を与える。

skiplistのようなものは、O（log n）挿入を与えることができます。しかし、それはあなたが尋ねているものとは異なるデータ構造です（木などもあります）。