Runtime of arraylist operations add and remove by index
This question already has an answer here:
No, this would not be accurate to say that insertion and removal of elements from ArrayList by index is amortized constant time, because there is no amortization going on for copying of data.
Only list expansions and their associated copying are amortized, because they happen infrequently*. However, this requires insertions at the end of the list.
When you insert at the beginning of the list, expansions are still amortized, but copies required to move elements by 1 position happen on every call, and are not amortized.
* In order to be able to amortize the cost of an operation you need a mix of "cheap" and "expensive" operations. In this situation you can split the total cost among all operations, getting you a lower result.
For add(Object) yes, but for remove(int index) it's constant time only if you're removing the last element, since otherwise the elements are shifted to remove any nulls from the middle of the array.
Index based add (and remove from not last position) aren't amortized constant time, they're linear time.
上一篇: 何时使用每个Java Collections数据结构
下一篇: 数组列表操作的运行时间按索引添加和删除