08/05/24 14:11:20
>>394
追加し続けるだけ? それなら、
ArrayList→1回のaddにおける代入回数は1回。配列の末尾に要素を代入する(これで1回)だけ。配列のサイズが足りなくなると、元の1.5倍のサイズの配列を確保して元の要素を全部コピー。(このときだけ遅い)
LinkedList→1回のaddにおける代入回数は5回。要素を入れるEntryをnewして要素を代入(これで1回)し、前後のリンクを繋ぎ直す。(前、後、前の後、後の前で計4回)
あとは、どちらにもサイズのインクリメントとConcurrentModificationException判定用カウンタのインクリメントがあるけど、数字を見ると大きな要因ではなさげ。(最近のCPUだと並列処理されるのかな)
また、ArrayListは配列の拡張にペナルティがあるけど、LinkedListも1要素毎にnewするからか、ある程度相殺されてるっぽい。