なぜ二重リンクリストのアドオンの実行時間はO（1）ですか？

Question

データ構造では、単一リンクリスト内のノードがO（n）操作になる前に要素をプッシュするといいでしょう！後方ポインタがないので、新しい要素の前に追加しようとしているキーに到達するために、要素を一貫して歩かなければなりません。したがって、それは線形実行時間を有する。 次に、二重リンクリストを導入すると、問題が解決され、今度は両方向のポインタが一定の時間操作O（1）になる前にプッシュしていると言います。 私は論理を理解していますが、まだ何かが私に混乱しています！リストの要素に一定の時間アクセスを持たないので、前に追加したい要素を見つけるために、前の要素を歩かなければなりません！これは、二重リンクリストでadd-beforeコマンドを実装する方が速くなりましたが、依然として興味あるキーを見つける操作はO（n）です！なぜ、二重リンクリストを使ってaddの演算がO（1）になるのですか？

おかげで、C++で

Answer 1

は、スタンダード::リスト::挿入（）関数は、挿入を行うべき場所を示すために反復子をとります。つまり、呼び出し元には既にこのイテレータがあり、挿入操作はではなく、であるため、一定時間内に実行されます。

しかし、find（）アルゴリズムは線形であり、リスト要素を検索する通常の方法です。 + insertを見つける必要がある場合、その組み合わせはO（n）です。

ただし、挿入する前に検索する必要はありません。たとえば、キャッシュされた（有効な）イテレータを使用している場合、一定時間内に対応する要素の前に挿入（または削除）できます。