17 
List li = new LinkedList();

for (int i = 0; i < 100; i++) {
    li.add(i);
}

long start1 = System.nanoTime();
li.get(57);

long end1 = System.nanoTime();
long diff1 = end1-start1;

System.out.println("Time taken by LinkedList = "+diff1);

List al = new ArrayList();
for (int i = 0; i < 100; i++) {
    al.add(i);
}

両方のリストでどのような操作を実行しても、かかった時間を出力すると、ArrayList は常に LinkedList よりも高速に実行されます。所要時間の点でどちらが優れているか誰か説明できますか? また、コードに問題がある場合はお知らせください。ありがとう！

4

4 に答える 4

16

多くの挿入とそれほど頻繁ではないルックアップを実行する必要がある場合は、LinkedList. ArrayList挿入よりも多くのルックアップを実行する場合に使用します。

その理由は次のとおりArrayListです。初期容量を持つ配列によってサポートされています。したがって、リストにアイテムを挿入し続けると、ある時点で、新しく挿入されたアイテムに対応するために配列容量を再調整する必要があり、インデックス固有の挿入を実行する場合は、既存のアイテムをシフトする必要がある場合もあります。一方、LinkedListリンクされたリストに支えられており、アイテムの作成は常に一定の時間で実行されます-アイテムを作成してリストの最後に割り当てます。ここでは再調整は行われません。

からアイテムをフェッチするArrayListには、一定の時間でバッキング配列に簡単にインデックスを付けることができるため、常に一定の時間がかかります。ただし、 から項目をフェッチするLinkedListと、リンク リスト全体を走査して項目ノードを見つける必要がある場合があります。ArrayListその結果、この場合よりもパフォーマンスが低下します。

上記の議論から、前者はそうでないのに対し、後者は挿入に関連する内部サイズ変更コストLinkedListがあるため、より多くの挿入を行う場合、常に優れていることがわかります。一方、挿入の頻度が低く、ルックアップの頻度が高い場合は、後者の場合、目的のアイテムを見つけるためにリンクされたリスト構造全体をトラバースする必要がある場合があるため、常に優れていますが、前者は配列を使用してアイテムをすばやく見つけることができます。一定時間のインデックス作成。ArrayListArrayListLinkedList

上記のすべての効果は、多数のアイテム (たとえば、数千のアイテム) を処理している場合に表示され、アプリケーションのパフォーマンスに影響を与えます。アイテム数が少ない場合、パフォーマンスの違いはあまり目立ちません。

さて、あなたのコードについてですが、いくつかの重大な問題があります。手始めに、生の型を使用していますが、ジェネリックが提供するすべての型の安全性が失われるため、これは悪いことです。新しいコードを記述するときは、常にコレクション API の汎用バージョンを使用する必要があります。したがって、次のようにコードを変更してください -

List<Integer> li = new LinkedList<Integer>();
for (int i = 0; i < 100; i++) {
    li.add(i);
}

long start1 = System.nanoTime();
li.get(57);

long end1 = System.nanoTime();
long diff1 = end1 - start1;

System.out.println("Time taken by LinkedList = "+diff1);

List<Integer> al = new ArrayList<Integer>();
for (int i = 0; i < 100; i++) {
    al.add(i);
}

詳細な説明については、 Effective Javaの項目 23: 新しいコードで生の型を使用しないを参照してください。

編集

コメントの議論から、リストの途中またはランダムな位置に要素を挿入する必要がある場合、前者は要素をシフトするために使用されるため、パフォーマンスの点でArrayList優れていることは明らかです。非常に高速であり、後者は新しい要素を適切に挿入するために目的のインデックスまでトラバースする必要があり、低速です。そのため、ランダムな挿入についても より優れています。唯一のケースは、リストの最後に挿入するだけで、これらの挿入がたくさんある場合です。LinkedListmemcpyArrayListLinkedListLinkedListArrayList

于 2013-09-11T07:05:04.237 に答える
2

読み取りに関しては、配列リストは常にリンクされたリストよりも高速です。ArrayList は基本的に配列の実装であり、配列に割り当てられるメモリはシーケンシャルであるため、読み取りは高速です。ただし、リストの間に挿入または削除が必要なリストを使用する場合は、リンクされたリストの方が高速です。ノード間にリンクを追加するだけだったからです。これらの 2 つのケースでは、配列リストが遅くなります。使用法は次のとおりです。

ArrayList - 読み取り操作が速くなり、リスト間の挿入、削除が遅くなります。Linked List - 配列リストに比べて読み取り操作は遅いですが、リスト間の挿入、削除は高速です。

于 2013-09-11T07:08:42.393 に答える
1

ArrayList配列によって支えられておりLinkedList、参照でリンクされている支えられたノードです。

したがって、操作ArrayListは実際には配列の評価操作です。追加操作は償却された一定時間で実行されます。つまり、n 個の要素を追加するにはO(n)時間がかかります。他のすべての操作は線形時間で実行されます (大まかに言えば)。定数係数は、LinkedList実装の場合と比較して低くなっています。

そして、LinkedListすべての操作で、二重リンクリストに期待されるように実行されます。リストにインデックスを付ける操作は、指定されたインデックスに近い方からリストをトラバースします。

ドキュメントの詳細を読む -

于 2013-09-11T07:05:40.043 に答える