0

ここで、Java で ArrayLists と LinkedLists を使用するコストについて議論するかなりの数の質問を読みました。これまでに見た中で最も便利なものの 1 つは、次のとおりです。.

正しく理解していることを確認したい。

私の現在の使用例では、List 構造にオブジェクトが格納されている状況が複数あります。リスト内のオブジェクトの数は実行ごとに変化し、リスト内のオブジェクトへのランダム アクセスは必要ありません。この情報に基づいて、LinkedLists を ListIterators と共に使用して、リストのコンテンツ全体をトラバースすることにしました。

たとえば、私のコードは次のようになります。

for (Object thisObject : theLinkedList) {
    // do something
}

これが悪い選択である場合は、その理由を理解するのを手伝ってください。

私の現在の理解では、LinkedList 内のオブジェクトのリスト全体をトラバースすると、反復ソリューションを使用して O(n) コストが発生します。リストへのランダム アクセスがないため (たとえば、アイテム #3 を取得する必要がある)、これは基本的に ArrayList の内容をループして各要素にインデックスを要求することと同じであると私は理解しています。

リストに格納するオブジェクトの数を事前に知っていたと仮定すると、現在の考えでは、ArrayList を適切なサイズに初期化し、ListIterator を使用せずにその構造に完全に切り替える方がよいでしょう。この論理は健全ですか？

いつものように、私は皆さんの意見にとても感謝しています!

4

1 に答える 1

0

いずれの場合も、ある要素から次の要素へのステップのコストは一定であるため、a の反復は完了するまでLinkedListにほぼ同じ時間がかかるはずです。ただし、参照の局所性が原因で少し良くなる可能性があるため、プロファイリングして何が起こるかを確認する価値があるかもしれませんArrayList.ArrayList

常に固定数の要素が存在し、ランダムな場所で挿入や削除が行われないことが保証されている場合は、生の配列が適切な選択になる可能性があります。

とはいえ、使用する理由の分析は適切にLinkedList思えます。繰り返しますが、プログラムのArrayListプロファイリングを行って、ユースケースで実際に高速になるかどうかを確認することは問題ありません。

お役に立てれば！

于 2013-09-10T19:27:26.280 に答える