Merging two arrayLists into a new arrayList, with no duplicates and in order, in Java

Question

I am trying to "combine" two arrayLists, producing a new arrayList that contains all the numbers in the two combined arrayLists, but without any duplicate elements and they should be in order. I came up with this code below. I run through it and it makes sense to me, but Im not sure if I can be using < or > to compare get(i)'s in arrayLists. I am adding all the elements in array1 into the plusArray. Then I am going through the plusArray and comparing it to array2 to see if any of array2's elements exist inside plusArray. If they do I am doing nothing, but if they dont then I am trying to add it in its correct position. Perhaps my nested for loops being used incorrectly? Note: The ArrayLists are presorted by the user in increasing order.

     ArrayList<Integer> plusArray = new ArrayList<Integer>(); for(int i = 0; i < array1.size(); i++){     plusArray.add(array1.get(i)); }  for(int i = 0; i < plusArray.size(); i++){     for(int j = 0; j < array2.size(); j++){      if(array2.get(j) < plusArray.get(i)){         plusArray.add(i,array2.get(j));     }     else if(plusArray.get(i).equals(array2.get(j))){         ;     }     else if(array2.get(j) > plusArray.get(i)){         plusArray.add(i, array2.get(j));     }  } 

UPDATE: I dont get the exception below anymore. Instead it seems the program runs forever. I changed the location of where to add the elements in the < and > conditions. /// Here is the exception that I get when my array lists are: IntSet 1: { 1 2 } IntSet 2: { 1 3 4 }

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.util.Arrays.copyOf(Unknown Source) at java.util.Arrays.copyOf(Unknown Source) at java.util.ArrayList.grow(Unknown Source) at java.util.ArrayList.ensureCapacityInternal(Unknown Source) at java.util.ArrayList.add(Unknown Source) at IntSet.plus(IntSet.java:92) at IntSetDriver.main(IntSetDriver.java:61) 

Answer 1

Firstly remove duplicates:

arrayList1.removeAll(arrayList2); 

Then merge two arrayList:

arrayList1.addAll(arrayList2); 

Lastly, sort your arrayList if you wish:

collections.sort(arrayList1); 

In case you don't want to make any changes on the existing list, first create their backup lists:

arrayList1Backup = new ArrayList(arrayList1); 

Answer 2

Instead of the code you wrote, you may use ArrayList.addAll() to merge the lists, Collections.sort() to sort it and finally traverse of the resulting ArrayList to remove duplicates. The aggregate complexity is thus O(n)+O(n*log(n))+O(n) which is equivalent to O(n*log(n)).