順序 - linkedlist java 使い方




JavaでArrayListの上でLinkedListを使用する場合 (20)

私はいつも使っているだけです。

List<String> names = new ArrayList<>();

私は移植性の型名としてインターフェイスを使用しています。そのため、私はこれらの質問をするとコードを書き直すことができます。

LinkedListLinkedList ArrayList上で使用する必要がありますか?


1) 検索: ArrayList検索操作は、LinkedList検索操作に比べてかなり高速です。 ArrayListのget(int index)は、LinkedListのパフォーマンスがO(n)である間にO(1)のパフォーマンスを示します。

理由: ArrayListは配列のデータ構造を暗黙的に使用するため、要素のインデックスベースのシステムを維持しているため、リスト内の要素を検索する処理が高速になります。 一方、LinkedListは二重リンクリストを実装しています。このリストでは、要素を検索するためにすべての要素をたどる必要があります。

2)削除: LinkedListの削除操作では、ArrayListが可変のパフォーマンスを与える間にO(1)のパフォーマンスが得られます。最悪の場合(最初の要素を削除している間)、O(1) 。

結論: LinkedList要素の削除は、ArrayListに比べて高速です。

理由: LinkedListの各要素は、2つのポインタ(アドレス)を保持しています。ポインタは、リスト内の両方の隣接要素を指しています。したがって、除去は、除去されるべきノードの2つの隣接ノード(要素)におけるポインタ位置の変更を必要とするだけである。In ArrayListの間、削除された要素によって作成されたスペースを埋めるために、すべての要素を移動する必要があります。

3)Inserts Performance: LinkedList addメソッドは、ArrayListが最悪の場合にO(n)を返す間にO(1)のパフォーマンスを与えます。理由は、削除について説明したのと同じです。

4)メモリオーバヘッド: ArrayListはインデックスと要素データを保持するが、LinkedListは要素データと2つのポインタを保持しているため、比較的LinkedListのメモリ消費量が多い。

これらのクラス間には、次のような類似点ほとんどありませ

ArrayListとLinkedListはどちらもListインターフェイスの実装です。それらはどちらも要素の挿入順序を維持しています。つまり、ArrayList要素とLinkedList要素を表示しているときに、結果セットは要素がListに挿入された順序と同じ順序になります。これらのクラスは両方とも非同期であり、Collections.synchronizedListメソッドを使用して明示的に同期させることができます。これらのクラスから返されるiteratorおよびlistIteratorは、フェイルファーストです(イテレータが作成された後、リストが構造的に変更された場合は、イテレータ自身のremoveメソッドまたはaddメソッド以外の方法で、イテレータはConcurrentModificationExceptionをスローします)。

LinkedListを使用するタイミングとArrayListを使用するタイミング

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

2)検索(メソッドの取得)操作はArrayList(O(1))で高速ですが、LinkedList(O(n))ではできません。


ArrayListそして、LinkedListの両方を実装List interfaceし、その方法及び結果はほとんど同じです。しかし、それらの間には、要求に応じて他のものより優れたものを作る相違点はほとんどありません。

ArrayListとLinkedList

1)Search: ArrayList検索操作は、LinkedList検索操作に比べてかなり高速です。get(int index)in ArrayListは性能があるO(1)間にLinkedList性能を与えるO(n)

Reason: ArrayList暗黙的に配列データ構造を使用するので、要素の索引ベースのシステムを維持します。これにより、リスト内の要素を検索する処理が高速になります。反対側LinkedListでは、要素を検索するためにすべての要素を通過する必要がある二重リンクリストを実装しています。

2)Deletion: LinkedList除去操作ではO(1)パフォーマンスがArrayList得られますがO(n)、最悪の場合(最初の要素を削除している間)O(1)、最善の場合(最後の要素を削除している間)、可変のパフォーマンスが得られます。

結論:LinkedList要素の削除は、ArrayListに比べて高速です。

理由:LinkedListの各要素は、リスト内の両方の隣接要素を指す2つのポインタ(アドレス)を保持します。したがって、除去は、除去されるべきノードの2つの隣接ノード(要素)におけるポインタ位置の変更を必要とするだけである。In ArrayListの間、削除された要素によって作成されたスペースを埋めるために、すべての要素を移動する必要があります。

3)Inserts Performance: LinkedListメソッドを追加すると、最悪の場合でもO(1)パフォーマンスがArrayListO(n)られます。理由は削除の説明と同じです。

4)Memory Overhead: ArrayListは要素データをLinkedList維持しながらインデックスと要素データを維持し、隣接ノードには2つのポインタ

比較的LinkedListのメモリ消費量が多い。

これらのクラス間には、次のような類似点はほとんどありません。

  • ArrayListとLinkedListはどちらもListインターフェイスの実装です。
  • それらはどちらも要素の挿入順序を維持しています。つまり、ArrayList要素とLinkedList要素を表示しているときに、結果セットは要素がListに挿入された順序と同じ順序になります。
  • これらのクラスは両方とも非同期であり、Collections.synchronizedListメソッドを使用して明示的に同期させることができます。
  • iteratorそしてlistIterator、これらのクラスによって返されますfail-fast(リストは、構造以外の方法では、反復子の作成後にいつでも変更された場合iterator's自体のremoveまたはaddメソッド、イテレータますthrowA ConcurrentModificationException)。

LinkedListを使用するタイミングとArrayListを使用するタイミング

  • インサート上述と削除などの操作は、良好な性能を与える(O(1))LinkedListと比較しますArrayList(O(n))

    したがって、アプリケーションで頻繁に追加および削除する必要がある場合は、LinkedListが最適です。

  • 検索(get method)操作は高速ですArraylist (O(1))が、LinkedList (O(n))

    したがって、追加操作と削除操作が少なく、検索操作の要件が多い場合は、ArrayListが最適です。


ArrayListは本質的に配列です。 LinkedListは二重リンクリストとして実装されています。

getはかなり明確です。 ArrayListはインデックスを使用してランダムアクセスを許可するため、 ArrayList O(1)を使用します。 LinkedList O(n)はインデックスを最初に探す必要があるためです。 注: addremoveバージョンは異なります。

LinkedListは追加と削除が高速ですが、getは遅くなります。 要するに、 LinkedListは次の場合に優先されるべきです:

  1. 要素のランダムアクセスが多数ありません
  2. 多数の追加/削除操作があります

=== ArrayList ===

  • 加算(E e)
    • ArrayListの最後に追加する
    • メモリのサイズ変更のコストが必要です。
    • O(n)最悪、O(1)償却
  • add(int index、E element)
    • 特定のインデックス位置に追加する
    • シフティング&可能なメモリリサイジングコストが必要
    • に)
  • remove(int index)
    • 指定された要素を削除する
    • シフティング&可能なメモリリサイジングコストが必要
    • に)
  • remove(Object o)
    • 指定された要素の最初のオカレンスをこのリストから削除します。
    • 最初に要素を検索してから、シフト&可能なメモリサイズ変更コスト
    • に)

=== LinkedList ===

  • 加算(E e)

    • リストの最後に追加する
    • O(1)
  • add(int index、E element)

    • 指定された位置に挿入する
    • 最初にポジションを見つける必要がある
    • に)
  • remove()
    • リストの最初の要素を削除する
    • O(1)
  • remove(int index)
    • 指定されたインデックスの要素を削除する
    • 最初に要素を見つける必要がある
    • に)
  • remove(Object o)
    • 指定された要素の最初のオカレンスを削除する
    • 最初に要素を見つける必要がある
    • に)

次はprogramcreek.comprogramcreek.comaddremoveは最初のタイプです。つまり、リストの最後に要素を追加し、リスト内の指定された位置にある要素を削除します)。


ArrayList無作為にアクセスできますが、LinkedList要素を展開して削除するには本当に安いです。ほとんどの場合、問題ArrayListありません。

大きなリストを作成してボトルネックを測定した場合を除き、おそらくその違いについて心配する必要はありません。


現代のコンピュータアーキテクチャに起因するTL; DRはArrayList、ほぼあらゆる可能なユースケースに対してはるかに効率的であるためLinkedList、非常にユニークで極端な場合を除いて避けるべきである。

理論的には、LinkedListにはO(1)があります。 add(E element)

リストの途中に要素を追加することも非常に効率的です。

LinkedListはキャッシュ敵対的なデータ構造であるため、練習は非常に異なります。パフォーマンスPOVからLinkedListキャッシュフレンドリー よりもパフォーマンスが良いケースはごくわずかArrayListです。

ランダムな場所に要素を挿入するベンチマークテストの結果を以下に示します。あなたが見ることができるように - 理論的にはリストの真ん中にある各インサートは配列の後のn個の要素を"移動"する必要があります(より低い値が良い)。

後の世代のハードウェア(より大きい、より効率的なキャッシュ)で作業する - 結果はさらに決定的です:

LinkedListは、同じ仕事を達成するためにより多くの時間を要します。source コード

これには主に2つの理由があります。

  1. 主に - のノードがLinkedListランダムにメモリに散在していること。RAM(「ランダムアクセスメモリ」)は実際にランダムではなく、メモリのブロックをキャッシュにフェッチする必要があります。この操作には時間がかかります。そのようなフェッチが頻繁に発生すると、キャッシュ内のメモリページを常に交換する必要があります - >キャッシュミス - >キャッシュは効率的ではありません。ArrayList要素は連続的なメモリに格納されます。これはまさに最新のCPUアーキテクチャが最適化しているものです。

  2. セカンダリ LinkedListは、バック/フォワードポインタを保持する必要があります。これは、格納されている値の3倍のメモリ消費量を意味しArrayListます。

DynamicIntArray、btwは、IntObjectではなく(プリミティブ型)を保持するカスタムArrayList実装です。したがって、すべてのデータは実際には隣接して格納されるため、さらに効率的です。

覚えておくべき重要な要素は、メモリブロックをフェッチするコストが、単一メモリセルにアクセスするコストよりも重要であることです。そのため、1MBのシーケンシャルメモリは、異なるメモリブロックからこの量のデータを読み取る場合に比べて最大400倍高速です。

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

出典:すべてのプログラマーが知るべき待ち時間の数字

ポイントをさらに明確にするために、リストの先頭に要素を追加するベンチマークを確認してください。これは、理論上、LinkedList本当に輝くArrayListべきであり、悪いケースや悪いケースの結果を提示しなければならないユースケースです。

注:これはC ++ Stdライブラリのベンチマークですが、これまでのC ++とJavaの結果は非常によく似ています。 ソースコード

シーケンシャルなメモリのコピーは、最新のCPUによって最適化された操作です - 理論を変えて、実際には、もう一度ArrayList/ Vectorはるかに効率化します

クレジット:ここに掲載されたすべてのベンチマークはKjellHedströmによって作成されています。彼のブログでさらに多くのデータを見つけることができます


まとめ ArrayDequeを持つArrayListArrayDequeよりはるかに多くのユースケースで使用するのが望ましいArrayList 。 あなたがわからない場合は、 ArrayListから始めてください。

LinkedListArrayListは、Listインタフェースの2つの異なる実装ArrayListLinkedListはそれを二重リンクリストで実装します。 ArrayListは動的にサイズを変更する配列を実装しています。

標準のリンクリストと配列操作と同様に、さまざまなメソッドは異なるアルゴリズム実行時間を持ちます。

LinkedList<E>

  • get(int index)O(n) (平均でn / 4ステップ)
  • add(E element)O(1)です。
  • add(int index, E element)O(n) (平均でn / 4ステップ)であるが、 index = 0場合はO(1) <--- LinkedList<E>
  • remove(int index)O(n)です (平均でn / 4ステップ)
  • Iterator.remove()O(1)です。 <--- LinkedList<E>主な利点LinkedList<E>
  • ListIterator.add(E element)Oです(1)これはLinkedList<E>主な利点の1つです

注:多くの操作では、平均でn / 4ステップ、最良の場合は一定のステップ数(たとえばインデックス= 0)、最悪の場合はn / 2ステップ(リストの真ん中)

ArrayList<E>

  • get(int index) is O(1) <--- ArrayList<E>主な利点ArrayList<E>
  • add(E element)O(1)は償却されますが、配列のサイズ変更とコピーが必要なため、 O(n)は最悪です。
  • add(int index, E element)O(n) (平均でn / 2ステップ)
  • remove(int index)O(n) (平均でn / 2ステップ)
  • Iterator.remove()O(n) (平均でn / 2ステップ)
  • ListIterator.add(E element)O(n) (平均でn / 2ステップ)

注:多くの操作では、平均でn / 2ステップ、最善のケースでは一定のステップ数(リストの終わり)、最悪のケースではnステップ(リストの開始)

LinkedList<E>では、 イテレータを使用した定数の挿入または削除が可能ですが、要素の順次アクセスのみが可能です。 言い換えれば、リストを前後に歩くことができますが、リスト内の位置を見つけるには、リストのサイズに比例した時間がかかります。 Javadocによると、 「リストにインデックスを付ける操作は、リストの先頭から最後のいずれかが近づいていく」というのでO(n)n / 4ステップ) index = 0

一方、 ArrayList<E> 、ランダムな読み取りアクセスを高速に許可するため、一定の時間内に任意の要素を取得できます。 しかし、最後を除くどこからでも追加または削除するには、後者のすべての要素をシフトする必要があります。 また、元の配列の容量より多くの要素を追加すると、新しい配列(サイズの1.5倍)が割り当てられ、古い配列が新しい配列にコピーされるため、 ArrayList追加するのはO(n)です。最悪の場合でも平均的に一定である。

したがって、実行する操作に応じて、実装を適切に選択する必要があります。 いずれの種類のリストを反復することは、実質的に同等に安価です。 ( ArrayList反復するのは技術的に高速ArrayListが、実際にパフォーマンスを重視するものを実行しない限り、これについては心配する必要はありません - 両方とも定数です。)

LinkedListを使用する主な利点は、既存のイテレータを再利用して要素を挿入したり削除したりするときに発生します。 これらの操作は、ローカルでのみリストを変更することでO(1)で実行できます。 配列リストでは、配列の残りの部分を移動 (コピー)する必要があります。 一方、 LinkedListすることは、最悪の場合のO(n)n / 2ステップ)のリンクをLinkedListことを意味しますが、 ArrayListでは数学的に計算してO(1)でアクセスできます。

LinkedListを使用するもう1つの利点は、リストの先頭から追加または削除するときに発生します。これらの操作はO(1)でArrayList場合はO(n) ArrayListArrayDequeは、 LinkedListを追加したり削除したりするためのLinkedList良い代替手段ですが、 Listではありません。

また、大きなリストがある場合は、メモリ使用量も異なることに注意してください。 LinkedList各要素は、次の要素および前の要素へのポインタも格納されるため、より多くのオーバーヘッドを持ちます。 ArrayListsはこのオーバーヘッドはありません。 しかし、 ArrayListsは、要素が実際に追加されたかどうかに関わらず、容量に割り当てられた分のメモリをArrayListsます。

ArrayListのデフォルトの初期容量は非常に小さい(Java 1.4から1.8までは10)。 しかし、基になる実装は配列なので、たくさんの要素を追加する場合は、配列のサイズを変更する必要があります。 多くの要素を追加することがわかっているときにサイズ変更のコストが高くなるのを避けるために、より高い初期容量でArrayListを構築してください。



ええ、私は知っている、これは古代の質問ですが、私は私の2セントを投げます:

LinkedListはほとんどの場合 、パフォーマンス面では間違った選択です。 LinkedListが呼び出される非常に特殊なアルゴリズムがいくつかありますが、それらは非常にまれであり、アルゴリズムは通常、リンクされたリストの中にある要素を比較的早く挿入したり削除したりするLinkedListの機能に特に依存しますListIteratorを使って

LinkedListがArrayListよりも優れている一般的な使用例が1つあります。キューのものです。 しかし、あなたの目標がLinkedListの代わりにパフォーマンスである場合は、ArrayBlockingQueueを使用することを検討する必要があります(キューサイズの上限を前もって決定し、すべてのメモリを前もって割り当てることができる場合)、またはこのCircularArrayList実装 。 (はい、それは2001年のものなので、それを集める必要がありますが、最近のJVMの記事で引用されているものと同等のパフォーマンス比が得られます)


それはあなたがリスト上でもっと何をしているのかによって異なります。

ArrayList索引付けされた値にアクセスする方が高速です。オブジェクトを挿入したり削除したりするのはずっと悪いことです。

詳細については、配列とリンクリストの違いについて説明している記事を読んでください。


それは効率的な質問です。 LinkedListは要素の追加と削除は高速ですが、特定の要素へのアクセスは遅くなります。 ArrayListは特定の要素へのアクセスが高速ArrayListが、いずれかの端に追加するのが遅く、特に途中で削除するのが遅い場合があります。

配列vs ArrayList vs LinkedList vs Vectorは、 Linked Listと同様に深みを増しています。


正解または正しくない:テストをローカルで実行し、自分で決定してください!

編集/削除は、 ArrayListよりもLinkedListで高速ArrayList

ArrayによってサポートされたArrayListは、サイズが2倍である必要があり、大容量アプリケーションでは悪化します。

以下は各操作の単体テスト結果です。タイミングはナノ秒単位で与えられます。

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

コードは次のとおりです:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

私はレスポンスを読んだことがありますが、私が共有するArrayList上で常にLinkedListを使用して意見を聞くというシナリオがあります:

DBから取得したデータのリストを返すメソッドがあるたびに、私は常にLinkedListを使用します。

私の理論的根拠は、どれだけ多くの結果が得られたのかを知ることは不可能であるため、(ArrayListのように、要素の容量と実際の数が異なるため)メモリが無駄にならず、時間を無駄にすることはありません容量を複製する。

ArrayListまでは、できるだけ配列の重複を最小限に抑えるために、少なくとも初期容量で常にコンストラクタを使用する必要があることに同意します。



ArrayListの操作get(i)がLinkedListより高速です:
ArrayList: Listインタフェースの
サイズ変更可能な配列の実装LinkedList: ListおよびDequeインタフェースの二重リンクリストの実装

リストにインデックスを付けるオペレーションは、指定されたインデックスに近いほうから、リストの先頭または末尾を走査します。


remove()とinsert()の両方とも、ArrayListsとLinkedListの両方で実行時の効率がO(n)になります。しかしながら、線形処理時間の背後にある理由は、2つの全く異なる理由から生じる。

ArrayListでは、O(1)の要素に到達しますが、実際には次の要素を変更する必要があるため、何かを削除または挿入するとO(n)になります。

LinkedListでは、目的の要素に実際に到達するためにはO(n)が必要です。なぜなら、最初から必要なインデックスに達するまで開始する必要があるからです。実際に取り除くか挿入するかどうかは、remove()の参照を1つだけ変更し、insert()の参照を2つ変更するだけで済むためです。

どちらの方が挿入と取り出しの方が速いかは、どこで発生するかによって異なります。私たちが最初に近づくと、比較的少数の要素を通らなければならないのでLinkedListはより速くなります。我々が終わりに近づくと、ArrayListはより速くなります。というのも、一定の時間内にそこに到達し、それに続く残りの要素をいくつか変更するだけで済むからです。真ん中で正確に行われると、n個の要素を通過するのがn個の値を移動するよりも速いので、LinkedListは高速になります。

ボーナス:ArrayListに対してこれら2つのメソッドO(1)を作成する方法はありませんが、LinkedListsでこれを行う方法が実際にあります。List全体を削除して要素を途中で挿入したいとしましょう。通常、LinkedListを使用して各要素の最初から開始しますが、作業中の現在の要素をIteratorで「保存」することもできます。Iteratorの助けを借りて、LinkedListで作業しているときにremove()とinsert()の効率をO(1)にします。これを唯一のパフォーマンス上のメリットにするために、私はLinkedListがArrayListより常に優れていることを認識しています。


あなたのコードにadd(0)とがあるなら、それをremove(0)使用してくださいLinkedList、それはよりきれいでaddFirst()removeFirst()方法です。そうでない場合は、使用ArrayList

もちろん、GuavaImmutableListはあなたの親友です。


リンクされたリスト(私が別の答えで読まなかった)の重要な特徴は、2つのリストの連結です。配列ではこれはO(n)(いくつかの再割り当てのオーバーヘッド)であり、リンクされたリストではこれはO(1)またはO(2)のみです;-)

重要:Javaの場合、LinkedListこれは当てはまりません!Javaでリンクされたリストの高速concatメソッドがありますか?を参照してください。


上の他の良い議論に加えて、あなたはArrayList実装している間、RandomAccessインターフェースをLinkedList実装することに気づくべきQueueです。

だから、どういうわけか、少しずつ異なる問題に対処し、効率と行動の違い(メソッドのリストを参照)。


私はこれが古い投稿だと知っていますが、私は正直言って、誰もそのLinkedList実装について言及したとは信じられませんDequeDeque(とQueue)のメソッドを見てみましょう。公正な比較が必要な場合は、機能比較のために実行LinkedListしてみてくださいArrayDeque


配列リストは基本的にはアイテムなどを追加するメソッドを持つ配列です(代わりに汎用リストを使用する必要があります)。これは、インデクサー(たとえば[0])を介してアクセスできるアイテムの集合です。それはある項目から次の項目への進展を意味する。

リンクされたリストは、ある項目から次の項目への進行を指定します(項目a - >項目b)。あなたは配列リストで同じ効果を得ることができますが、リンクされたリストは絶対にどの項目が前のものに従うと言われているかを示します。





linked-list