linked list - 応用例 - リンクリストO(1)の途中に挿入するのはなぜですか?




循環リスト 応用例 (10)

この分析では、ノード操作の検出(必須ではありますが)と挿入自体のみが考慮されていますか?

あなたはそれを持っています。 指定したポイントでの挿入は、挿入するアイテムへのポインタをすでに保持していることを前提としています。

InsertItem(item * newItem, item * afterItem)

リンクリストに関するWikipediaの記事によると、 リンクリストの途中に挿入すると、O(1)とみなされます。 私はそれがO(n)と思うだろう。 リストの終わり近くにあるかもしれないノードを見つける必要はありませんか?

この分析では、ノード操作の検出(必須ではありますが)と挿入自体のみが考慮されていますか?

編集

リンクされたリストには、配列よりもいくつかの利点があります。 リストの特定の点に要素を挿入することは、一定時間の操作ですが、配列に挿入するには要素の半分以上を移動する必要があります。

上記のステートメントは私に少し誤解を招く。 私が間違っている場合は私を修正しますが、結論は次のようにすべきです:

配列:

  • 挿入/削除点の発見O(1)
  • 挿入/削除の実行O(n)

リンクされたリスト:

  • 挿入/削除点の発見O(n)
  • 挿入/削除の実行O(1)

私はあなたがそれに何らかのポインタを置いていればポジションを見つける必要がない唯一の時間があると思います(場合によっては頭と尾のように)。 だから私たちは、リンクリストは常に挿入/削除オプションの配列に勝ると言うことはできません。


O(1)は、新しい項目を挿入する項目があるという事実に依存します。 (前または後)。 あなたがその項目を見つけなければならないので、あなたがしなければ、それはO(n)です。


あなたは正しいです、記事では、別の操作として "インデックス作成"と考えています。 したがって、挿入自体はO(1)ですが、その中間ノードに到達するのはO(n)です。


いいえ、それは検索のためのものではありません。 しかし、すでにリストの途中にある項目へのポインタを保持している場合は、その時点での挿入はO(1)です。

それを検索する必要がある場合は、検索の時間を追加する必要があります.O(n)にする必要があります。


この記事では、配列とリストを比較する方法について説明します。 配列とリストの両方の挿入位置を見つけることはO(N)なので、記事はそれを無視します。


これはループを伴わないためです。

挿入は次のようなものです:

  • 要素を挿入する
  • 前へのリンク
  • 次へのリンク
  • 完了

これはどんな場合でも一定の時間です。

したがって、n個の要素を1つずつ挿入することはO(n)です。


リンクされたリストの操作がO(1)の後に挿入するノードの参照がある場合。
配列の場合は、すべての連続ノードを移動する必要があるため、まだO(n)です。


リンクリストへの挿入は、それを反復することとは異なります。 アイテムが見つからない場合は、ポインタをリセットしてそのアイテムをそこに配置します。 フロントエンドの近くに挿入されようとエンドの近くに挿入されるかどうかは関係ありませんが、挿入にはまだポインタが再割り当てされます。 もちろん、それが実装された方法に依存しますが、それはリストの強みです。簡単に挿入できます。 viaインデックスへのアクセスは、配列が輝く場所です。 リストの場合は、通常はn番目のアイテムを見つけるためにO(n)になります。 少なくともそれは私が学校から覚えているものです。


最も一般的なケースは、リストの最初または最後に挿入されている可能性があります(リストの最後には検索に時間がかかりません)。

配列の最初または最後に項目を挿入すること(配列が最後にある場合は配列のサイズを変更する必要があります。または、最初の要素があればすべての要素をサイズ変更して移動する必要があります)。


私は、あなたがO()表記のために数えることを選んだのは単なるケースだと思う。 挿入する場合には、通常のカウント動作はコピー動作である。 配列では、中央に挿入すると、上のすべての場所をメモリにコピーします。 リンクされたリストでは、これは2つのポインタを設定します。 挿入する内容に関係なく、場所を見つける必要があります。