1

私は ArrayList と LinkedList の長所と短所に精通しています。ArrayList は、追加と削除が少ない場合、ランダム アクセスに適しています。逆の場合も同様です。ランダム アクセスの両方を行う必要があり、リストからアイテムを頻繁に追加および削除する必要があるデータ構造が必要な場合はどうすればよいですか?

どちらを選ぶ？

4

2 に答える 2

3

これらのデータ構造は API と互換性があり、両方でコードをベンチマーク/プロファイリングするだけです。

別のヒント:ルックアップとミューテーションArrayListを実行すると仮定します。これは複雑になります。(線形ルックアップ時間+ 一定時間の突然変異時間) が得られます。したがって、両方のデータ構造は同等です。NNO(N) + O(N * N) <=> O(N^2)LinkedListO(N*N) + O(N) <=> O(N^2)NN

うさぎの穴をもう少し深く掘り下げたい場合は、検索と挿入/削除の両方の一定のコストscala.collection.immutable.Vectorを償却しています。そしてそれは不変であるため、スレッドセーフです! これは、その下にある洗練されたデータ構造を使用して実現されます。

于 2012-10-20T07:44:08.403 に答える
1

ArrayList に Random Access を使用したい場合は、それを通常のリストとして使用し、項目を追加/削除できます。

ArrayList のメモリはブロック単位で割り当てられるため、ArrayList が巨大になるまでメモリが不足する可能性があります。

メモリの制約があるかどうかについて言及していないので（制約はランダム アクセスのみ）、ArrayList はすべてのニーズを満たす必要があると言えます。

于 2012-10-20T07:41:06.010 に答える