Java: ArrayList add() and remove() performance, implementation?

Question

I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time. What does this mean exactly?

In the implementation of add(item) I can see that it ArrayList uses an array buffer, which is at most 3/2 of the list't size, and if it is full, System.arraycopy() is called, which should execute in O(n), not O(1) time. Is it then that System.arraycopy attempts to do something smarter than copying elements one by one into newly created array, since the time is actually O(1)?

---

Conclusion: add(item) runs in amortized constant time, but add(item, index) and remove(index) don't, they run in linear time (as explained in answers).

Solution 1

I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time.

I don't think that is true for remove() except under unusual conditions.

• A remove(Object) call for a random element on average has to call equals on half of entries in the list, and then copy the references for the other half.

• A remove(int) call for a random element on average has to copy the references for half of the elements.

The only cases where remove(...) is going to be O(1) on average (e.g. amortized) is when you are using remove(int) to remove elements some constant offset from the end of the list.

Solution 2

"Amortized" roughly means "averaged across the entire runtime". Yes, an array-copy will be O(n). But that only happens when the list is full, which happens 1 in n times.

Comments

[Admin]

+1 even though I'm not sure if "happens 1 in n times" is appropriate... usually the backing is double each time for an increase so... dunno what remove's limits/rules are.

[Ognjen]

So, i guess this "constant time in average" holds because the buffer growth is not constant, but proportional to the array's size? (+1/2 of array's size each time it resizes, instead of e.g. +5 places each time)?