ビジネスプログラミングで、リンクリスト、二重リンクリストなどを使用していますか？

Question

リンクリストのようなデータ構造は、実際のプログラミングでは純粋に学術的なものですか、それとも実際に使用していますか？それらはジェネリックでカバーされているので、それらをビルドする必要はありません（あなたの言語にジェネリックがあると仮定して）？私はそれらが何であるかを理解することの重要性について議論しているのではなく、アカデミア以外でのそれらの使い方だけです。フロントエンドWeb、バックエンドデータベースの観点からお願いします。誰かがこれらを構築していると確信しています。コンテキストから質問しています。

ありがとう。

編集：ジェネリックはリンクリストなどを作成する必要がないようになっていますか？

Answer 1

使用している言語とフレームワークに依存します。最新の言語とフレームワークでは、これらの車輪を再発明することはできません。代わりに、List<T>やHashTableのようなものを提供します。

編集：

おそらくリンクリストを常に使用しますが、気付いていません。リンクリストの実装を独自に作成する必要はありません。使用するフレームワークによって既に作成されているためです。

<！> quot; generics <！> quot;についても混乱しているかもしれません。 Tなどの汎用リストクラスを参照している可能性があります。これは、非ジェネリッククラスListとまったく同じですが、要素は常にタイプ<=>です。おそらくリンクリストとして実装されますが、気にする必要はありません。

また、物理メモリの割り当て、割り込みの仕組み、ファイルシステムの作成方法について心配する必要もありません。それを行うオペレーティングシステムがあります。しかし、学校でも同じように教えられるかもしれません。

Answer 2

確かに。多くの<！> quot; List <！> quot;現代の言語の実装は、実際にはリンクされたリストであり、直接アクセスするための配列またはハッシュテーブルと組み合わせられる場合もあります（反復ではなくインデックスによる）。

リンクリスト（特に二重リンクリスト）は、<！> quot; real-world <！> quot;で非常によく使用されます。データ構造。

すべての共通言語には、言語リスト、ネイティブテンプレートライブラリ（C ++など）、ネイティブライブラリ（Javaなど）、またはサードパーティの実装（おそらくオープン-ソース）。

そうは言っても、過去に何度か、複雑なデータ構造のインフラストラクチャコードを作成するときに、リンクリストの実装をゼロから作成しました。実装を完全に制御することをお勧めします。また、<！> quot; twist <！> quot;を追加する必要があります。特定の要件を満たすための従来の実装に。代替手段とトレードオフを理解している限り、独自の実装をコーディングするかどうかについては、正しいことも間違ったこともありません。ほとんどの場合、そして確かにC＃のような非常に現代的な言語では、私はそれを避けます。

もう1つのポイントは、リストと配列/ベクターまたはハッシュテーブルを使用する必要がある場合です。あなたの質問から、あなたはここでトレードオフを知っているので、私はそれにあまり入りませんが、基本的に、あなたの主な使用法がリストを順番に走査し、リストのサイズが大幅に異なる場合、リストは実行可能なオプションである。もう1つの考慮事項は、挿入のタイプです。一般的なユースケースが<！> quot;中央に挿入する<！> quot;の場合、リストには配列/ベクトルよりも大きな利点があります。続行できますが、この情報は古典的なCSブックにあります：）

明確化：私の答えは言語に依存せず、リンクリストの実装を持っているジェネリックとは特に関係ありません。

Answer 3

単一リンクリストは、<！> quot; mutate <！> quot;に構成できる、メモリ効率の高い不変リストを持つ唯一の方法です。それ。 Erlangの仕組みをご覧ください。配列に対応したリストよりも若干遅いかもしれませんが、マルチスレッドで純粋に機能する実装では非常に有用なプロパティがあります。

Answer 4

はい、リンクリストを使用する現実のアプリケーションがあります。リンクリストを非常に使用する巨大なアプリケーションを維持する必要がある場合があります。

そして、はい、リンクリストはC ++ / STLから.netまでのほぼすべてのクラスライブラリに含まれています。

そして、代わりに配列を使用したいです。

実際には、リンクリストはページングやCPUキャッシュサイズなどの理由で低速です（リンクリストはデータを拡散する傾向があるため、メモリのさまざまな領域からデータにアクセスする必要がある可能性が高くなります今日のコンピューターでは、すべてのデータを1つのシーケンスで保存するアレイを使用するよりも遅くなります。

Google <！> quot;参照の局所性<！> quot;詳細については。

Answer 5

大学の宿題を除き、手作りのリストを使用したことはありません。

Answer 6

使用法によっては、リンクリストが最適なオプションになる場合があります。リストの先頭からの削除は、配列リストよりもリンクリストの方がはるかに高速です。

プロファイリングを維持しているJavaプログラムでは、最初に多くの削除があったリストのArrayListからLinkedListに移動することでパフォーマンスを向上できることが示されました。

Answer 7

私は長年にわたって基幹業務アプリケーション（.NET）を開発してきましたが、リンクリストを使用した1つのインスタンスしか考えられず、その場合でもオブジェクトを作成する必要はありませんでした。

これは私の経験です。

Answer 8

使用方法に依存すると思いますが、場合によっては通常のランダムアクセスコンテナよりも高速です。

また、一部のライブラリでは基本的なコレクション型として使用されていると思うので、リンクされていないリストのように見えるものは、実際には下のリストになります。

Answer 9

最後の会社で開発したC / C ++アプリケーションでは、常に二重リンクリストを使用していました。これらは、リアルタイム3Dグラフィックスである私たちがやっていることに不可欠でした。

Answer 10

はい、あらゆる種類のデータ構造は、毎日のソフトウェア開発に非常に役立ちます。私が知っているほとんどの言語（C / C ++ / Python / Objective-C）には、これらのデータ構造を実装するフレームワークがあり、車輪を再発明する必要はありません。

そして、はい、データ構造は学者だけのものではなく、非常に便利であり、あなたはそれらなしではソフトウェアを書くことができません（あなたが何をするかに依存します）。

メッセージキュー、データマップ、ハッシュテーブルでデータ構造を使用し、データの順序を維持し、高速アクセス/削除/挿入などを行う必要があります。

Answer 11

はい、できます。それはすべて状況に依存します。大量のデータを保存しない場合、または特定のアプリケーションがFIFO構造を必要とする場合は、実装が高速であるため、何も考えずに使用します。

ただし、私が知っている他の開発者向けのアプリケーションでは、貧弱なローカリティが多くのキャッシュミスを引き起こすことを除いて、リンクリストが完全に適合する場合があります。

Answer 12

リストを処理しない多くのプログラムは想像できません。 あなたが何かの1つ以上のものを扱う必要がある分、あなたはこれらのものを保存するためにどこかを必要とするので、すべてのフォームと形状のリストが必要になります。そのリストは、単一/二重にリンクされたリスト、配列、セット、キーに基づいて物事にインデックスを付ける必要がある場合はハッシュテーブル、ソートする必要がある場合は優先度キューなどです。

通常、これらのリストはデータベースシステムに保存しますが、どこかでデータベースからフェッチし、アプリケーションに保存して操作する必要があります。ドロップダウンコンボボックス。

最近では、C＃、Python、Javaなどの言語では、通常、独自のリストを実装する必要がなくなります。これらの言語には、ものを格納できるコンテナの多くの抽象化が付属しています。標準ライブラリを介して、または言語に組み込まれています。

これらのトピックを学ぶ利点はまだあります。 C＃で作業している場合は、ArrayListの仕組みを知りたいのですが、そのようなリストを追加/挿入/検索/ランダムインデックスする必要に応じて、ArrayListまたは他の何かを選択します。