私はいつも単純に使用する人でした：
List<String> names = new ArrayList<>();
portabilityの型名として interface を使用しているので、このような質問をしたときにコードを書き直すことができます。
逆にいつLinkedList使用する必要がありますか?ArrayList
sdellysse
質問する
1251850 次
33 に答える
3707
を使用したサマリー ArrayListは、 よりも多くのユースケースでArrayDeque推奨されます。よくわからない場合は、 から始めてください。LinkedListArrayList
TLDR、ArrayList では、要素へのアクセスに一定の時間 [O(1)] がかかり、要素の追加には O(n) の時間 [最悪の場合] がかかります。LinkedList では、要素の追加に O(n) 時間、アクセスにも O(n) 時間がかかりますが、LinkedList は ArrayList より多くのメモリを使用します。
LinkedListとArrayListは List インターフェイスの 2 つの異なる実装です。LinkedList二重にリンクされたリストでそれを実装します。ArrayList動的にサイズ変更する配列で実装します。
標準のリンクされたリストおよび配列操作と同様に、さまざまなメソッドには異なるアルゴリズム ランタイムがあります。
get(int index)はO(n) (平均n/4ステップ) ですが、 orの場合はO(1) (この場合、andも使用できます)。の主な利点の 1 つindex = 0index = list.size() - 1getFirst()getLast()LinkedList<E>add(int index, E element)はO(n) (平均n/4ステップ) ですが、またはの場合はO(1) (この場合、and /も使用できます)。の主な利点の 1 つindex = 0index = list.size() - 1addFirst()addLast()add()LinkedList<E>remove(int index)はO(n) (平均n/4ステップ) ですが、 orの場合はO(1) (この場合、andも使用できます)。の主な利点の 1 つindex = 0index = list.size() - 1removeFirst()removeLast()LinkedList<E>Iterator.remove()はO(1)です。の主な利点の 1 つLinkedList<E>ListIterator.add(E element)はO(1)です。の主な利点の 1 つLinkedList<E>
注: 操作の多くは、平均でn/4ステップ、最良の場合 (例: インデックス = 0) では一定数のステップ、最悪の場合 (リストの中央) ではn/2ステップを必要とします。
get(int index)はO(1)です。主なメリット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>iterators を使用した一定時間の挿入または削除が可能ですが、要素の順次アクセスのみが可能です。つまり、リストを前後に移動できますが、リスト内の位置を見つけるには、リストのサイズに比例して時間がかかります。Javadoc は、「リストにインデックスを付ける操作は、リストの先頭または末尾のどちらか近い方からトラバースする」と述べているため、これらのメソッドは平均でO(n) ( n/4ステップ) ですが、 の場合はO(1)ですindex = 0。
ArrayList<E>一方、高速ランダム読み取りアクセスを許可するため、任意の要素を一定時間で取得できます。しかし、最後以外のどこからでも追加または削除するには、開口部を作成するかギャップを埋めるために、後者のすべての要素を移動する必要があります。また、元の配列の容量よりも多くの要素を追加すると、新しい配列 (サイズの 1.5 倍) が割り当てられ、古い配列が新しい配列にコピーされるため、 an への追加ArrayListは最悪でO(n)になります。ケースですが、平均的には一定です。
したがって、実行する操作に応じて、それに応じて実装を選択する必要があります。どちらの種類のリストを反復しても、実際には同じように安価です。( を繰り返し処理するArrayList方が技術的に高速ですが、パフォーマンスが非常に重要な場合を除き、これについて心配する必要はありません。どちらも定数です。)
a を使用する主な利点は、LinkedList既存の反復子を再利用して要素を挿入および削除する場合に生じます。これらの操作は、リストをローカルでのみ変更することにより、 O(1)で実行できます。配列リストでは、配列の残りの部分を移動(コピー)する必要があります。一方、最悪の場合はO(n) ( n/2LinkedListステップ)のリンクをたどる手段でシークしますが、目的の位置は数学的に計算してO(1)でアクセスできます。ArrayList
LinkedListリストの先頭に追加または削除すると、 a を使用する別の利点が生じます。これは、これらの操作がO(1)であるのに対し、 の場合はO(n)であるためArrayListです。は、頭に追加したり頭から削除したりするためArrayDequeの良い代替手段かもしれませんが、 .LinkedListList
また、リストが大きい場合は、メモリ使用量も異なることに注意してください。a の各要素にはLinkedList、次の要素と前の要素へのポインターも格納されるため、オーバーヘッドが大きくなります。ArrayListsこのオーバーヘッドはありません。ただし、ArrayLists要素が実際に追加されたかどうかに関係なく、容量に割り当てられているだけのメモリを占有します。
のデフォルトの初期容量ArrayListはかなり小さいです (Java 1.4 - 1.8 では 10)。ただし、基礎となる実装は配列であるため、多数の要素を追加する場合は配列のサイズを変更する必要があります。多くの要素を追加することがわかっている場合にサイズ変更の高コストを回避するにはArrayList、より高い初期容量で を構築します。
データ構造の観点を使用して 2 つの構造を理解する場合、LinkedList は基本的に、ヘッド ノードを含む順次データ構造です。Node は 2 つのコンポーネントのラッパーです。タイプ T の値 [ジェネリックを通じて受け入れられる] と、それにリンクされた Node への別の参照です。したがって、再帰的なデータ構造であると断言できます (ノードには、別のノードを持つ別のノードが含まれます...)。前述のように、LinkedList では要素の追加に線形時間がかかります。
ArrayList は拡張可能な配列です。通常の配列と同じです。フードの下では、要素が追加され、ArrayList が既に容量いっぱいになると、以前のサイズよりも大きいサイズの別の配列が作成されます。次に、要素が前の配列から新しい配列にコピーされ、追加される要素も指定されたインデックスに配置されます。
于 2008-11-27T01:49:42.357 に答える
671
LinkedListこれまでのところ、aは「はるかに多い」という一般的なコンセンサス以外に、これらの各リストのメモリフットプリントに取り組んだ人はいないようです。ArrayListそのため、両方のリストがN個のnull参照にどれだけかかるかを正確に示すために、いくつかの数値計算を行いました。
参照は相対システムで32ビットまたは64ビット（nullの場合でも）であるため、32ビットと64ビットLinkedListsおよびの4セットのデータを含めArrayListsました。
注：ArrayList行に示されているサイズは、トリミングされたリストのものです-実際には、のバッキング配列の容量は、ArrayList通常、現在の要素数よりも大きくなります。
注2: (BeeOnRopeに感謝） CompressedOopsはJDK6の半ば以降のデフォルトであるため、64ビットマシンの以下の値は、もちろん特にオフにしない限り、基本的に32ビットのマシンと一致します。
結果は、特に要素数が非常に多い場合に、LinkedListそれがをはるかに上回っていることを明確に示しています。ArrayListメモリが要因である場合は、を避けてLinkedListsください。
私が使用した式は次のとおりです。何か間違ったことをした場合はお知らせください。修正します。'b'は32ビットまたは64ビットシステムの場合は4または8であり、'n'は要素の数です。modsの理由は、Javaのすべてのオブジェクトが、すべて使用されているかどうかに関係なく、8バイトの倍数のスペースを占めるためです。
配列リスト：
ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)
LinkedList：
LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
于 2011-10-06T06:46:45.893 に答える
283
ArrayListあなたが望むものです。LinkedListほとんどの場合、(パフォーマンス) バグです。
なぜLinkedListひどい：
- 多数の小さなメモリ オブジェクトを使用するため、プロセス全体のパフォーマンスに影響を与えます。
- 小さなオブジェクトがたくさんあると、キャッシュの局所性が低下します。
- インデックス操作にはトラバーサルが必要です。つまり、O(n) のパフォーマンスがあります。これはソースコードでは明らかではなく、アルゴリズム O(n)
ArrayListが使用された場合よりも遅くなります。 - 良いパフォーマンスを得るのは難しいです。
- big-O のパフォーマンスが と同じ場合でも、
ArrayListとにかく大幅に遅くなる可能性があります。 LinkedListおそらく間違った選択であるため、ソースで見るのは耳障りです。
于 2008-11-27T14:20:16.133 に答える
169
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
アルゴリズム：Big-Oh表記（アーカイブ）
ArrayListsは、write-once-read-manyまたはappendersには適していますが、フロントまたはミドルからの追加/削除には適していません。
于 2010-04-08T20:33:35.467 に答える
153
約 10 年間、非常に大規模な SOA Web サービスで運用パフォーマンス エンジニアリングを行ってきた者として、ArrayList よりも LinkedList の動作を好みます。LinkedList の定常状態のスループットは悪化するため、ハードウェアの追加購入につながる可能性がありますが、プレッシャー下での ArrayList の動作により、クラスター内のアプリがほぼ同期して配列を拡張する可能性があり、配列サイズが大きい場合は応答性が低下する可能性があります。アプリと停止、プレッシャー下での破滅的な行動です。
同様に、デフォルトのスループットの Tenured ガベージ コレクターからアプリのスループットを向上させることができますが、10 GB ヒープの Java アプリを取得すると、フル GC 中にアプリが 25 秒間ロックされ、SOA アプリでタイムアウトや障害が発生する可能性があります。頻繁に発生する場合は、SLA を吹き飛ばします。CMS コレクターはより多くのリソースを使用し、同じ生スループットを達成しませんが、より予測可能で待ち時間が短いため、はるかに優れた選択肢です。
ArrayList は、パフォーマンスがスループットのみを意味し、レイテンシを無視できる場合にのみ、パフォーマンスに適した選択肢です。私の仕事での経験では、最悪の場合のレイテンシーを無視することはできません。
更新 (2021 年 8 月 27 日 -- 10 年後): この回答 (SO に関する私の最も歴史的に支持された回答) は、おそらく間違っています (以下のコメントで概説されている理由により)。ArrayList はメモリのシーケンシャル読み取りを最適化し、キャッシュラインや TLB ミスなどを最小限に抑えることを付け加えたいと思います。配列が境界を超えて大きくなったときのコピーのオーバーヘッドは、比較すると取るに足らないものである可能性があります (効率的な CPU 操作によって行うことができます)。 ）。ハードウェアの傾向を考えると、この答えはおそらく時間の経過とともに悪化しています。LinkedList が意味を成す唯一の状況は、何千ものリストがあり、そのうちのいずれかが GB サイズになる可能性があるが、リストの割り当て時に適切な推測を行うことができず、それらを設定できないような非常に工夫されたものです。すべてを GB サイズにすると、ヒープが爆発します。そして、そのような問題が見つかった場合は、解決策が何であれ、リエンジニアリングが必要です (そして、私自身が古いコードの山と山を維持しているため、古いコードのリエンジニアリングを軽く提案するのは好きではありませんが、それは元のデザインが単に滑走路を使い果たし、チャックする必要がある場合の非常に良いケース)。私は何十年も前の私の悪い意見をまだそこに残しておきますが、あなたが読むことができます. シンプルで論理的で、かなり間違っています。ただし、何十年も前の私の貧弱な意見はまだ残しておきますが、読んでください。シンプルで論理的で、かなり間違っています。ただし、何十年も前の私の貧弱な意見はまだ残しておきますが、読んでください。シンプルで論理的で、かなり間違っています。
于 2011-01-01T20:23:52.100 に答える
117
ええ、私は知っています、これは昔からの質問ですが、私は 2 セントを投入します:
LinkedList は、ほとんどの場合、パフォーマンスに関して間違った選択です。LinkedList が呼び出される非常に特殊なアルゴリズムがいくつかありますが、それらは非常にまれであり、アルゴリズムは通常、そこに移動すると、リストの途中で要素を比較的迅速に挿入および削除する LinkedList の機能に特に依存します。 ListIterator を使用します。
LinkedList が ArrayList よりも優れている一般的な使用例が 1 つあります。それは、キューの使用です。ただし、目標がパフォーマンスである場合は、LinkedList の代わりに ArrayBlockingQueue の使用を検討する必要があります (事前にキュー サイズの上限を決定でき、事前にすべてのメモリを割り当てる余裕がある場合)、またはこのCircularArrayList 実装. (はい、2001 年のものなので、一般化する必要がありますが、最近の JVM で、記事で引用されているものに匹敵するパフォーマンス比を得ました)
于 2009-05-19T11:21:20.293 に答える
93
LinkedList の作成者である Joshua Bloch 氏は、次のように述べています。
実際に LinkedList を使っている人はいますか? 私はそれを書きましたが、私はそれを決して使用しません。
リンク：https ://twitter.com/joshbloch/status/583813919019573248
回答が他の回答ほど有益でなくて申し訳ありませんが、明らかにならない限り、それが最も自明だと思いました。
于 2017-03-01T10:47:43.927 に答える
79
効率の問題です。LinkedList要素の追加と削除は高速ですが、特定の要素へのアクセスは低速です。ArrayList特定の要素へのアクセスは高速ですが、両端への追加は遅く、特に途中での削除は遅くなります。
Array vs ArrayList vs LinkedList vs Vectorは、 Linked Listと同様に、より詳細に説明します。
于 2008-11-27T01:39:59.897 に答える
57
正誤: ローカルでテストを実行し、自分で判断してください!
の編集/削除は より高速LinkedListですArrayList。
ArrayListに裏打ちされたArray、これは 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);
}
}
于 2011-09-21T22:59:23.773 に答える
36
ArrayListランダムにアクセスできますが、LinkedList要素を展開して削除するのは非常に安価です。ほとんどの場合、ArrayList問題ありません。
大規模なリストを作成してボトルネックを測定したことがない限り、おそらく違いを気にする必要はありません。
于 2008-11-27T01:41:47.740 に答える
25
コードにadd(0)andがある場合は、 aをremove(0)使用してください。それ以外の場合は、 を使用します。LinkedListaddFirst()removeFirst()ArrayList
そしてもちろん、GuavaのImmutableListはあなたの親友です。
于 2008-11-28T02:04:15.433 に答える
22
これが古い投稿であることは知っていますが、正直なところ、LinkedList実装について誰も言及していないとは信じられませんDeque。Deque(およびQueue)のメソッドを見てください。公平な比較が必要な場合は、実行LinkedListしArrayDequeて機能ごとの比較を行ってください。
于 2013-04-19T07:26:48.140 に答える
20
ArrayListandLinkedListと alsoの Big-O 表記は次のCopyOnWrite-ArrayListとおりです。
配列リスト
get O(1)
add O(1)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
リンクされたリスト
get O(n)
add O(1)
contains O(n)
next O(1)
remove O(1)
iterator.remove O(1)
CopyOnWrite-ArrayList
get O(1)
add O(n)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
これらに基づいて、何を選択するかを決定する必要があります。:)
于 2012-11-06T14:32:08.023 に答える
15
上記の他の適切な引数に加えて、ArrayListimplementsRandomAccessインターフェースがLinkedList実装されていることに注意してくださいQueue。
したがって、どういうわけか、効率と動作の違いにより、わずかに異なる問題に対処します (メソッドのリストを参照してください)。
于 2008-11-27T01:47:34.280 に答える
11
それは、リストでさらにどのような操作を行うかによって異なります。
ArrayListインデックス付きの値にアクセスする方が高速です。オブジェクトを挿入または削除するときはさらに悪化します。
詳細については、配列と連結リストの違いについて説明している記事を読んでください。
于 2008-11-27T01:42:03.217 に答える
9
Java チュートリアル - リストの実装を参照してください。
于 2011-09-05T06:33:52.753 に答える
9
配列リストは基本的に、項目などを追加するメソッドを含む配列です (代わりに汎用リストを使用する必要があります)。これは、インデクサー ([0] など) を介してアクセスできるアイテムのコレクションです。これは、ある項目から次の項目への進行を意味します。
リンクされたリストは、あるアイテムから次のアイテムへの進行を指定します (アイテム a -> アイテム b)。配列リストでも同じ効果が得られますが、連結リストは、前の項目の後にどの項目が続くべきかを絶対に示します。
于 2010-04-20T15:32:01.660 に答える
8
リンクされたリストの重要な機能 (別の回答では読みませんでした) は、2 つのリストの連結です。配列の場合、これは O(n) (+ 一部の再割り当てのオーバーヘッド) であり、リンクされたリストの場合、これは O(1) または O(2) のみです;-)
重要: Java の場合、LinkedListこれは正しくありません。Java でリンクされたリストの高速な concat メソッドはありますか? を参照してください。
于 2010-03-22T22:32:31.243 に答える
6
応答を読みましたが、意見を聞くために共有したいArrayListに対してLinkedListを常に使用するシナリオが1つあります。
DBから取得したデータのリストを返すメソッドがあるたびに、常にLinkedListを使用します。
私の理論的根拠は、取得している結果の数を正確に知ることは不可能であるため、メモリが無駄になることはなく（ArrayListのように、容量と実際の要素数の違いがあるため）、時間を無駄にすることはないということでした。容量を複製します。
ArrayListに関しては、配列の重複を可能な限り最小限に抑えるために、少なくとも初期容量のコンストラクターを常に使用する必要があることに同意します。
于 2011-10-03T23:23:00.370 に答える
5
ArrayListLinkedList両方の実装とList interface その方法と結果はほとんど同じです。ただし、要件に応じて、それらの間にいくつかの違いがあり、一方が他方よりも優れています。
ArrayList 対 LinkedList
1)Search: ArrayList検索操作は、検索操作に比べてかなり高速LinkedListです。get(int index)inArrayListは のパフォーマンスを与えますが、O(1)パフォーマンスLinkedListは ですO(n)。
Reason: ArrayListリスト内の要素の検索を高速化する配列データ構造を暗黙的に使用するため、要素のインデックスベースのシステムを維持します。反対側LinkedListでは、要素を検索するためにすべての要素を走査する必要がある双方向リンク リストを実装します。
2) Deletion: LinkedListremove 操作はO(1)パフォーマンスを向上させますが、パフォーマンスArrayListは変動します:O(n)最悪の場合 (最初の要素を削除している間) とO(1)最良の場合 (最後の要素を削除している間)。
結論: LinkedList 要素の削除は、ArrayList に比べて高速です。
理由: LinkedList の各要素は、リスト内の両方の隣接要素を指す 2 つのポインター (アドレス) を維持します。したがって、削除するには、削除しようとしているノードの 2 つの隣接ノード (要素) のポインター位置を変更するだけで済みます。ArrayList では、削除された要素によって作成されたスペースを埋めるために、すべての要素をシフトする必要があります。
3)Inserts Performance: LinkedListメソッドを追加するとO(1)パフォーマンスが向上しArrayListますがO(n)、最悪の場合はパフォーマンスが低下します。理由は削除の説明と同じです。
4)要素データと隣接ノードの 2 つのポインターを維持しMemory Overhead: ArrayListながら、インデックスと要素データを維持します。LinkedList
したがって、LinkedList では比較的メモリ消費量が多くなります。
これらのクラスには、次のようないくつかの類似点があります。
- ArrayList と LinkedList はどちらも List インターフェイスの実装です。
- どちらも要素の挿入順序を維持します。つまり、ArrayList 要素と LinkedList 要素を表示している間、結果セットは、要素がリストに挿入された順序と同じになります。
- これらのクラスは両方とも非同期であり、Collections.synchronizedList メソッドを使用して明示的に同期することができます。
- これらのクラスによって返される と は次のとおりです
iterator(イテレータが作成された後、独自の remove メソッドまたは add メソッド以外の方法でリストが構造的に変更された場合、イテレータは になります)。listIteratorfail-fastiterator’sthrowConcurrentModificationException
LinkedList をいつ使用し、いつ ArrayList を使用するか?
- 上で説明したように、挿入操作と削除操作
(O(1))は にLinkedList比べて優れたパフォーマンスを発揮しArrayList(O(n))ます。したがって、アプリケーションで頻繁に追加および削除する必要がある場合は、LinkedList が最適です。
- 検索 (
get method) 操作は高速ですArraylist (O(1))が、高速ではありませんLinkedList (O(n))そのため、追加操作と削除操作が少なく、検索操作の要件が多い場合は、ArrayList が最適です。
于 2016-11-02T09:00:23.477 に答える
3
remove()ArrayListsとinsert()LinkedLists の両方で O(n) の実行効率があります。ただし、直線的な処理時間の背後にある理由は、次の 2 つのまったく異なる理由によるものです。
ArrayList では O(1) の要素に到達しますが、実際に何かを削除または挿入すると O(n) になります。これは、後続のすべての要素を変更する必要があるためです。
LinkedList では、目的のインデックスに到達するまで最初から開始する必要があるため、実際に目的の要素に到達するには O(n) かかります。remove()の 1 つの参照と の 2 つの参照のみを変更する必要があるため、実際の削除または挿入は一定ですinsert()。
挿入と削除のどちらが速いかは、それがどこで発生するかによって異なります。最初に近づくと、比較的少数の要素を通過する必要があるため、LinkedList は高速になります。最後に近づくと、ArrayList はより高速になります。これは、定数時間でそこに到達し、それに続くいくつかの残りの要素を変更するだけでよいためです。n 個の要素を通過する方が n 個の値を移動するよりも速いため、正確に真ん中で行うと、LinkedList はより高速になります。
おまけ: これら 2 つのメソッドを ArrayList に対して O(1) にする方法はありませんが、実際には LinkedLists でこれを行う方法があります。途中で要素を削除および挿入しながら、リスト全体を調べたいとしましょう。通常、LinkedList を使用して各要素の最初から開始します。また、Iterator を使用して作業中の現在の要素を「保存」することもできます。Iterator の助けを借りて、LinkedList で作業するときremove()のO(1) 効率が得られます。insert()LinkedList が常に ArrayList よりも優れていることを認識している唯一のパフォーマンス上の利点です。
于 2016-06-11T20:40:29.867 に答える
-2
いつ使用する必要がありますLinkedListか? 主にスタックを操作する場合、またはバッファを操作する場合。いつ使用する必要がありますArrayListか? インデックスを操作する場合のみ、それ以外の場合は、リンクされたリストで HashTable を使用できます。次のようになります。
ハッシュテーブル＋連結リスト
- キーO(1) によるアクセス、
- キーO(1) で挿入、
- キーO(1)で削除
- バージョン管理を使用する場合、 O(1) で RemoveAll / SetAll を実装するトリックがあります
これは良い解決策のように思えますが、ほとんどの場合、HashTable は大量のディスク容量を必要とするため、1,000,000 個の要素リストを管理する必要がある場合に重要になります。これはサーバーの実装で発生する可能性がありますが、クライアントではめったに発生しません。
Red-Black-Treeもご覧ください
- ランダム アクセスログ(n)、
- ログを挿入(n)、
- ログを削除(n)
于 2012-06-11T09:08:06.680 に答える