I have to replace an element in an ArrayList.
Which is faster—using remove() and add() or getting the needed item index and using set(int, E)?
If you know some books about similiar themes, please give me some advice.
3 Answers
If this is the last item of ArrayList, almost no difference. In othe case - set(int, E) will be faster because no nee to copy part of array
Comments
It's all in the javadoc (emphasis mine):
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).
To recap: set = O(1) whereas add/remove = O(n) ==> use set.
Comments
The remove(Object) will perform a linear search in your ArrayList and then remove the first occurrence of the specified object, which means that in the worst case you'll get an O(N) complexity.
If you already know the index to replace, for sure will be faster to call .set(index, object), but if you don't, there is no difference because in both cases you will have to perform a linear search getting O(N) complexity.
add(Object) always add the object at the end of the ArrayList, so it runs in O(1) complexity to add a single object in your ArrayList.
setis highly likely to be the fastest since no resizing or node manipulation will be necessary other than referencing the new object.