私は ArrayList と LinkedList の長所と短所に精通しています。ArrayList は、追加と削除が少ない場合、ランダム アクセスに適しています。逆の場合も同様です。ランダム アクセスの両方を行う必要があり、リストからアイテムを頻繁に追加および削除する必要があるデータ構造が必要な場合はどうすればよいですか?
どちらを選ぶ?
私は ArrayList と LinkedList の長所と短所に精通しています。ArrayList は、追加と削除が少ない場合、ランダム アクセスに適しています。逆の場合も同様です。ランダム アクセスの両方を行う必要があり、リストからアイテムを頻繁に追加および削除する必要があるデータ構造が必要な場合はどうすればよいですか?
どちらを選ぶ?
これらのデータ構造は API と互換性があり、両方でコードをベンチマーク/プロファイリングするだけです。
別のヒント:ルックアップとミューテーションArrayList
を実行すると仮定します。これは複雑になります。(線形ルックアップ時間+ 一定時間の突然変異時間) が得られます。したがって、両方のデータ構造は同等です。N
N
O(N) + O(N * N) <=> O(N^2)
LinkedList
O(N*N) + O(N) <=> O(N^2)
N
N
うさぎの穴をもう少し深く掘り下げたい場合は、検索と挿入/削除の両方の一定のコストscala.collection.immutable.Vector
を償却しています。そしてそれは不変であるため、スレッドセーフです! これは、その下にある洗練されたデータ構造を使用して実現されます。
ArrayList に Random Access を使用したい場合は、それを通常のリストとして使用し、項目を追加/削除できます。
ArrayList のメモリはブロック単位で割り当てられるため、ArrayList が巨大になるまでメモリが不足する可能性があります。
メモリの制約があるかどうかについて言及していないので(制約はランダム アクセスのみ)、ArrayList はすべてのニーズを満たす必要があると言えます。