CODEWITHSUNDEEP
javacollectionslinked-listasymptotic-complexity
kaizokun
kaizokun

Reputation: 1034

Java Collection addAll complexity

Is there a Java collection with a complexity of O(1) and not O(n) for the addAll operation, or must I implement my own collection ? With a efficient linked list the Collection1.addAll(Collection2) operation should append the second collection to the first adding the first node of collection2 to the last of collection 1 and the others follow. But it' s not that I read into the documentation it seems to use an Iterator so I guess the complexity is O( collection2.size).

Is that right ?

Upvotes: 8

Views: 17780

Answers (2)

Sean Patrick Floyd
Sean Patrick Floyd

Reputation: 298838

ArrayList is probably as good as it gets in this respect, but it actually depends on the supplied collection as well. The best-case complexity is O(1), but only if the supplied Collection's toArray() method also has constant complexity.

The System.arrayCopy() call that does the actual allocation is O(1), anyway is complicated, see below:

// java.util.ArrayList.addAll
// Oracle JDK 1.8.0_91
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray(); // O(?) <-- depending on other type
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew); 
    size += numNew;
    return numNew != 0;
}

There's some disagreement on whether System.arrayCopy is a constant-time operation. Some say no. Others suggest it is.

According to this benchmark I hacked together, it's somewhere in the middle. Copy Times stay pretty much constant up to about 100 array items, but grow linear from there on, I am guessing some kind of paging is involved there. So effectively, System.arrayCopy has linear time complexity unless the arrays are very small.

Upvotes: 4

glglgl
glglgl

Reputation: 91017

Even the optimization for linked lists can only work if you move items from one linked list to another.

You could build an own kind of collection, however, which has one more level of indirection, i. e. which contains a collection of collections. This way, adding whole collection is quite cheap, and so is iterating. Indexing or length determination can become quite expensive, however.

Upvotes: 5

Related Questions