217

Java の ArrayDeque が Java の LinkedList よりも優れている理由を理解しようとしています。どちらも Deque インターフェイスを実装しているためです。

コードで ArrayDeque を使用している人をほとんど見かけません。誰かが ArrayDeque の実装方法にさらに光を当てると、役に立ちます。

理解できれば、自信を持って使えます。JDK の実装での head 参照と tail 参照の管理方法がよくわかりませんでした。

4

9 に答える 9

203

リンクされた構造は、各要素でキャッシュ ミスを繰り返す最悪の構造である可能性があります。その上、より多くのメモリを消費します。

両端の追加/削除が必要な場合、ArrayDeque はリンクされたリストよりもはるかに優れています。巡回キューの場合、ランダム アクセスの各要素も O(1) です。

リンクされたリストの唯一の優れた操作は、反復中に現在の要素を削除することです。

于 2011-05-28T17:23:34.073 に答える
29

ArrayDequeは Java 6 の新機能です。そのため、多くのコード (特に、以前の Java バージョンとの互換性を維持しようとするプロジェクト) で使用されていません。

挿入するアイテムごとにノードを割り当てていないため、場合によっては「より良い」です。代わりに、すべての要素が巨大な配列に格納され、いっぱいになるとサイズが変更されます。

于 2011-05-28T17:18:29.183 に答える
21

ArrayDequeとLinkedListはDequeインターフェイスを実装していますが、実装が異なります。

主な違い:

  1. ArrayDequeクラスはDequeインターフェイスのサイズ変更可能な配列実装であり、LinkedListクラスはリスト実装です。

  2. NULL 要素は LinkedList に追加できますが、ArrayDequeには追加できません

  3. ArrayDequeは、両端での追加および削除操作に関して LinkedListよりも効率的であり、LinkedList 実装は、反復中に現在の要素を削除するために効率的です。

  4. LinkedListの実装は、ArrayDequeよりも多くのメモリを消費します

したがって、NULL 要素をサポートする必要がない場合 && より少ないメモリを探す && 両端で要素を追加/削除する効率が高い場合は、ArrayDequeが最適です

詳細については、ドキュメントを参照してください。

于 2015-09-18T07:29:26.780 に答える
1

ArrayDeque<E>とLinkedList<E>は両方とも Interface を実装 していDeque<E>ますが、ArrayDeque は基本的に Object 配列E[]を使用して Object 内に要素を保持するため、通常は index を使用して head 要素と tail 要素を見つけます。

つまり、Deque と同じように (すべて Deque のメソッドを使用して) 動作しますが、配列のデータ構造を使用します。どちらが優れているかは、使い方と場所によって異なります。

于 2015-02-07T02:12:53.223 に答える
1

ArrayDequeよりも優れているとは思いませんLinkedList。それらは違う。

ArrayDequeLinkedList平均より速いです。ただし、要素を追加するには、ArrayDeque償却一定の時間がLinkedListかかり、一定の時間がかかります。

すべての操作に一定の時間がかかる必要がある、時間に敏感なアプリケーションの場合は、のみLinkedListを使用する必要があります。

ArrayDequeの実装は配列を使用し、サイズ変更が必要です。また、配列がいっぱいで要素を追加する必要がある場合、サイズ変更に線形時間がかかり、結果としてadd()メソッドに線形時間がかかります。アプリケーションが非常に時間に敏感な場合、これは大惨事になる可能性があります。

Java の 2 つのデータ構造の実装に関するより詳細な説明は、Wayne と Sedgewick が教えるプリンストン大学が提供する Courseraの「アルゴリズム、パート I 」コースで利用できます。コースは無料で公開されています。

詳細は、「第 2 週」の「スタックとキュー」セクションのビデオ「Resizing Arrays」で説明されています。

于 2021-11-16T18:08:37.073 に答える
-6

要素にアクセスするための ArrayDeque の時間計算量は O(1) で、最後の要素にアクセスするための LinkList の時間計算量は O(N) です。ArrayDeque はスレッドセーフではないため、複数のスレッドを介してアクセスできるように手動で同期する必要があり、高速になります。

于 2015-09-21T07:02:09.013 に答える