Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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).

like image 672
Ognjen Avatar asked Oct 26 '11 23:10

Ognjen


People also ask

What is the time complexity of ArrayList remove method?

The overall time complexity of both the variations of remove method in ArrayList will be O(N), where N is the number of inputs.

How can an ArrayList improve performance?

In order to optimize the performance of ArrayLists, it is advisable to set a large enough initial capacity when initializing an ArrayList to incorporate all your data. This will allocate a large enough chunk of memory so that you will probably not need to perform the allocation process again.

How the performance of ArrayList and LinkedList are when you try to add Modify Search large number of records?

It looks like ArrayList and LinkedList both will have the same performance. Here we need to notice that array(underlying data structure of ArrayList) stores all values in a continuous memory location, but DoublyLinkedList store each node at a random memory location.

Why is ArrayList generally the best performing implementation?

Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.


2 Answers

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.

like image 143
Stephen C Avatar answered Oct 06 '22 10:10

Stephen C


"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.

like image 26
Oliver Charlesworth Avatar answered Oct 06 '22 11:10

Oliver Charlesworth