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

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)

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

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

List<String> listA = new ArrayList<String>();

    listA.add("A");
    listA.add("B");

List<String> listB = new ArrayList<String>();

    listB.add("B");
    listB.add("C");

Set<String> newSet = new HashSet<String>(listA);

    newSet.addAll(listB);
List<String> newList = new ArrayList<String>(newSet);

System.out.println("New List :"+newList);

is giving you New List :[A, B, C]

Add ArrayList1, ArrayList2 and produce a Single arraylist ArrayList3. Now convert it into

Set Unique_set = new HashSet(Arraylist3);

in the unique set you will get the unique elements.
Note

ArrayList allows to duplicate values. Set doesn't allow the values to duplicate. Hope your problem solves.

Java 8 Stream API can be used for the purpose,

ArrayList<String> list1 = new ArrayList<>();

list1.add("A");
list1.add("B");
list1.add("A");
list1.add("D");
list1.add("G");

ArrayList<String> list2 = new ArrayList<>();

list2.add("B");
list2.add("D");
list2.add("E");
list2.add("G");

List<String> noDup = Stream.concat(list1.stream(), list2.stream())
                     .distinct()
                     .collect(Collectors.toList());
noDup.forEach(System.out::println);

En passant, it shouldn't be forgetten that distinct() makes use of hashCode().

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

Related

Recent Posts