リンクされたn個のノードのリストがあります。k番目のノードを削除し、その中に要素を表示します。これは、nの値が比較的小さく、問題の複雑さが問題でない場合は簡単です。リンクされたリストの10000番目のノードを削除する
問題は、n> = 200000のリンクされたリストにn個のノードがあり、比較的大きな値（たとえばk = 150000）のノードを削除したい場合です。
この問題の通常の解決策は、リンクリスト全体を横断してノードを削除することです（ソリューションの複雑さはO（n）です）。この問題の他の解決策は2つのポインタを持つことができますが、それでも最適な解決策ではありません。
私は、最適なソリューションを探しており、結果として最小限の時間で結果を提供します。
私の質問は明らかです。
あなたはアクセスがO（n）なので、 の2つの選択肢があります：コンテナを変更するか、セカンダリコンテナを使用して直接アクセスを高速化します（スペースの複雑さを増やす）。 。 すべての治療にO（1）の複雑さを持つ魔法の容器は見つかりません。
解決に感謝しますが、空間の複雑さを増やすことは、他の方法がない限り、私が感じたことではありません。 – sushh
'O（1）'ではなく 'O（log n）'を大幅に改善した 'skip-list'を使うことで' O（log n） 'を実現できます。 –
標準のリンクされたリストでは、その要素への唯一の参照がその直前の要素で発生するため、リストの後の要素にすばやくアクセスする方法はありません（追加のポインタはありません）。
インデックスが既知の要素に頻繁にアクセスする必要があることがわかっている場合は、配列を使用するほうがよいでしょう。 （質問を再読しても、これはまだ要素を削除するには良いことではありません）
解決策のMattに感謝します。しかし、私は少し疑いがある（私はそれをクリアしたいと思うが、私はそれをクリアしたいと思う）、私はリストの最初のノードのアドレスを持って、このアドレスを使用し、各ノードのサイズを知って、数学演算、リンクリストのk番目のノードのアドレスを知ることはできますか？ – sushh
と要素に直接アクセスしますか？ – sushh
@sushhいいえ、できません。これは、連続したメモリアドレスに要素を格納するコンテナでのみ実行できます。リストは、配列とは異なり、非連続メモリアドレスに格納されます。これは、削除操作を容易にし、後続要素を前方に移動させる必要がないため、リストのコストを大幅に削減します。 –
これは単なるインタビューの質問ですか、実際のシナリオがありますか？後であれば、あなたの支配下にあるもののような他のものについて、より多くの洞察を与えることができますか？ –
単独リンクされたリストをお持ちの場合、唯一の選択はO（n）ソリューションです。あなたは情報を追加するためにデータ構造を変更することが許されていますか？答えの1つによって示唆されるように、中間ノードへの参照のリストを維持するのと同じですか？ –