1

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:

List

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.

4 Answers 4

6

As per my understanding, ArrayList is an array implementation of a list. So if you remove elements from the beginning of an array you need to move all the remaining elements to fill up the elements that you removed. So this is going to essentially be a O(n-1) operation.However this is not the case when you remove elements from end of the list. This will be O(1).

2

There is more to removing elements from the beginning of the list than just setting the elements to null. You also need to move the remaining elements to fill in the vacated locations.

It's possible to use a variable to keep track of the "beginning" of the list without moving elements, but then you will sacrifice memory efficiency because of the unused elements in the array.

2
  • Thanks, I was just thinking that a shift every single time an element is removed is quite expensive, yet, I'm guessing this is done this way so as to keep the array consistent and with non-null (or removed) values at all times.
    – arin
    Commented Mar 12, 2013 at 2:24
  • @arin "I was just thinking that a shift every single time an element is removed is quite expensive" Exactly! And so is the alternative. Commented Mar 12, 2013 at 2:28
0

In ArrayList<> removing from start is slow because entire array will have to be shifted since the add function add the elements at and if we left the start empty then we will be wasting the memory.

If we take into account big(O) notation removing from start is essentially linear time O(n) while deleting from end is constant time O(1).

0

While Code-Apprentice's answer is correct, I'd like to elaborate on how you can verify the behavior that every entry is moved to the left by making an index-based lookup, i.e., calling list.get(index).

  1. add two entries
  2. remove the first element
  3. check the value of the first element: is it now null or the previously second element?

The code to verify:

List<String> list = new ArrayList<>();
list.add("0");
list.add("1");
list.remove(0);
String entry0 = list.get(0);
System.out.println(entry0);

You suspected that null would be printed, but "1" is printed. This confirms that all the elements are shifted to the left.

NB. I used Strings to avoid the confusion caused by remove(int index) and remove(Object o).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.