36

たとえば、Javaリストの「名前」など、大量の情報を保存する必要があります。アイテムの数は変更できます (つまり、サイズを事前に定義することはできません)。私は、メモリ割り当ての観点から、LinkedList は ArrayList よりも優れたオプションであると考えています。ArrayList については、最大サイズに達すると自動的にメモリ割り当てが 2 倍になるため、常により多くのメモリが割り当てられる可能性があります。必要なもの。

ここの他の投稿から、LinkedList にはノード情報も格納する必要があるため、LinkedList に格納されている個々の要素は ArrayList よりも多くのスペースを必要とすることを理解していますが、LinkedList を定義したシナリオでは、より良いオプションである可能性があると推測しています。また、パフォーマンスの側面 (フェッチ、削除など) については、既に多くのことが議論されているので、ここでは触れたくありません。

4

5 に答える 5

66

LinkedListより少ないエントリを割り当てる可能性がありますが、それらのエントリは実際よりも天文学的に高価です。メモリに関する限りArrayList、最悪の場合でも安価です。ArrayList

（参考までに、あなたはそれを間違っていると思います。ArrayListいっぱいになると2倍ではなく1.5倍になります。）

例を参照してください https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt :LinkedList要素ごとに 24 バイトをArrayList消費しますが、最良の場合は要素ごとに 4 バイト、最悪の場合は要素ごとに 6 バイトを消費します。 . (結果は、32 ビットと 64 ビットの JVM、および圧縮されたオブジェクト ポインター オプションによって異なる場合がありますが、これらの比較ではLinkedList要素あたり少なくとも 36 バイトのコストがかかり、ArrayList最高で 8、最悪で 12 です。)

アップデート：

ここの他の投稿から、LinkedList に格納されている個々の要素は ArrayList よりも多くのスペースを必要とすることを理解しています。また、パフォーマンスの側面 (フェッチ、削除など) については、既に多くのことが議論されているので、ここでは触れたくありません。

明確にするために、最悪の場合でも、は同じ要素のArrayListよりも 4 倍小さいです。LinkedList勝つための唯一の可能な方法LinkedListは、意図的に膨らませた値で呼び出して比較を意図的に修正するか、追加されensureCapacityた後に多くの値を削除することです。ArrayList

要するに、メモリ比較で勝つことは基本的に不可能LinkedListであり、スペースを気にする場合は、 を呼び出すtrimToSize()とArrayListすぐにArrayList再び大きな差で勝つことができます。真剣に。 ArrayList勝つ。

于 2012-07-19T15:44:34.800 に答える
6

...しかし、私が定義したシナリオについては、LinkedListがより良いオプションである可能性があるとまだ推測しています

あなたの推測は間違っています。

配列リストの初期容量を超えると、バッキングのサイズは 1 ～ 2 参照×エントリ数になります。これは、バッキング アレイを拡張するために使用される戦略によるものです。

リンクされたリストの場合、各ノードにはエントリ参照と同様にnextand参照があるため、各ノードはエントリ数の少なくとも 3 倍を占有します。prev(実際には、ノードのオブジェクト ヘッダーとパディングによって使用されるスペースのため、3 倍以上になります。JVM とポインターのサイズによっては、6 倍にもなる可能性があります。)

リンクされたリストが配列リストよりも少ないスペースを使用する唯一の状況は、配列リストの初期容量をひどく過大評価した場合です。（そして非常に小さなリストの場合...）

考えてみると、連結リストが配列リストより優れている唯一の真の利点は、要素を挿入および削除するときです。その場合でも、やり方次第です。

于 2012-07-19T15:45:52.987 に答える
4

ArrayList は、オブジェクトごとに 1 つの参照を使用します (必要なサイズの 2 倍の場合は 2 つ)。これは通常 4 バイトです。

LinkedList は必要なノードのみを使用しますが、これらはそれぞれ 24 バイトになる場合があります。

したがって、最悪の場合でも、ArrayList は LinkedList よりも 3 倍小さくなります。

ARrayList の取得では、ランダム アクセス O(1) をサポートしていますが、LinkedList は O(n) です。最後から削除する場合は両方とも O(1)、途中から削除する場合は ArrayList は O(n) です。

何百万ものエントリがない限り、コレクションのサイズは問題になりません。最初に問題になるのは、使用されるコレクションに関係なく同じエントリのサイズです。

于 2012-07-19T15:44:04.767 に答える
3

封筒の裏の最悪の場合:

1,000,000 のサイズの配列に 500,000 個の名前 = 500,000 個が使用され、割り当てられた配列の未使用部分に 500,000 個の空のポインター。

リンクされたリスト内の 500,000 エントリ = エントリごとに 3 つのポインター (Node オブジェクトは現在、前、および次を保持) = メモリ内の 1,5000,000 ポインター。(次に、ノード自体のサイズを追加する必要があります)

于 2012-07-19T15:47:05.017 に答える
3

ArrayList.trimToSize()はあなたを満足させるかもしれません。

リストの現在のサイズになるように、この ArrayList インスタンスの容量をトリミングします。アプリケーションは、この操作を使用して、ArrayList インスタンスのストレージを最小限に抑えることができます。

ちなみにArrayList Java6では2倍の容量ではなく、最大サイズの1.5倍程度です。

于 2012-07-19T15:43:15.787 に答える