配列とリンクリストの比較

StackOverflow https://stackoverflow.com/questions/166884

質問

なぜ配列ではなくリンク リストを使用したいのでしょうか?

リンク リストのコーディングは、配列を使用するよりも少し手間がかかることは間違いありません。追加の労力が何に正当化されるのか疑問に思う人もいるかもしれません。

新しい要素の挿入はリンクリストでは簡単だと思いますが、配列では大変な作業です。データセットを配列に格納する場合と比較して、リンクリストを使用してデータセットを格納することには、他にも利点はありますか?

この質問は次の質問と重複するものではありません この質問 なぜなら、他の質問は特定の Java クラスについて具体的に尋ねているのに対し、この質問は一般的なデータ構造に関するものだからです。

役に立ちましたか？

解決

  • リンクされたリストにさまざまなサイズのデータ​​を保存する方が簡単です。配列では、すべての要素がまったく同じサイズであると想定されます。
  • おっしゃるとおり、リンクされたリストは有機的に成長しやすいです。配列のサイズは事前に把握しておくか、拡張する必要があるときに再作成する必要があります。
  • リンクされたリストをシャッフルすることは、何を指すのかを変更するだけです。配列のシャッフルはより複雑になり、より多くのメモリが必要になります。
  • すべての反復が「foreach」コンテキストで行われる限り、反復中にパフォーマンスが失われることはありません。

他のヒント

もう1つの正当な理由は、リンクリストが効率的なマルチスレッド実装に適していることです。この理由は、変更はローカルになりがちであるためです。データ構造のローカライズされた部分での挿入と削除のポインタは1つまたは2つだけです。そのため、同じリンクリストで多数のスレッドを動作させることができます。さらに、CASタイプの操作を使用してロックフリーバージョンを作成し、重いロックを完全に回避することができます。

リンクリストを使用すると、イテレータは変更中にリストを走査することもできます。変更が衝突しない楽観的なケースでは、イテレータは競合することなく続行できます。

配列の場合、配列のサイズを変更するには、配列の大部分をロックする必要があります。実際、配列全体でグローバルロックを使用せずにこれを行うことはめったにないため、変更は停止します世界情勢。

Wikipediaには、違いに関する非常に優れたセクションがあります。

  

リンクリストにはいくつかの利点があります   配列上。要素を挿入できます   無限にリンクリストに   配列は最終的にどちらかを埋めます   アップまたはサイズ変更が必要、高価   でさえないかもしれない操作   メモリが断片化されている場合に可能です。   同様に、多くの   削除される要素は   無駄に空になるか、作成する必要がある   小さい。

     

一方、配列はランダムを許可します   アクセス、リンクリストのみ許可   要素への順次アクセス。   実際、単一リンクリストは   一方向に移動します。この   リンクされたリストを不適切にします   見ていると便利なアプリケーション   インデックスによって要素をすばやく作成し、   ヒープソートなど。順次アクセス   配列はリンクよりも高速です   局所性による多くのマシンのリスト   参照およびデータキャッシュの。リンク済み   リストはほとんど恩恵を受けません   キャッシュ。

     

リンクリストの別の欠点   に必要な追加のストレージです   多くの場合、それらを作る参照   小さなデータのリストには非実用的   文字やブールなどのアイテム   値。また、遅くなる可能性があります   na <！>＃239; veアロケータ、無駄な、   それぞれに個別にメモリを割り当てます   新しい要素、一般的な問題   メモリプールを使用して解決しました。

http://en.wikipedia.org/wiki/Linked_list

もう1つ追加します-リストは完全に機能のデータ構造として機能します。

たとえば、同じ終了セクションを共有する完全に異なるリストを持つことができます

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

i.e。：

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next

aが指すデータをbおよびcにコピーする必要なし。

これが、不変変数を使用する関数型言語で非常に人気がある理由です-prependおよびtail操作は、元のデータをコピーすることなく自由に実行できます-データを不変として扱う場合の非常に重要な機能です。

リストの中央に挿入するのが簡単であることに加えて、配列よりもリンクされたリストの中央から削除する方がはるかに簡単です。

しかし、率直に言って、リンクリストを使用したことはありません。高速な挿入と削除が必要なときはいつでも、高速なルックアップも必要だったため、HashSetまたはDictionaryに移動しました。

2つのリンクリスト（特に2つの二重リンクリスト）のマージは、2つの配列のマージよりもはるかに高速です（マージが破壊的であると想定）。前者はO（1）を取り、後者はO（n）を取ります。

編集：明確にするため、<！> quot;マージ<！> quot;ここでは、マージソートのようにではなく、無秩序な意味で。おそらく<！> quot; concatenating <！> quot;より良い言葉だっただろう。

ArrayList および LinkedList に対する広く評価されていない議論は、次のとおりです。 LinkedList はデバッグ中に不快です. 。メンテナンス開発者がプロ​​グラムを理解するために費やした時間。バグや増加を見つけるには、私見では、エンタープライズ アプリケーションのパフォーマンス向上におけるナノ秒やメモリ消費量のバイトが正当化されない場合があります。場合によっては (もちろん、アプリケーションの種類によって異なりますが)、数バイトを無駄にしても、より保守しやすい、または理解しやすいアプリケーションを使用する方が良い場合があります。

たとえば、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 の内部をフィルタリングするために必要な認知オーバーヘッドは言うまでもなく、「ツリー展開」クリックの悪夢になります。

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 またはリンクリストのブーストポインターリスト。リンクリストと配列の主な問題は、ポインターとひどいランダムアクセスに必要な余分なスペースです。

の場合は、リンクリストを使用する必要があります
  • データへのランダムアクセスは不要
  • 特にリストの中央で要素を追加/削除します

私にとってはこんな感じです

  1. アクセス

    • リンクリストでは、要素への順次アクセスのみが許可されます。したがって、アルゴリズムの複雑さはO（n）の次数です
    • 配列はその要素へのランダムアクセスを許可するため、複雑さはO（1）の順序です

  2. ストレージ

    • リンクリストでは、参照用に追加のストレージが必要です。これは、文字やブール値などの小さなデータ項目のリストに対しては実用的ではありません。
    • 配列は、次のデータ項目を指すために追加のストレージを必要としません。各要素にはインデックスを介してアクセスできます。

  3. サイズ

    • リンクリストのサイズは本質的に動的です。
    • 配列のサイズは宣言に制限されています。

  4. 挿入/削除

    • 要素はリンクリストで無期限に挿入および削除できます。
    • 配列の値の挿入/削除は非常に高価です。メモリの再割り当てが必要です。

2つのこと：

  

リンクされたリストのコーディングは、間違いなく、配列を使用するよりも少し手間がかかり、彼は何が追加の努力を正当化するのか疑問に思いました。

C ++を使用する場合は、リンクリストをコーディングしないでください。 STLを使用するだけです。実装がどれほど難しいかは、ほとんどのデータ構造がすでに実装されているため、あるデータ構造を別のデータ構造よりも選択する理由にはなりません。

配列とリンクリストの実際の違いに関して、私にとって大きなことは、構造の使用方法を計画することです。ベクトルという用語は、C ++のサイズ変更可能な配列の用語なので使用します。

リンクされたリストへのインデックス付けは、指定されたインデックスに到達するためにリストを走査する必要があるため遅くなりますが、ベクトルはメモリ内で連続しており、ポインタ数学を使用してそこに到達できます。

リンクリストの末尾または先頭に追加するのは簡単です。1つのリンクを更新するだけでよいため、ベクターではコンテンツのサイズを変更してコピーする必要がある場合があります。

リストからアイテムを削除するのは簡単です。1組のリンクを解除してから、それらを再び接続するだけです。順序を気にするかどうかに応じて、ベクターからアイテムを削除する速度は速くも遅くもなります。削除するアイテムの上にある最後のアイテムを上にスワッピングすると高速になり、ダウンした後にすべてをシフトすると遅くなりますが、順序は維持されます。

Eric Lippertには最近投稿がありました配列を控えめに使用する理由の1つ。

高速な挿入と削除は、実際にリンクリストの最適な引数です。構造が動的に成長し、任意の要素（動的スタックやキューなど）への一定時間のアクセスが必要ない場合は、リンクリストが適しています。

ここに簡単なものがあります：アイテムの削除が速くなりました。

リンクリストは、コレクションが絶えず成長している場合に特に便利です。収縮。たとえば、配列を使用してキューを実装しようとする（最後に追加し、前面から削除する）ことを想像するのは困難です。一方、リンクされたリストを使用するのは簡単です。

リストの中央から追加および削除する以外に、リンクリストは動的に拡大および縮小できるため、リンクリストの方が好きです。

自分のリンクリストをコーディングする人はもういません。それはばかげている。リンクリストを使用するとより多くのコードが必要になるという前提は、間違っています。

最近では、リンクリストの作成は、学生が概念を理解できるようにするための演習にすぎません。代わりに、全員が事前に作成されたリストを使用します。 C ++では、質問の説明に基づいて、おそらくstlベクトル（#include <vector>）を意味します。

したがって、リンクリストと配列を選択することは、アプリのニーズに応じて各構造のさまざまな特性を比較することです完全にです。追加のプログラミングの負担を克服しても、決定に影響はありません。

それは本当に効率の問題です。リンクリスト内の要素を挿入、削除、または移動するオーバーヘッドは最小限です。つまり、操作自体はO（1）で、O（n）は配列。データのリストを頻繁に操作している場合、これは大きな違いを生む可能性があります。データ型は、その操作方法に基づいて選択し、使用しているアルゴリズムに最も効率的なものを選択しました。

配列は、アイテムの正確な数がわかっている場合、およびインデックスによる検索が意味をなす場合に意味があります。たとえば、圧縮せずに特定の瞬間のビデオ出力の正確な状態を保存したい場合、おそらくサイズ[1024] [768]の配列を使用します。これにより、必要なものが正確に提供されます。また、指定されたピクセルの値を取得するためのリストは非常に遅くなります。配列が意味をなさない場所では、データを効果的に処理するために、一般的にリストよりも優れたデータ型があります。

配列とリンクリスト：

  1. メモリの断片化が原因で、配列メモリの割り当てが失敗することがあります。
  2. すべての要素には連続したメモリ空間が割り当てられるため、配列ではキャッシュが優れています。
  3. コーディングは配列よりも複雑です。
  4. 配列とは異なり、リンクリストにサイズ制限はありません
  5. リンクリストでは挿入/削除が速くなり、配列ではアクセスが速くなります。
  6. マルチスレッドの観点からリンクリストの改善。

配列は本質的に静的であるため、すべての操作 コンパイル時にメモリ割り当てが発生するような のみ。そのため、プロセッサは実行時の労力を減らす必要があります。

順序付けられたセットがあり、要素を追加および削除して変更することもできます。さらに、後で前または次の要素を取得できるように、要素への参照を保持する機能が必要です。たとえば、To Doリストや本の段落セット。

最初に、セット自体の外部のオブジェクトへの参照を保持する場合、オブジェクト自体を保存するのではなく、配列にポインターを保存することになります。そうしないと、配列に挿入できません。オブジェクトが配列に埋め込まれている場合、オブジェクトは挿入中に移動し、それらへのポインターは無効になります。配列インデックスについても同様です。

最初に指摘したように、最初の問題は挿入です。リンクリストではO（1）に挿入できますが、配列には通常O（n）が必要です。この問題は部分的に克服することができます-読み取りと書き込みの両方が最悪の場合、対数である配列のような通常のアクセスインターフェイスを提供するデータ構造を作成することが可能です。

2番目に深刻な問題は、次の要素を見つける要素がO（n）であることです。セットが変更されていない場合、ポインタの代わりに要素のインデックスを参照として保持することができ、find-nextをO（1）操作にしますが、オブジェクト自体へのポインタであり、方法はありません<！> quot; array <！> quot;全体をスキャンする以外の方法で、配列内の現在のインデックスを決定します。これは配列にとって乗り越えられない問題です-挿入を最適化できたとしても、次のタイプの検索操作を最適化するためにできることは何もありません。

配列では、O（1）時間で任意の要素にアクセスする特権があります。そのため、バイナリ検索クイックソートなどの操作に適しています。一方、リンクリストは、O（1）時間の挿入削除に適しています。どちらにも長所と短所があり、どちらを優先するかは、実装するものになります。

-大きな問題は、両方のハイブリッドを使用できるかどうかです。 pythonとperlがリストとして実装するもののようなもの。

リンクリスト

挿入に関しては、より望ましいです！基本的には、ポインターを処理することです

1-<！> gt; 3-<！> gt; 4

挿入（2）

1 ........ 3 ...... 4
..... 2

最後に

1-<！> gt; 2-<！> gt; 3-<！> gt; 4

3の2点から1本の矢印と2の1点の矢印

シンプル！

しかし配列から

| 1 | 3 | 4 |

挿入（2） | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

だれでも違いを視覚化できます！ インデックスが4つだけの場合、3つのステップを実行しています

配列の長さが100万の場合はどうなりますか？配列は効率的ですか？ 答えはノーだ！ ：）

同じことが削除についても言えます！ リンクリストでは、単純にポインタを使用して、要素を無効にし、次にオブジェクトクラス内で無効にすることができます。 しかし、配列の場合、shiftLeft（）

を実行する必要があります

役立つことを願っています！ ：）

リンクリストは、配列よりも維持するオーバーヘッドが多く、これらすべての点が合意されている追加のメモリストレージも必要です。しかし、配列ができないことはいくつかあります。多くの場合、長さ10 ^ 9の配列が必要だと仮定します。連続したメモリ位置を1つ取得する必要があるため、取得できません。リンクされたリストはここで救世主になる可能性があります。

複数のデータをデータとともに保存したい場合、リンクリストで簡単に拡張できます。

STLコンテナには通常、背後でリンクリストの実装があります。

リンクリストを使用する唯一の理由は、要素の挿入が簡単なことです（削除も可能です）。

欠点は、ポインターが多くのスペースを取ることです。

そしてそのコーディングについては難しいです： 通常、リンクされたコードは必要ありません（または一度だけ） STL  まだやらなければならないのであればそれほど複雑ではありません。

iは、リンクリストの方が配列よりも優れていると考えています。 私たちは配列ではなくリンクリストを走査するためです

言語によっては、これらの短所と長所のいくつかを考慮することができます：

Cプログラミング言語：リンクリストを使用する場合（通常は構造体ポインターを使用）、メモリリークがないことを特に考慮する必要があります。前に述べたように、リンクされたリストはシャッフルが簡単です。なぜなら、すべてがポインターを変更しているからです。しかし、すべてを解放することを忘れないでください？

Java ：Javaには自動ガベージコレクションがあるため、メモリリークは問題になりませんが、リンクリストの実装の詳細はハイレベルプログラマからは見えません。リストの中央からノードを削除するなどの方法は、言語の一部のユーザーが期待するよりも手順が複雑です。

なぜ配列ではなくリンクされたリストを使うのでしょうか?すでに何人かが言っているように、挿入と削除の速度が向上しました。

しかし、私たちはどちらかの制限に耐える必要はなく、同時に両方の長所を最大限に活用する必要があるのか​​もしれません...え？

配列の削除の場合、「削除」バイトを使用して行が削除されたという事実を表すことができるため、配列の再編成は必要なくなります。挿入やデータの急速な変更の負担を軽減するには、リンク リストを使用します。次に、それらを参照するときに、ロジックで最初に一方を検索し、次にもう一方を検索します。したがって、これらを組み合わせて使用​​すると、両方の長所が得られます。

非常に大きな配列がある場合は、それを別のはるかに小さい配列またはリンク リストと組み合わせて、小さい配列に最近使用した 20、50、100 個の項目を保持することができます。必要なものが短いリンク リストまたは配列にない場合は、大きい配列に移動します。そこで見つかった場合は、「最近使用されたものは再利用される可能性が最も高い」という仮定に基づいて、それをより小さなリンクされたリスト/配列に追加できます (そして、おそらく、最も最近使用されていない項目をリストから削除します)。これは多くの場合に当てはまり、.ASP セキュリティ権限チェック モジュールで取り組まなければならなかった問題を、簡単かつ優雅に、そして驚異的な速度で解決しました。

多くの人がリンクリストと配列の主要な改良/修正に触れましたが、比較の大部分は、一方が他方より優れているか悪いかです。配列でランダムアクセスを行うことはできますが、リンクリストなどではできません。ただし、これはリンクリストと配列が同様のアプリケーションに適用されることを前提としています。ただし、正しい答えは、特定のアプリケーションの展開において、アレイよりもリンクリストを優先する方法と、その逆の場合です。 辞書アプリケーションを実装する場合、何を使用しますか？ 配列：mmmバイナリ検索やその他の検索アルゴリズムを使用して簡単に取得できますが、リンクリストの改善方法を考えてみましょう。<！> quot; Blob <！> quot;辞書で。 A-<！> gt; B-<！> gt; C-<！> gt; D ---- <！> gt; Zのリンクリストを作成してから、各リスト要素がその文字で始まるすべての単語の配列または別のリスト.. 

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

今、上記のアプローチの方が良いですか、または[Adam、Apple、Banana、Blob、Cat、Cave]のフラット配列ですか？配列でも可能でしょうか？ したがって、リンクリストの主な利点は、次の要素だけでなく、他のリンクリスト/配列/ヒープ/または他のメモリの場所を指す要素を持つことができることです。 配列は、格納する要素のブロックサイズにスライスされた1つのフラットな連続メモリです。一方、リンクリストは、非連続メモリユニットのチャンク（任意のサイズで任意のデータを格納できます）で、それぞれを指します。あなたが望む他の方法。 同様に、USBドライブを作成しているとしましょう。ファイルを配列またはリンクリストとして保存しますか？私が何を指しているのかわかると思います：）

  

なぜ配列にリンクリストを使用したいのですか？

これが唯一の理由です。リンクリストデータ構造が必要で、使用しているプログラミング言語がポインタをサポートしていない場合。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top