c - リンクされたリストに要素が存在するかどうかを効率的に見つける

Question

情報を含むリンクされたリストがあると仮定します。My Program アーキテクチャは、このリンクされたリストの個々のノードに特定の情報が既に存在するかどうかを確認できることに基づいています。

(つまり、int exampleあるノードで子の整数値がすでに 5 の値を持っているかどうかを確認します。)

その後、各ノードを体系的に操作できます。

これを行うにはさまざまな方法が考えられますが、より経験豊富な人がかなり効率的な方法を示してくれることを期待していました。

また、これは良い習慣ですか、それとも別のより適切なデータ構造が存在する必要がありますか?

ありがとう！

Answer 1

O(N)では不十分な場合は、並べ替えられた配列とバイナリ検索、またはBSTで が得られますO(log(N))。あるいは、 hashmap data structureを見ることができます。この構造は、キーに基づいてほぼ一定時間のルックアップを提供しますが、他のオプションよりも複雑です。問題は、1 つの標準ライブラリ実装がないことです。

それ以外の場合は、各要素を検索することが、リンクされたリストで行うことができる最善の方法です。