リンクされたリストのようなデータ構造は、実際のプログラミングにとって純粋に学術的なものですか、それとも実際に使用しますか? それらはジェネリックでカバーされているので、ビルドする必要はありません (言語にジェネリックがあると仮定して)。私はそれらが何であるかを理解することの重要性について議論しているわけではありません.学界の外でそれらを使用することだけです. フロントエンド Web、バックエンド データベースの観点からお尋ねします。誰かがどこかでこれらを構築していると確信しています。私は私の文脈から尋ねています。
ありがとうございました。
編集:リンクされたリストなどを作成する必要がないようにジェネリックですか?
使用している言語とフレームワークによって異なります。ほとんどの最新の言語とフレームワークでは、これらの車輪を再発明する必要はありません。代わりに、List<T>または HashTable などを提供します。
編集：
私たちはおそらくリンクされたリストを常に使用していますが、それを認識していません。リンク リストの実装を自分で記述する必要はありません。これは、使用するフレームワークが既にそれらを記述しているためです。
「ジェネリック」についても混乱しているかもしれません。のような一般的なリスト クラスを参照している可能性がありますList<T>。これは、非ジェネリック クラスの List とまったく同じですが、要素の型は常に ですT。リンクされたリストとして実装されている可能性がありますが、気にする必要はありません。
また、物理メモリの割り当て、割り込みの仕組み、ファイル システムの作成方法についても心配する必要はありません。それを行うためのオペレーティングシステムがあります。しかし、私たちは学校でも同じようにその情報を教えられるかもしれません。
そうです。現代の言語における多くの「リスト」実装は、実際にはリンクされたリストであり、直接アクセスするために (反復ではなくインデックスによって) 配列またはハッシュ テーブルと組み合わせられる場合があります。
連結リスト (特に二重連結リスト) は、「実際の」データ構造で非常に一般的に使用されます。
すべての一般的な言語には、言語プリミティブ、ネイティブ テンプレート ライブラリ (C++ など)、ネイティブ ライブラリ (Java など)、またはサード パーティの実装 (おそらくオープン ソース) のいずれかとして、事前に構築されたリンク リストの実装があるとあえて言います。
そうは言っても、複雑なデータ構造のインフラストラクチャ コードを作成する際に、リンク リストの実装をゼロから作成したことが過去に何度かありました。実装を完全に制御することをお勧めする場合もあれば、特定の要件を満たすために従来の実装に「ひねり」を加える必要がある場合もあります。代替案とトレードオフを理解している限り、独自の実装をコーディングするかどうかに関しては、正しいも間違いもありません。ほとんどの場合、そして確かに C# のような非常に近代的な言語では、私はそれを避けます。
もう 1 つのポイントは、リストと配列/ベクトルまたはハッシュ テーブルを使用する必要がある場合です。あなたの質問から、ここでのトレードオフを認識していることを理解しているので、あまり詳しく説明しませんが、基本的に、主な使用法がリストを順番にトラバースすることであり、リストのサイズが大幅に異なる場合、リストは実行可能なオプションになります。もう 1 つの考慮事項は、挿入の種類です。一般的なユースケースが「途中に挿入する」場合、リストは配列/ベクトルよりも大きな利点があります。私は続けることができますが、この情報は古典的なCSの本にあります:)
明確化：私の答えは言語にとらわれず、私の理解ではリンクリストの実装を持つジェネリックには特に関係ありません。
単一リンクリストは、それを「変更」するように構成できるメモリ効率の高い不変リストを作成する唯一の方法です。Erlangがどのようにそれを行うかを見てください。配列に基づくリストよりも少し遅いかもしれませんが、マルチスレッドで純粋関数型の実装では非常に便利なプロパティがあります。
はい、リンクリストを使用する実際のアプリケーションがあります。リンクリストを非常に活用する巨大なアプリケーションを維持する必要がある場合があります。
そして、はい、リンクリストはC ++/STLから.netまでのほぼすべてのクラスライブラリに含まれています。
そして、代わりに配列を使用したいと思います。
現実の世界では、リンクリストはページングやCPUキャッシュサイズなどの理由で低速です（リンクリストはデータを拡散する傾向があり、メモリのさまざまな領域からデータにアクセスする必要がある可能性が高くなり、今日でははるかに遅くなりますすべてのデータを1つのシーケンスに格納するアレイを使用するよりもコンピュータ）。
詳細については、Googleの「参照の局所性」を参照してください。
大学での宿題を除いて、手作りのリストを使用したことはありません。
使用状況によっては、リンクされたリストが最適なオプションになる場合があります。リストの先頭からの削除は、配列リストよりも連結リストの方がはるかに高速です。
私が管理している Java プログラムのプロファイリングでは、最初に多くの削除があった List を ArrayList から LinkedList に移動することで、パフォーマンスを向上できることが示されました。
はい、あらゆる種類のデータ構造は、日常のソフトウェア開発に非常に役立ちます。私が知っているほとんどの言語 (C/C++/Python/Objective-C) には、それらのデータ構造を実装するフレームワークがあり、車輪を再発明する必要はありません。
はい、データ構造は学者だけのものではなく、非常に便利であり、それらなしではソフトウェアを作成することはできません (何をするかによって異なります)。
メッセージキュー、データマップ、ハッシュテーブルでデータ構造を使用し、データの順序を維持し、高速アクセス/削除/挿入などを行う必要があるかによって異なります。
はい、そうです。それはすべて状況に依存します。それらに大量のデータを保存しない場合、または特定のアプリケーションで FIFO 構造が必要な場合は、実装が高速であるため、何も考えずに使用します。
ただし、私が知っている他の開発者向けのアプリケーションでは、リンクされたリストが完全に適合する場合があります。
リストを扱わないプログラムがたくさんあるとは想像できません。何かの複数のものを処理する必要がある分、これらのものを保管する場所が必要になるため、すべての形式と形状のリストが必要になります。そのリストは、一重/二重にリンクされたリスト、配列、セット、キーに基づいてインデックスを作成する必要がある場合はハッシュテーブル、並べ替える必要がある場合は優先キューなどです。
通常、これらのリストはデータベース システムに保存しますが、データベースから取得し、アプリケーションに保存して操作する必要がある場所に保存します。ダウンコンボボックス。
最近では、C#、Python、Java などの言語では、通常、独自のリストを実装する必要がなくなります。これらの言語には、標準ライブラリを介して、または言語に組み込まれたものを格納できるコンテナの抽象化が多数付属しています。
これらのトピックを学習する利点はまだあります。たとえば、C# を使用している場合は、ArrayList がどのように機能するかを知りたいと思います。リストなどの検索/ランダム インデックス。
私は何年もの間、基幹業務アプリケーション (.NET) を開発してきましたが、リンク リストを使用したことがあり、その場合でもオブジェクトを作成する必要がなかったインスタンスは 1 つしか思い浮かびません。
これは私の経験です。
用途にもよると思いますが、場合によっては、通常のランダム アクセス コンテナーよりも高速です。
また、一部のライブラリで基になるコレクション型として使用されていると思うので、リンクされていないリストのように見えるものは、実際にはその下にある可能性があります。
前の会社で開発した C/C++ アプリケーションでは、常に二重リンク リストを使用していました。それらは、リアルタイム 3D グラフィックスである私たちが行っていたことに不可欠でした。