Sean Hill Sean Hill - 2 months ago 7
Java Question

Runtime of arraylist operations add and remove by index

For Java ArrayList, is it accurate to say add and remove by index run in amortized constant time, meaning on average it is constant time (in rare cases linear time by setting up the memory so future operations are faster)?

Answer

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.