ArrayList add(index, object) vs add(object) complexity

Question

I was given the following little multiple-choice question in my APCS class concerning adding elements to ArrayList's and although one particular answer seems intuitively correct to me (choice B), I'm not entirely sure whether it's indeed right or what's actually going on behind the scenes performance-wise:

//Consider the following methods
public static List<Integer> process1(int n) {
    List<Integer> someList = new ArrayList<Integer>();
    for (int k = 0; k < n; k++) {
        someList.add(new Integer(k));
    }
    return someList;
}
public static List<Integer> process2(int n) {
    List<Integer> someList = new ArrayList<Integer>();
    for (int k = 0; k < n; k++) {
        someList.add(k, new Integer(k));
    }
    return someList;
}

//Which of the following best describes the behavior of process1 and process2?
//(A) Both methods produce the same result and take the same amount of time
//(B) Both methods produce the same result and process1 is faster than process2
//(C) The two methods produce different results and process1 is faster than process2
//(D) The two methods produce different results and process2 is faster than process1

Note: I did test both methods out on my computer using large enough parameters and both are quite close in run length, but method1 seems to be slightly faster. Also, this isn't a homework problem to be turned in or anything, so no need to feel worried about providing me with answers:)

I think in the process2 method you want to test with someList.add(0, new Integer(k)); instead of someList.add(k, new Integer(k));. Then you might notice a difference. Because add(int, element) will shifts the element currently at that position (if any) and any subsequent elements to the right. This would be O(n) in my view. With the current code you always adding the element into the next element that is available and I think that is why the performance numbers are same for both methods. Where as add(element) has O(1) complexity. — Madhusudana Reddy Sunnapu
– Madhusudana Reddy Sunnapu, Commented Mar 11, 2016 at 5:51

andars · Accepted Answer · 2016-03-11 05:27:13Z

1

From the JDK source (reproduced in @ScaryWombat's answer), it appears that the first will be slightly faster.

In context, System.arraycopy won't actually do anything, but the call will still be made. Otherwise, they are essentially identical. The first has one extra function call, so it will likely be a tiny bit slower (magnified by large n).

answered Mar 11, 2016 at 5:27

andars

1,4048 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Nick Over a year ago

Ah, I see - I figured it had to be doing some sort of extra (albeit empty in this case) method calls behind the scenes

Scary Wombat · Accepted Answer · 2016-03-11 05:30:46Z

0

 public boolean add(E e) {
         ensureCapacity(size + 1);  // Increments modCount!!
         elementData[size++] = e;
         return true;
}

vs

public void add(int index, E element) {
         rangeCheckForAdd(index);

         ensureCapacity(size+1);  // Increments modCount!!
         System.arraycopy(elementData, index, elementData, index + 1,
                          size - index);
         elementData[index] = element;
         size++;
     }

so it looks like method has more code to do in addition to the common code shared by both

edited Mar 11, 2016 at 5:30

answered Mar 11, 2016 at 5:23

Scary Wombat

44.9k6 gold badges38 silver badges67 bronze badges

Collectives™ on Stack Overflow

ArrayList add(index, object) vs add(object) complexity

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related