What is the time complexity to copy one arraylist to another in Java?

Question

ArrayList<Integer>arr1=new ArrayList<Integer>();
 arr1.add(1);
 arr1.add(2);
 arr1.add(3);
ArrayList<Integer>copyArray=new ArrayList<Integer>(arr1);

Does the above code to replicate one arrayList to another arrayList work in O(1) or deep down it's O(n) ,as seems that to copy each element of one array to another it would iterate one by one which would result in O(n) ,or is it just a reference to a object pool ?

'Deep down' `System.arraycopy(...)` is used which results in O(n). — L.Spillner, Jun 14 '18 at 06:27

score 3 · Accepted Answer · answered Jun 14 '18 at 06:36

Looking to the source:

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

The ArrayList(Collection) constructor calls toArray() which calls Arrays.copyOf:

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

The important part here is System.arraycopy which is a native call. Another question on SO addresses the time complexity of this call, and the conclusion seems to be that this call is O(n) in worst case scenarios but that some systems may use block copies for some data types (like primitives I imagine), thus resulting in more efficient runtime than for loop iteration.

score 1 · Answer 2 · answered Jun 14 '18 at 06:36

Internally it uses Arrays.copyOf which further uses System.arraycopy whose complexity is O(n). Checkout the source below:

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

score 1 · Answer 3 · answered Jun 14 '18 at 07:45

Checking the source code , ArrayList(Collection<? extends E> c) constructor internally calls c.to Array()

The Java Doc for toArray() https://docs.oracle.com/javase/9/docs/api/java/util/ArrayList.html#toArray--

says its does a deep copy of the source array and returns the safe copied array. So any change the client makes to the retuned array doesn't impact the internal datastructure of the ArrayList. So in worst case its O(n).

What is the time complexity to copy one arraylist to another in Java?

3 Answers3