c# - リンクされたリストを使用する必要がある場合の実際の例は何ですか?

Question

別のプログラマーは、彼のキャリアの中で、リンクされたリストのデータ構造を使用するプロ用ソフトウェアのユースケースを見つけられなかったと述べていました。頭のてっぺんから良い例が思い浮かびませんでした。彼は主に C# と Java の開発者です。

これが特定の現実世界の問題を解決するための正しいデータ構造である例を誰か挙げることができますか?

関連: Linked List の実用的で現実的な例は何ですか?

score 24 · Accepted Answer

リンクされたリストには、静的または動的に拡張される配列などの同等のデータ構造に比べていくつかの利点があります。

LinkedLists はメモリの連続したブロックを必要としないため、メモリの断片化を減らすのに役立ちます
LinkedLists は要素の効率的な削除をサポートします (動的配列は通常、すべての要素のシフトを強制します)。
LinkedLists は要素の効率的な追加をサポートします (特定の追加が現在の容量を超えた場合、動的配列は再割り当て + コピーを引き起こす可能性があります)

これらの利点がプログラムにとって非常に価値がある (そして LinkedList の欠点が無視できる) 場所は、LinkedList を使用する場所です。

score 21 · Accepted Answer

実際の例はFIFOキューです。単純な配列ベースのリストは、一方の端で追加し、もう一方の端で削除する必要があるため、かなり悪いです。これらの操作の1つは、配列ベースのリストでO（n）になります（追加のロジックを追加しない限り）。開始インデックスと終了インデックスで動作します）、どちらもO（1）であり、余分な労力をかけずにリンクリストを使用します。

score 17 · Accepted Answer

煩わしいリンクリストは、ゲーム開発にとって興味深い獣です。たとえば、煩わしい単一または二重にリンクされた「レンダリング」リストを作成することは、やや一般的な方法です。

class Renderable /*またはclassObject、何でも* /
{{
  //..。
  レンダリング可能*m_pNext;
  レンダリング可能*m_pPrev; //単独でリンクされている場合は、そうでない
  //..。
}

Renderableが存在するようになるか、存在しなくなると、メモリ割り当てを発生させることなく、このリストに自分自身を登録できます。レンダリングの深さや優先度が変更された場合は、自分自身を削除して再挿入することができます。

レンダリングするときは、リストの先頭を見つけて、適切なメソッドを呼び出して圧縮するだけです。

（もちろん、このテーマには多くのバリエーションがあり、複数の個別のリストなどがあります。この作業を行うために煩わしいリストは必要ありません。邪魔なリストが面白いと思います。）

score 15 · Accepted Answer

リンクリスト（ハッシュテーブルとペアになっている）は、 LRUキャッシュに非常に役立ちます。

すべてのGetは、ノードをリストの先頭に配置する必要があります。これは、リンクリストを使用すると非常に安価な操作です。

score 7 · Accepted Answer

スタックとキューはリンクリストの非常に明確な例ですが、他の人がすでに言及しているように、他のいくつかの例を追加したいと思います。

DOMはノードをリンクリストとして保存します。どの言語でも実際に同じである単純なjavascriptサンプル：

for (var node = parent.firstChild; node != null; node = node.nextSibling) {
    // ..
}

Java開発者はある時点でXMLに出くわしたと思います。

ツリーは、単純な1次元のものではありませんが、リンクリストのもう1つの良い例です。多くのJava開発を行った人は、おそらくTreeMapsとTreeSetsに出くわしたことがあります。

全体の議論は私には少しばかげているようです。リンクリストは、あらゆる場所で使用される基本的なデータ構造です。彼/彼女がそれらに出くわしていないと思うかもしれない唯一の理由は、今日の高級言語でのデータ構造の実装について本当に心配する必要がないということですが、もちろんそれらはまだそこにあります。

score 6 · Accepted Answer

それらは、オブジェクトが同じタイプの別のオブジェクトを指すプロパティを持っている場所ならどこでも、常に発生します。CLRでは、プロパティが原因で、例外がリンクリストを形成しInnerExceptionます。

score 5 · Accepted Answer

不変のリンクされたリストは、同じテールを持つ他のリストと「構造を共有」できるため、非常に価値のある構造です。ほとんどの関数型言語には、基本的なデータ構造の 1 つとして不変の連結リスト型が含まれており、これらの型はいたるところで使用されています。

score 4 · Accepted Answer

私は、USB ホストコントローラ用の BIOS 拡張機能 (基本的には、アセンブリで記述された BIOS 用のデバイスドライバ) を作成しました。-- リンクされたリストのような高レベルの一見抽象的なデータ構造をアセンブリに実装することは、思ったほど難しくありません。-- コントローラは、メインメモリ内のパケットのリンクリストを使用して、キーボードとディスクの I/O 要求を処理していました。別のリンクされたリストに空きパケットのプールを維持しました。I/O の実行には、基本的に、フリーリストの先頭からフリーパケットを取得し、パケットを構成し、パケットをデバイスのリストに追加し、I/O が終了したときにパケットをフリープールの先頭に再度追加する必要がありました。リンクされたリストは、オブジェクトが実際に移動する必要がないため、特にオブジェクトが大きい場合、このようなオブジェクトの周りを移動するのに非常に高速です。それらのポインターのみを更新する必要があります。

配列ベースのキューには次のものが必要です。

開始/終了インデックスポインターを使用します。これは高速ですが、キューのサイズを修正して、コンシューマーのキューがいっぱいになったときにプロデューサーが待機する必要があり、複数のプロデューサーが存在する場合はパケット全体がいっぱいになるまでキューをロックする必要があります。
挿入/削除するたびにキュー内のすべての要素をシフトします。これは、大きなオブジェクトの場合は遅くなります

したがって、連結リストは、大きなオブジェクトの任意の長さの先入れ先出しキューを実装するための優れた方法です。

注意すべきもう 1 つの点は、小さいオブジェクトの場合、またはカスタムフリープールの代わりに従来のヒープからオブジェクトを割り当てる場合、配列の方が高速になる可能性があるということです。新しい要素が追加されるたびにリンクされたリストが必要とするヒープからは遅いです。

もちろん、答えを見つけるために、使い捨てのテストコードを使用して特定のシナリオをシミュレートおよび測定することもできます。私は、リンクされたリストと配列を使用して数百万回ループを実行し、小さなオブジェクトと大きなオブジェクトを使用して、それぞれにかかる時間をリアルタイムで測定するのが好きです。驚かれることもあります。

score 3 · Accepted Answer

.Netでおそらく最良の実例として、MultiCastDelegateを検討してください。

このように実装されたリンクリストは、リストチェーンの側面が個別のコンテナーとしてではなく、タイプに直接バックアップされるため、非常に強力で効率的です。ただし、さまざまなトレードオフがあります。
明らかなものの1つはコードの重複です。このロジックは、各タイプでベイク処理する必要があります。ポインターを提供する基本クラスを拡張するなどの手法は厄介であり（ジェネリックスがないと強い型付けを失う）、パフォーマンスの観点から受け入れられないことがよくあります。
もう1つは、タイプごとに1つの実装に制限されていることです。すべてのインスタンスに追加のフィールドを挿入し、関連するすべてのコードを更新しない限り、単一リンク構造を二重リンク構造にすることはできません。

score 2 · Accepted Answer

すでに述べたように、要素を挿入および削除する必要がある場合は、すでにリンクされたリストが非常に役立ちます。

たとえば、コードでメモリ管理をデバッグするために、最近、参照数がカウントされたすべてのオブジェクト間にリンクリストを実装して、プログラムの最後に（参照がすべてゼロになり、オブジェクトが削除されたときに）正確に何であるかを確認できるようにしました。まだ残っていますが、通常、問題の根本にある単一のオブジェクトを見つけることができます。

CPythonは、デバッグを使用して構築された場合、ほぼすべての間に大規模なリンクリストを備えた類似の何かを実装します。

score 2 · Accepted Answer

タグ「データ構造」に答えると、アセンブリなどの低レベルで、リンクされたリストは、他のデータ構造の可変長リストを格納する理想的な方法です。リストの長さや終了を維持するためのオーバーヘッドはなく、固定サイズのリスト項目も必要ありません。最後の理由は、高水準言語にも当てはまります。

score 2 · Accepted Answer

連結リストはDancing Linksの重要なデータ構造です。これは Algorithm Xを効率的に実装するために使用される手法です。これは、多くの困難な問題が自然に還元できるNP 完全完全カバー問題のすべての解を見つけるためのバックトラッキングアルゴリズムです。

score 1 · Accepted Answer

daustin777 が指摘するように、リンクされたリストはあなたの周りにあり、あなたはそれを知らないかもしれません. しかし、問題の実用性は、かなり基本的な操作を比較的簡単かつ柔軟に実行できるようにすることです。たとえば、並べ替えではなく、ポインターを交換するだけです。任意の場所に挿入または削除する必要がありますか? リスト内でポインターを挿入または削除します。前後に反復する必要があります... リンクされたリスト。正確にはビジネスの例ではありませんが、これが十分に明確になり、実際のビジネスケースに適用できることを願っています。

score 1 · Accepted Answer

この質問に他の人たちとは少し違う答え方をするとしたら、最近はリンク付きリストを使って音楽リストを整理しています。リストは、アーティスト、曲、アルバム、さらには評価や曲の長さで音楽を保存およびソートするための優れた方法を提供します。私のは二重リンクリストですが、片リンクリストにも適用できることがわかりました。買い物リストもぴったりです。もしあなたが私のお母さんのように OCD なら、通路や冷凍食品を最後に簡単に整理できます。

スタックとキューを含めると、明らかにキューは印刷キューまたは音楽プレイリストです (リストはあらゆる意味で明らかに優れています)。

score 0 · Accepted Answer

0

スタックとキューは、リンクされたリストの例です。

于 2009-03-21T22:21:05.270 に答える

score 0 · Accepted Answer

最大ノード数が 100 またはそれ以下に制限されている問題の場合、リンクリストは合理的な解決策です。同じことは、バブルソートなど、最適ではないと考えられるものにも当てはまります。

score -1 · Accepted Answer

リンクリストの長所：

動的ストレージは断片化を無効にします
素早い挿入/取り外し
最初の要素への高速アクセス (および双方向で実装されている場合は終了)
効率的なメモリ使用

リンクリストの短所：

スロートラバース

私の頭から、リンクされたリストを使用してスタック、キュー、およびメッセージポンプを実装したいと思います。また、高速な挿入/削除のために、複数参照リンクリストを使用してデータツリーを実装します。

c# - リンクされたリストを使用する必要がある場合の実際の例は何ですか?

18 に答える 18

Related

Reference