順序付きリストと順序付けられていないリンクリストの検索

Question

私は最終的なプロジェクトに取り組んでいるプログラムで、順序付きリストと順序付けられていないリンクリストの検索機能を実装する必要があります。課題では、各タイプの検索機能が期待されていることが明らかになりました。

私は以前のクラスでリンクされたリストを使っていましたが、順序付けと順序付けの違いを理解していますが、その違いを調べる際に壁を打ちました。私の考えでは、キー値が見つかるまでリストを繰り返して、それを返すべきです。これらはどうやって違いますか？

Answer 1

リンク先リストの場合、検索操作中に時間の複雑さを減らすことができます。この目的でskip listを実装できます。しかし、あなたのリンクされたリストが単独でリンクされたリストである必要がある場合、厳密には@kaylumのコメントに他の違いはありません