1

私は自分自身の（可能な限り標準に近い）単一のリンクリストの実装を書き込もうとしています。しかし、私は人々がそのようなリストに何時の複雑さを期待するのか疑問に思っていますか？

特に挿入するために、私はそれをどのように実装すべきか疑問に思っています。私はインターネット上のいくつかの場所を読みました。挿入はO（1）であると言う人もいれば、O（n）と言う人もいます。すべてが二重リンクリストがO（1）であることに同意しています。しかし、O（1）は単一のリンクリストにも当てはまると思いますか？

前のノードを知っている限り、前のノードが新しい新しいノードを指すようにするだけで、新しいノードは前のノードが最初に指していた場所を指します。

そうは言っても、人々はどのようinsertに行動することを期待しているのだろうか？通常、指定されたイテレータの前に要素を挿入します。ただし、単一のリンクリストではそうするのは困難です（O(n)前の要素を取得してから上記のメソッドを使用するには、時間をかける必要があります）。そのようなリストではinsert、現在のイテレータの背後にアイテムを配置するのが一般的ですか？または-おそらくより良い-これには別の一般的な機能がありますか？

4

1 に答える 1

3

挿入の複雑さは、何をする必要があるかによって異なります。先行ノードがわかっている場合（実際には、先行ノードの「次のポインター」を変更するための適切なハンドルが必要です）、複雑さはO(1)です。挿入する場所を見つける必要がある場合、複雑さはO(n)です。

期待に関しては、insert()二重にリンクされたリストの場合と同じように動作することを期待しますが、これを達成できないことも認識しています。異なる時間計算量（先行ノードを見つけるため）または異なるイテレータが必要です。無効化セマンティクス（つまり、他のノードへのイテレータは無効化されます）。C ++ 2011クラステンプレートは別のインターフェイスに使用されたと思いstd::forward_listますが、イテレータの有効性の保証は保持されています。

イテレータの有効性が影響を受ける理由を簡単に説明すると、イテレータは現在のノードについてのみ知る必要はありません。代わりに、たとえば、前任者のnextポインタを指すことができます。イテレータを逆参照する場合、最初にそのポインタをポインタに逆参照しnext、次にこのポインタを逆参照して実際のノードを取得します。next見返りとして、イテレータは更新するポインタを知っているため、イテレータの前に挿入することができます。残念ながら、これは、イテレータが指すポインタが変更され、別のノードを参照するためにイテレータが無効になる可能性があることを意味します（ノードを消去するときに、参照されるノードがまだ存在していても、イテレータが完全に無効になるように移動された可能性があります）。

于 2012-12-08T20:22:12.863 に答える