In the Collection framework tutorials for the List interface, there is an interesting quote regarding performance of removal of elements from a List implementation:
For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.
The tutorials do not go further into explaining this and I am trying to understand exactly why it might be so.
Considering an ArrayList<Integer> list
as below:
In the first scenario, if we remove the last 4 elements from the end of the list
, then the values of these are set to null
(or equivalent). My theory is that, when a copy operation is necessary, only the elements that are not null
will be copied.
In the second scenario, if we remove the first 4 elements, they would be set to null
again and again only non-null
elements would be copied.
So from this point of view, the performances appear to be around the same. Is there another reason why the operation is faster if performed from the end?
On the other hand, for LinkedList
, the inverse appears to be true; removal from the beginning is faster, whereas removal from the end requires an almost full traversal unless a tail-pointer
is kept.