CODEWITHSUNDEEP
javaperformancearraylist
Nick
Nick

Reputation: 147

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

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

Upvotes: 2

Views: 346

Answers (2)

Scary Wombat
Scary Wombat

Reputation: 44834

 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

Upvotes: 0

andars
andars

Reputation: 1404

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

Upvotes: 1

Related Questions