リンクリストをソートする目的は何ですか？

Question

リンクされたリストをソートする目的が何であるか疑問に思っています。ソートされていないリンクリストとソートされたリンクリストで要素を見つける必要がある場合は、O（n）を実行する必要があるためです。 私の質問がばかだと許してください

Answer 1

ソートの目的は、必ずしも対数時間で検索するとは限りません。明らかにソートされたデータには他にもたくさんのアプリケーションがあります。

大きなリンクリストから重複した要素を削除する必要があり、リスト項目が非常に大きいため、リスト項目をハッシュテーブルに読み込むための十分な領域がないとします。この場合、リストをソートして、連続する要素が同じであればそれらを削除し、リストの重複を排除することができます。

ソートされたコンテナ内の適切な位置に要素を挿入する場合、ソートされたリンクリストは非常に便利で、線形の時間と一定の空間の複雑さを保証します。しかし、配列の場合は、一時配列を使用し、後ですべての要素を1つずつ移動する必要があります。 Infact LRUキャッシュは、フードの下に二重リンクされたリストであり、最近のヒットアイテムに基づいてソートされます。新しく使用されたアイテムと最近アクセスされた古いアイテムは、既にソートされたリストをソートした状態に保つために前面に挿入されます。構造体のような配列がここで使用される場合、LRUキャッシュは一定の複雑さを提供できません。

これは単なる古典的なアプリケーションの1つです。あなたは他の多くのアプリケーションを見つけることができます。

Answer 2

リンクリストを使用して優先キューを実装するとしましょう。異なる優先度の要素をランダムに追加できますが、優先度に従ってキューの要素を処理する必要があります。先頭に優先度の高い項目が表示されるようにソートされたリンクリストを維持し、キューは簡単な操作です。これは、リストを正確にソートするのではなく、アイテムが挿入されるときに、そのアイテムが優先順位に基づいて正しい位置に配置されるようになります。これは、配列の挿入ソートに似ています。