リンクリストの途中に挿入すると O(1) になるのはなぜですか? 質問する

によるリンクリストに関するWikipediaの記事リンクリストの途中に挿入する場合は O(1) とみなされます。O(n) になると思います。リストの末尾近くにあるノードを見つける必要はないでしょうか?

この分析では、ノード操作の検出 (必須ですが) は考慮されず、挿入自体のみが考慮されるのでしょうか?

編集:

リンク リストには、配列に比べていくつかの利点があります。リストの特定のポイントに要素を挿入する操作は一定時間で実行されますが、配列への挿入では要素の半分以上を移動する必要がある場合があります。

上記の記述は、私にとっては少々誤解を招くものだと思います。間違っていたら訂正してください。しかし、結論はこうであるべきだと思います。

配列:

• 挿入/削除ポイントの検索 O(1)
• 挿入/削除をO(n)で実行する

リンクリスト:

• 挿入/削除ポイントの検索 O(n)
• 挿入/削除の実行 O(1)

位置を見つける必要がないのは、何らかのポインター (場合によっては先頭と末尾) を保持している場合だけだと思います。したがって、挿入/削除オプションに関して、リンク リストが常に配列よりも優れているとは断言できません。