[解決済み] リンクリストの途中への挿入はなぜO(1)なのか？

質問

によると ウィキペディアのリンクリストの記事 によると、リンクリストの途中への挿入は O(1) とされています。 私はO(n)であろうと思います。 リストの末尾に近いノードを見つける必要はないのでしょうか？

この解析は、ノード操作の発見を考慮せず (必要ではありますが)、挿入そのものだけを考慮するのでしょうか?

EDIT :

リンクリストは配列と比較していくつかの利点があります。リストの特定のポイントへの要素の挿入は一定時間の操作ですが、配列への挿入は要素の半分、あるいはそれ以上を移動する必要があるかもしれません。

上記のステートメントは、私には少し誤解を招くものです。 私が間違っているならば訂正してください、しかし私は結論はそうあるべきだと思います。

配列です。

• 挿入/削除のポイントを見つける O(1)
• 挿入/削除の実行 O(n)

リンクされたリスト

• 挿入/削除のポイントを見つける O(n)
• 挿入/削除の実行 O(1)

位置を見つける必要がないのは、何らかのポインタを保持している場合だけだと思います（いくつかのケースでヘッドとテールがそうであるように）。 ですから、挿入/削除のオプションについて、リンクされたリストが常に配列に勝るとは、一概に言えません。

どのように解決するのですか?

その通り、この記事では "Indexing"を別の操作として考えています。つまり、挿入自体は O(1) ですが、その中間ノードに到達するのは O(n) です。