223

私はたくさんのリストと配列を使用していますが、配列リストをリンクリストと同じくらい簡単に使用できないというシナリオにはまだ遭遇していません。リンクリストが特に優れている場合の例を誰かが教えてくれることを期待していました。

4

15 に答える 15

304

次の場合は、配列よりもリンクリストの方が適しています。

  1. リストからの一定時間の挿入/削除が必要です（時間の予測可能性が絶対的に重要なリアルタイムコンピューティングなど）

  2. リストにいくつのアイテムが含まれるかわかりません。配列の場合、配列が大きくなりすぎた場合は、メモリを再宣言してコピーする必要があります。

  3. 要素にランダムにアクセスする必要はありません

  4. リストの中央にアイテムを挿入できるようにしたい（優先キューなど）

配列は次の場合に適しています。

  1. 要素へのインデックス付き/ランダムアクセスが必要です

  2. 配列内の要素の数を事前に知っているので、配列に正しい量のメモリを割り当てることができます

  3. すべての要素を順番に繰り返すときは、速度が必要です。配列でポインター演算を使用して各要素にアクセスできますが、リンクリスト内の各要素のポインターに基づいてノードを検索する必要があります。これにより、ページフォールトが発生し、パフォーマンスが低下する可能性があります。

  4. 記憶が問題です。塗りつぶされた配列は、リンクリストよりも少ないメモリを使用します。配列内の各要素は単なるデータです。各リンクリストノードには、データと、リンクリスト内の他の要素への1つ（または複数）のポインターが必要です。

配列リスト（.Netのリストなど）には配列の利点がありますが、リソースを動的に割り当てるため、リストサイズについてあまり心配する必要はなく、任意のインデックスでアイテムを削除したり、やり直したりする必要はありません。周りの要素をシャッフルします。パフォーマンス面では、配列リストは生の配列よりも低速です。

于 2008-12-26T07:12:04.860 に答える
67

配列にはO（1）のランダムアクセスがありますが、何かを追加したり、そこから何かを削除したりするには、非常にコストがかかります。

リンクリストは、どこにでもアイテムを追加または削除したり、繰り返したりするのに非常に安価ですが、ランダムアクセスはO（n）です。

于 2008-12-26T07:08:06.723 に答える
16

他の回答に追加すると、ほとんどの配列リストの実装では、リストの最後に余分な容量が予約されているため、新しい要素を O(1) 時間でリストの最後に追加できます。配列リストの容量を超えると、新しいより大きな配列が内部的に割り当てられ、古い要素がすべてコピーされます。通常、新しい配列は古い配列の 2 倍のサイズになります。これは、平均して、配列リストの最後に新しい要素を追加することは、これらの実装では O(1) 操作であることを意味します。したがって、事前に要素の数がわからない場合でも、要素を最後に追加する限り、配列リストは要素を追加するための連結リストよりも高速である可能性があります。明らかに、配列リストの任意の場所に新しい要素を挿入することは、依然として O(n) 操作です。

配列リスト内の要素へのアクセスは、アクセスがシーケンシャルであっても、リンクされたリストよりも高速です。これは、配列要素が連続したメモリに格納され、簡単にキャッシュできるためです。リンク リスト ノードは、多くの異なるページに分散している可能性があります。

任意の場所でアイテムを挿入または削除することがわかっている場合は、リンクされたリストのみを使用することをお勧めします。配列リストは、他のほとんどすべてに対してより高速になります。

于 2008-12-26T09:13:52.273 に答える
7

リストの利点は、アイテムを中央に挿入する必要があり、配列のサイズ変更やシフトを開始したくない場合に表示されます。

これは通常は当てはまらないという点で正しいです。私はそのような非常に特殊なケースをいくつか経験しましたが、あまり多くはありません。

于 2008-12-26T07:07:49.517 に答える
4

それはすべて、反復中に実行している操作の種類に依存します。すべてのデータ構造には時間とメモリの間のトレードオフがあり、ニーズに応じて適切な DS を選択する必要があります。そのため、LinkedList が配列よりも高速である場合や、その逆の場合もあります。データ構造に対する 3 つの基本的な操作について考えてみましょう。

  • 検索中

array は index ベースのデータ構造であるため、array.get(index) を検索すると O(1) 時間がかかりますが、linkedlist はインデックス DS ではないため、 index までトラバースする必要があります。ここで、 index <=n 、n は linked list のサイズです。そのため、要素のランダムアクセスがある場合、配列はリンクされたリストよりも高速です。

Q.では、この背後にある美しさは何ですか?

配列は連続したメモリブロックであるため、最初のアクセス時にそれらの大きなチャンクがキャッシュにロードされます。これにより、配列の要素にアクセスする限り、参照の局所性も増加するため、配列の残りの要素に比較的迅速にアクセスできます。ミス、キャッシュの局所性は、キャッシュ内にある操作を指すため、メモリ内と比較してはるかに高速に実行されます。基本的に配列では、キャッシュ内にある順次要素アクセスの可能性を最大化します。リンクされたリストは必ずしもメモリの連続したブロックにあるとは限りませんが、リストに順番に表示されるアイテムが実際にメモリ内で互いに近くに配置されているという保証はありません。これは、キャッシュ ヒットが少ないことを意味します。

  • 挿入

配列と比較して LinkedList (Java) での挿入は O(1) 操作であるため、これは LinkedList では簡単かつ高速です。配列がいっぱいになった場合を考えてみましょう。要素を O(n) の ArrayList に最悪の場合、配列の最後以外の場所に何かを挿入した場合、ArrayList もそのインデックスを更新する必要があります。リンクされたリストの場合、サイズを変更する必要はありません。ポインターを更新します。

  • 消す

挿入のように機能し、配列よりも LinkedList の方が優れています。

于 2016-04-16T09:32:25.883 に答える
2

これらは Collection の最も一般的に使用される実装です。

配列リスト：

  • 最後に挿入/削除 通常 O(1) 最悪の場合 O(n)

  • 途中で挿入/削除 O(n)

  • 任意の位置を取得 O(1)

リンクリスト:

  • 任意の位置に挿入/削除 O(1) (要素への参照がある場合は注意してください)

  • 途中で取得 O(n)

  • 最初または最後の要素を取得 O(1)

ベクトル: 使用しないでください。これは ArrayList に似た古い実装ですが、すべてのメソッドが同期されています。マルチスレッド環境での共有リストの正しいアプローチではありません。

ハッシュマップ

O(1) のキーによる挿入/削除/取得

O(log N) でのTreeSetの挿入/削除/包含

O(1) のHashSet 挿入/削除/含む/サイズ

于 2015-07-04T13:26:41.007 に答える
0

うーん、Arraylistは次のような場合に使用できます。

  1. いくつの要素が存在するかわからない
  2. ただし、インデックスを作成してすべての要素にランダムにアクセスする必要があります

たとえば、連絡先リストのすべての要素をインポートしてアクセスする必要があります（サイズは不明です）。

于 2008-12-26T07:28:20.257 に答える
0

配列の基数並べ替えと多項式演算にはリンク リストを使用します。

于 2013-01-24T15:30:52.523 に答える
0

1) 上で説明したように、挿入操作と削除操作は、ArrayList(O(n)) と比較して、LinkedList で優れたパフォーマンス (O(1)) を提供します。したがって、アプリケーションで頻繁に追加および削除する必要がある場合は、LinkedList が最適です。

2) 検索 (get メソッド) 操作は Arraylist (O(1)) では高速ですが、LinkedList (O(n)) では高速ではないため、追加操作と削除操作が少なく、検索操作の要件が多い場合は、ArrayList が最適です。

于 2015-09-05T12:01:21.537 に答える
0

いくつかのベンチマークを行ったところ、リスト クラスは実際には LinkedList よりもランダムな挿入が高速であることがわかりました。

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

リンクされたリストの場合は 900 ミリ秒、リスト クラスの場合は 100 ミリ秒かかります。

後続の整数のリストを作成します。リストに既にある乱数の後に、それぞれ新しい整数が挿入されます。List クラスは単なる配列よりも優れたものを使用している可能性があります。

于 2016-05-08T13:33:08.943 に答える
0

主な違いは、リストの一番上に頻繁に挿入または削除する必要があるかどうかだと思います。

配列では、リストの先頭から何かを削除すると、配列要素のすべてのインデックスをシフトする必要があるため、複雑さは o(n) になります。

リンクされたリストでは、ノードを作成し、ヘッドを再割り当てし、次への参照を前のヘッドとして割り当てるだけでよいため、o(1) です。

リストの最後で頻繁に挿入または削除する場合、複雑さが o(1) になるため配列が望ましいです。最後のノードへ。

おそらくバイナリ検索を使用するため、リンクされたリストと配列の両方での検索は o(log n) になると思います。

于 2016-01-31T16:00:36.147 に答える