リンクリストを効率的に検索

Question

リンクリストを扱うCプログラミングクラスの割り当てがあります。

1つの関数は、ルートポインタとIdを取り、リストを検索して削除します。私はすでにこれらのIDに基づいてリンクリストをソートしました。

リンクリストを効率的に検索する方法はありますか？その割り当ては、彼らがより良い方法であることを強く示唆していますが、私はひどく非効率的でなくてはならない、または線形検索を使用することなく、それを行う方法を考えることはできません。

Answer 1

リンクされたリスト内の各ノードには、次のノード（およびオプションで前のノード）へのポインタしか含まれていないため、リストを検索する唯一の方法は線形です。

ただし、リストをソートするので、プロセスでバイナリツリーを構築できます。その後、そのツリーを使用してO(n)の代わりにO(log n)という時間の複雑さでリストを検索することができます。