配列に対してリンクリストを使用したいのはなぜですか?
リンクリストのコーディングは、間違いなく、配列を使用するよりも少し手間がかかり、追加の作業を正当化するものは何か疑問に思うかもしれません。
リンクリストでは新しい要素の挿入は簡単だと思いますが、配列では大変な作業です。リンクされたリストを使用して一連のデータを格納することと、配列に格納することには他に利点がありますか?
この質問は一般的なデータ構造に関係しているのに対し、他の質問は特定のJavaクラスについて具体的に尋ねているため、この質問はこの質問の複製ではありません。
もう1つの理由は、リンクリストが効率的なマルチスレッド実装に適していることです。この理由は、変更がローカルになる傾向があるためです。データ構造のローカライズされた部分での挿入と削除のポインターに影響を与えるのは1つか2つだけです。したがって、同じリンクリストで多くのスレッドを動作させることができます。さらに、CASタイプの操作を使用してロックフリーバージョンを作成し、重いロックを完全に回避することができます。
リンクリストを使用すると、変更が行われている間、イテレータはリストをトラバースすることもできます。変更が衝突しない楽観的なケースでは、イテレータは競合することなく続行できます。
アレイの場合、アレイのサイズを変更する変更を行うと、アレイの大部分をロックする必要が生じる可能性があります。実際、アレイ全体でグローバルロックを使用せずにこれを行うことはめったにないため、変更によって世界の問題が停止します。
ウィキペディアには、違いについて非常に優れたセクションがあります。
リンクリストには、配列に比べていくつかの利点があります。要素はリンクリストに無期限に挿入できますが、配列は最終的にいっぱいになるか、サイズを変更する必要があります。これは、メモリが断片化されている場合でも不可能な、コストのかかる操作です。同様に、多くの要素が削除された配列は、無駄に空になるか、小さくする必要があります。
一方、配列はランダムアクセスを許可しますが、リンクリストは要素への順次アクセスのみを許可します。実際、単一リンクリストは一方向にしかトラバースできません。これにより、リンクリストは、ヒープソートなど、インデックスで要素をすばやく検索するのに役立つアプリケーションには適していません。配列へのシーケンシャルアクセスは、参照とデータキャッシュの局所性により、多くのマシンのリンクリストよりも高速です。リンクリストは、キャッシュの恩恵をほとんど受けません。
リンクリストのもう1つの欠点は、参照に必要な追加のストレージです。これにより、文字やブール値などの小さなデータ項目のリストでは実用的でないことがよくあります。また、新しい要素ごとに個別にメモリを割り当てるのは遅く、ナイーブなアロケータを使用すると無駄になる可能性があります。この問題は、一般にメモリプールを使用して解決されます。
もう 1 つ追加します。リストは純粋に機能的なデータ構造として機能します。
たとえば、同じ終了セクションを共有する完全に異なるリストを持つことができます
a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)
すなわち:
b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next
aが指すデータをbとにコピーする必要はありませんc。
これが、不変変数を使用する関数型言語で非常に人気がある理由ですprepend。tail元のデータをコピーすることなく操作を自由に行うことができます。これは、データを不変として扱う場合に非常に重要な機能です。
リストの途中に挿入するのが簡単であることに加えて、配列よりもリンクされたリストの途中から削除する方がはるかに簡単です。
しかし、率直に言って、私はリンクされたリストを使用したことがありません。高速な挿入と削除が必要なときはいつでも、高速なルックアップも必要だったので、HashSet または Dictionary に行きました。
2つのリンクリスト（特に2つの二重リンクリスト）をマージする方が、2つの配列をマージするよりもはるかに高速です（マージが破壊的であると想定）。前者はO（1）を取り、後者はO（n）を取ります。
編集：明確にするために、私はここで、マージソートのようにではなく、順序付けられていない意味で「マージ」することを意味しました。おそらく「連結」という言葉の方がいいでしょう。
ArrayList を支持し、LinkedList に反対する議論として広く認められていないのは、デバッグ中に LinkedList が不快であるということです。メンテナンス開発者がバグを見つけるなど、プログラムを理解するのに費やす時間は増加し、IMHO では、エンタープライズ アプリケーションでのパフォーマンスの向上におけるナノ秒やメモリ消費のバイト数を正当化できない場合があります。場合によっては (もちろん、アプリケーションの種類によって異なります)、数バイトを無駄にする方がよい場合もありますが、より保守しやすく、理解しやすいアプリケーションを使用することをお勧めします。
たとえば、Java 環境で Eclipse デバッガーを使用して ArrayList をデバッグすると、非常に理解しやすい構造が明らかになります。
arrayList ArrayList<String>
elementData Object[]
[0] Object "Foo"
[1] Object "Foo"
[2] Object "Foo"
[3] Object "Foo"
[4] Object "Foo"
...
一方、LinkedList のコンテンツを監視して特定のオブジェクトを見つけることは、LinkedList 内部を除外するために必要な認知オーバーヘッドは言うまでもなく、Expand-The-Tree をクリックする悪夢になります。
linkedList LinkedList<String>
header LinkedList$Entry<E>
element E
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
previous LinkedList$Entry<E>
...
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
まず第一に、C ++では、リンクリストは配列よりも操作するのにそれほど問題はないはずです。リンクリストには、 std::listまたはブーストポインタリストを使用できます。リンクリストと配列の主な問題は、ポインタとひどいランダムアクセスに必要な余分なスペースです。次の場合はリンクリストを使用する必要があります
私の場合はこんな感じです、
アクセス
保管所
サイズ
挿入・削除
2つのこと：
リンクリストのコーディングは、間違いなく、配列を使用するよりも少し手間がかかり、彼は追加の作業を正当化するものは何かと考えました。
C ++を使用する場合は、リンクリストをコーディングしないでください。STLを使用するだけです。ほとんどがすでに実装されているため、実装がどれほど難しいかが、あるデータ構造を別のデータ構造よりも選択する理由になることはありません。
配列とリンクリストの実際の違いについては、私にとって重要なのは、構造の使用をどのように計画するかです。ベクトルという用語を使用します。これは、C++でサイズ変更可能な配列を表す用語だからです。
リンクリストへのインデックス作成は、指定されたインデックスに到達するためにリストをトラバースする必要があるため低速ですが、ベクトルはメモリ内で連続しており、ポインタ演算を使用してそこに到達できます。
リンクリストの最後または最初に追加するのは簡単です。更新する必要があるのは1つのリンクだけであり、ベクターではコンテンツのサイズを変更してコピーする必要がある場合があります。
リストからアイテムを削除するのは簡単です。リンクのペアを壊してから、それらを元に戻すだけだからです。ベクトルからのアイテムの削除は、順序を気にするかどうかに応じて、速くなることも遅くなることもあります。削除したいアイテムの上に最後のアイテムを入れ替えると速くなりますが、下に移動した後にすべてをシフトすると遅くなりますが、順序は維持されます。
Eric Lippert は最近、配列を慎重に使用する必要がある理由の 1 つについて投稿しました。
迅速な挿入と削除は、リンクリストの最良の議論です。構造が動的に成長し、要素（動的スタックやキューなど）への一定時間のアクセスが必要ない場合は、リンクリストが適しています。
もはや誰も自分のリンクリストをコーディングすることはありません。それはばかげているでしょう。リンクリストを使用するとより多くのコードが必要になるという前提は間違っています。
最近では、リンクリストを作成することは、学生が概念を理解できるようにするための単なる演習です。代わりに、誰もが事前に作成されたリストを使用します。C ++では、質問の説明に基づいて、それはおそらくstlベクトル（#include <vector>）を意味します。
したがって、リンクリストと配列のどちらを選択するかは、アプリのニーズに関連して各構造のさまざまな特性を比較検討することです。追加のプログラミングの負担を克服しても、決定に影響はありません。
配列とリンクリスト：
リストの中央から追加および削除する以外に、リンクリストは動的に拡大および縮小できるため、リンクリストの方が好きです。
リンクリストは、コレクションが絶えず拡大および縮小している場合に特に役立ちます。たとえば、配列を使用してキューを実装しようとする（最後に追加し、前面から削除する）ことを想像するのは難しいです-あなたは物事をシフトダウンすることにすべての時間を費やしているでしょう。一方、リンクリストでは簡単です。
ここに簡単なものがあります。アイテムの削除はより迅速です。
これは実際には効率の問題です。リンクリスト内の要素を挿入、削除、または移動するためのオーバーヘッドは最小限です。つまり、操作自体はO（1）であり、配列の場合はO（n）です。データのリストを頻繁に操作している場合、これは大きな違いを生む可能性があります。データ型は、それらをどのように操作するかに基づいて選択し、使用しているアルゴリズムに最も効率的なものを選択します。
配列は、アイテムの正確な数がわかる場所、およびインデックスによる検索が意味をなす場所に意味があります。たとえば、圧縮せずに特定の瞬間のビデオ出力の正確な状態を保存したい場合は、おそらくサイズ[1024][768]の配列を使用します。これにより、必要なものが正確に提供され、特定のピクセルの値を取得するためのリストの速度が大幅に低下します。配列が意味をなさない場所では、データを効果的に処理するために、一般的にリストよりも優れたデータ型があります。
配列では、O(1) 時間で任意の要素にアクセスできる特権があります。したがって、二分探索クイックソートなどの操作に適しています。一方、連結リストは O(1) 時間であるため、挿入削除に適しています。どちらにも長所と短所があり、どちらを優先するかは、実装したいものに要約されます。
-- より大きな問題は、両方のハイブリッドを持つことができるかということです。python と perl がリストとして実装するもののようなもの。
リンクされたリストは、配列よりも維持するためのオーバーヘッドが多く、追加のメモリストレージも必要です。これらすべての点が合意されています。しかし、配列ができないことがいくつかあります。多くの場合、長さ 10^9 の配列が必要であると仮定すると、1 つの連続したメモリ ロケーションを取得する必要があるため取得できません。リンクされたリストは、ここで救世主になる可能性があります.
複数のものをデータとともに保存したい場合、それらはリンクされたリストで簡単に拡張できます。
通常、STL コンテナには、バックグラウンドでリンク リストが実装されています。
1-リンクされたリストは動的なデータ構造であるため、メモリの割り当てと割り当て解除によって実行時に拡大および縮小できます。したがって、リンク リストの初期サイズを指定する必要はありません。ノードの挿入と削除は非常に簡単です。
2-リンクされたリストのサイズは実行時に増減できるため、メモリの浪費はありません。配列の場合、サイズ 10 の配列を宣言し、そこに 6 つの要素のみを格納すると、4 つの要素のスペースが無駄になるように、多くのメモリが浪費されます。リンクされたリストには、必要なときにのみメモリが割り当てられるため、このような問題はありません。
3-スタックやキューなどのデータ構造は、リンク リストを使用して簡単に実装できます。
配列は本質的に静的であるため、メモリ割り当てなどのすべての操作はコンパイル時にのみ発生します。そのため、プロセッサーは実行時の労力を軽減する必要があります。
順序付けられたセットがあり、要素を追加および削除して変更したいとします。さらに、後で前または次の要素を取得できるように、要素への参照を保持する機能が必要です。たとえば、書籍の To Do リストや一連の段落です。
最初に、セット自体の外部にあるオブジェクトへの参照を保持したい場合は、オブジェクト自体を格納するのではなく、ポインターを配列に格納することになる可能性が高いことに注意してください。そうしないと、配列に挿入できません。オブジェクトが配列に埋め込まれている場合、オブジェクトは挿入中に移動し、それらへのポインターは無効になります。配列インデックスについても同様です。
あなたが指摘したように、あなたの最初の問題は挿入です - リンクされたリストは O(1) に挿入できますが、配列は通常 O(n) を必要とします。この問題は部分的に克服できます。読み取りと書き込みの両方が最悪でも対数的である、配列のような序数によるアクセス インターフェイスを提供するデータ構造を作成することは可能です。
2番目のより深刻な問題は、次の要素を見つける要素がO(n)であることです。セットが変更されていない場合は、要素のインデックスをポインターの代わりに参照として保持できるため、find-next を O(1) 操作にすることができますが、オブジェクト自体へのポインターしかないため、方法はありません。 「配列」全体をスキャンする以外に、配列内の現在のインデックスを決定します。これは配列にとって克服できない問題です。挿入を最適化できたとしても、find-next 型操作を最適化するためにできることは何もありません。
リンクリストを使用する唯一の理由は、要素の挿入が簡単である（削除も）ということです。
不利な点は、ポインタが多くのスペースを占めることである可能性があります。
そして、そのコーディングはより困難です。通常、コードリンクリストは必要ありません（または1回だけ）。それらは STLに含まれ ており、それでも実行する必要がある場合はそれほど複雑ではありません。
言語によっては、これらの短所と長所のいくつかを考慮することができます。
Cプログラミング言語：リンクリストを使用する場合（通常は構造体ポインターを使用）、メモリリークが発生していないことを特に考慮する必要があります。先に述べたように、リンクリストはポインタを変更するだけなので、簡単にシャッフルできますが、すべてを解放することを忘れないでください。
Java：Javaには自動ガベージコレクションがあるため、メモリリークは問題になりませんが、高レベルのプログラマーには、リンクリストとは何かの実装の詳細が隠されています。リストの中央からノードを削除するなどの方法は、言語の一部のユーザーが期待するよりも手順が複雑です。
また、リンク リストは配列よりも優れていると思います。配列ではなくリンクリストでトラバースするため
なぜ配列上の連結リストなのですか? すでに述べたように、挿入と削除の速度が向上しました。
しかし、おそらく、どちらかの制限を抱えて生活する必要はなく、同時に両方を最大限に活用する必要はありません...え？
配列の削除の場合、'Deleted' バイトを使用して、行が削除されたことを表すことができるため、配列の再編成は不要になります。挿入や急速に変化するデータの負担を軽減するには、リンクされたリストを使用します。次に、それらを参照するときに、ロジックで最初に 1 つを検索し、次にもう 1 つを検索します。したがって、これらを組み合わせて使用すると、両方の利点が得られます。
非常に大きな配列がある場合は、それを別のはるかに小さい配列またはリンクされたリストと組み合わせることができます。小さい方の配列には、最近使用した 20、50、100 個のアイテムが含まれます。必要なものが短い連結リストまたは配列にない場合は、大きな配列に移動します。そこに見つかった場合は、「最近使用したものは再利用される可能性が最も高い」という前提で、それをより小さなリンクされたリスト/配列に追加できます(そうです、リストから最も最近使用されていないアイテムをバンプする可能性があります)。これは多くの場合に当てはまり、私が .ASP セキュリティ アクセス許可チェック モジュールで取り組まなければならなかった問題を、簡単かつ優雅に、印象的な速さで解決しました。
linklist を使用している人は必読です。人々は再び配列に恋をするでしょう。Out Of Order 実行、ハードウェア プリフェッチ、メモリ レイテンシなどについて説明します。
http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
配列とリンク リストの違いは、配列はインデックス ベースのデータ構造であり、すべての要素がインデックスに関連付けられているのに対し、リンク リストは参照を使用するデータ構造であり、各ノードは別のノードを参照することです。配列のサイズは固定されていますが、リンクリストのサイズは固定されていません。