Combine two ArrayList(s), omit duplicates

[Sanxion]

Is using a HashSet the  fastest way to combine two ArrayList(s) and omit duplicates?

ArrayList a1, a2; // fill them with junk

HashSet hash = new HashSet(a1);
hash.addAll(a2);

[ryanm]

You could just do

ArrayList a1, a2; // fill with junk

a1.removeAll( a2 ); // removes duplicates
a1.addAll( a2 ); // combines lists

You might also want to use LinkedLists instead of ArrayLists in order to avoid costly removing-from-an-array operations, and the annoying array-growing operation.  Anyhoo, as long as your chosen collection implements the java.util.Collection interface, you can do the above.

[abies]

Exact testing needs to be done, but I do think that HashSet version should be an order of magnitude faster.

In theory HashSet insert is O(1) and ArrayList remove of _single_ element is O(n). So here we have O(n) versus O(n^2) complexity, a BIG difference.

Of course, for small n, other costs will be important. But I do not expect that remove version will be faster for anything over 5-6 elements.

Games published by our own members! Check 'em out!

[opinali]

If both ArrayLists are sorted, the fastest way is coding a loop that iterates both arrays in parallel and for each iteration, copies the lower-ordering element to a new array.