CODEWITHSUNDEEP
javaarraylist
Milwaukoholic
Milwaukoholic

Reputation: 1161

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)

Upvotes: 57

Views: 173606

Answers (14)

Hoa Nguyen
Hoa Nguyen

Reputation: 14540

Here is one solution using java 8:

Stream.of(list1, list2)
    .flatMap(Collection::stream)
    .distinct()
    // .sorted() uncomment if you want sorted list
    .collect(Collectors.toList());

Upvotes: 9

Rinks
Rinks

Reputation: 1

I got your point that you don't wanna use the built-in functions for merging or remove duplicates from the ArrayList. Your first code is running forever because the outer for loop condition is 'Always True'. Since you are adding elements to plusArray, so the size of the plusArray is increasing with every addition and hence 'i' is always less than it. As a result the condition never fails and the program runs forever. Tip: Try to first merge the list and then from the merged list remove the duplicate elements. :)

Upvotes: 0

Soner from The Ottoman Empire
Soner from The Ottoman Empire

Reputation: 20891

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

Upvotes: 15

iehrlich
iehrlich

Reputation: 3592

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

Upvotes: 35

Ashish Agrawal Yodlee
Ashish Agrawal Yodlee

Reputation: 123

**Add elements in Final arraylist,**
**This will Help you sure**

import java.util.ArrayList;
import java.util.List;

public class NonDuplicateList {

public static void main(String[] args) {

    List<String> l1 = new ArrayList<String>();
    l1.add("1");l1.add("2");l1.add("3");l1.add("4");l1.add("5");l1.add("6");
    List<String> l2 = new ArrayList<String>();
    l2.add("1");l2.add("7");l2.add("8");l2.add("9");l2.add("10");l2.add("3");
    List<String> l3 = new ArrayList<String>();
    l3.addAll(l1);
    l3.addAll(l2);
    for (int i = 0; i < l3.size(); i++) {
        for (int j=i+1; j < l3.size(); j++) {
             if(l3.get(i) == l3.get(j)) {
                 l3.remove(j);
            }
        }
    }
    System.out.println(l3);
}

}

Output : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Upvotes: 0

Noumenon
Noumenon

Reputation: 6412

You don't have to handcode this. The problem definition is precisely the behavior of Apache Commons CollectionUtils#collate. It's also overloaded for different sort orders and allowing duplicates.

Upvotes: 0

Ediz T&#252;rkoğlu
Ediz T&#252;rkoğlu

Reputation: 1159

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

Upvotes: 84

Hiren Patel
Hiren Patel

Reputation: 52790

Add elements in first arraylist

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

firstArrayList.add("A");
firstArrayList.add("B");
firstArrayList.add("C");
firstArrayList.add("D");
firstArrayList.add("E");

Add elements in second arraylist

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

secondArrayList.add("B");
secondArrayList.add("D");
secondArrayList.add("F");
secondArrayList.add("G");

Add first arraylist's elements in second arraylist

secondArrayList.addAll(firstArrayList);

Assign new combine arraylist and add all elements from both arraylists

ArrayList<String> comboArrayList = new ArrayList<String>(firstArrayList);
comboArrayList.addAll(secondArrayList);

Assign new Set for remove duplicate entries from arraylist

Set<String> setList = new LinkedHashSet<String>(comboArrayList);
comboArrayList.clear();
comboArrayList.addAll(setList);

Sorting arraylist 

Collections.sort(comboArrayList);

Output

 A
 B
 C
 D
 E
 F
 G

Upvotes: 5

DilanG
DilanG

Reputation: 1225

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]

Upvotes: 16

special
special

Reputation: 641

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.

Upvotes: 13

Southeast
Southeast

Reputation: 597

your nested for loop 

 for(int j = 0; j < array2.size(); i++){

is infinite as j will always equal to zero, on the other hand, i will be increased at will in this loop. You get OutOfBoundaryException when i is larger than plusArray.size()

Upvotes: 1

Stephen C
Stephen C

Reputation: 718758

Perhaps my nested for loops being used incorrectly?

Hint: nested loops won't work for this problem. A simple for loop won't work either.

You need to visualize the problem.

Write two ordered lists on a piece of paper, and using two fingers to point the elements of the respective lists, step through them as you do the merge in your head. Then translate your mental decision process into an algorithm and then code.

The optimal solution makes a single pass through the two lists.

Upvotes: 4

Eric J.
Eric J.

Reputation: 150108

I'm not sure why your current code is failing (what is the Exception you get?), but I would like to point out this approach performs O(N-squared). Consider pre-sorting your input arrays (if they are not defined to be pre-sorted) and merging the sorted arrays:

http://www.algolist.net/Algorithms/Merge/Sorted_arrays

Sorting is generally O(N logN) and the merge is O(m+n).

Upvotes: 2

Chetter Hummin
Chetter Hummin

Reputation: 6817

Your second for loop should have j++ instead of i++

Upvotes: 2

Related Questions