二重にリンクされたリストはより多くのメモリを使用しますが、CPU は少なくなり、通常、単純なリンクされたリストと比較してアルゴリズムの複雑さが向上することを理解しています。
私が知りたいのは、二重にリンクされたリストと比較して、単純なリンクされたリストの方が全体的な結果が優れている場合です。どちらか一方を使用することが間違いなく最良の解決策である明確なポイント/状況はありますか? (通常の PC の x 要素の後のように)
私の特定の問題：
私は一般的な使用のためにリンクされたリスト構造を実装しており、要素の削除の複雑さを大幅に軽減するため、リンクバックを含める必要があるかどうかを考えています.
ありがとう。
アップデート：
単純なリンクされたリストで要素の削除が高くなりすぎるサイズはどれくらいですか?
データ構造を選択することは、コストと利益、通常は作業と維持を比較検討することです。
単独でリンクされたリストは、簡単なトラバーサルと簡単なフロント挿入を提供します。最後のノードを追跡することを犠牲にして、テールを簡単に挿入できます。そのコストは、ノードを追加/削除するたびに、追加のチェック (これはテールですか?) とリスト構造の可能な更新を行う必要があることを意味します。
双方向にリンクされたリストでは、メンテナンスのオーバーヘッドが大幅に増加します。すべてのノードは 2 つのポインターを格納する必要があり、それらを管理および維持する必要があります。
リストを後方に移動する必要がない場合は、単一リンク リストが理想的ですが、後方に移動できないということは、削除のコストが高くなることを意味します。
そのため、使用するパターンを決定することから始める必要があります。1 回限りのリストを作成する場合は、単独でリンクされたリストが理想的です。削除率の高い動的リストを作成する場合は、二重リンク リストの方が適しています。
データ構造が提供する特定の操作コストを決定することは、「 Big O Notation 」などのトピックです。
私が知りたいのは、二重にリンクされたリストと比較して、単純なリンクされたリストの方が全体的な結果が優れている場合です。
後戻りする必要がないとき。
一方向の線形検索を行っている場合、リストを他の方向にトラバースするインセンティブはなく、それらのポインターは必要ありません。
アップデート：
単純なリンクされたリストで要素の削除が高くなりすぎるサイズはどれくらいですか?
この問題は、リストが一重リンクか二重リンクかには関係ありません。リスト内の何かを削除する必要がある場合は、それを探す必要があります。これが時間の複雑さO(n)です。ここでは、前のノードへの追加のポインターは役に立ちません。
Linked List は、ほとんどの場合、スタックまたはキューを実装するために使用できるデータ構造です。一般的に言えば、スタックの挿入と削除を実装している場合は、片端で発生します。Q を使用する場合、通常、一方の端で削除し、もう一方の端で追加します。ご覧のとおり、これらの抽象 ds は両方とも二重リストを必要とせず、操作の追加と削除はアイテムの数に依存しません。上で Kepani が述べたように、リスト内の要素の数が心配になる唯一のケースは、スタック/Q インターフェイス (非線形アプローチ) で説明されていない方法で削除する場合です。これは、要素が順序付けられている場合 (もちろんそうでない場合もあります) であり、順序を維持する必要がある場合です。各ノードが「余分な」ポインタを維持する必要があるため、二重リストを使用することはメモリ要件にとって間違いなく困難です。過去の値も参照するストアを維持しようとしている場合を除きます。ここでは dlist が便利です (例: cli コマンド ライン インタープリター)。現在のノードの前の値に到達するために必要なトラバーサルは、リスト内の要素の数に依存するため、単一のリストでは時間がかかります。