Best way to merge and remove duplicates from multiple lists in Java

Question

I have a situation where I will be receiving 2+ ArrayList<Widget> and I need to be able to merge all the lists and remove any duplicate Widget so that I wind up with only 1 ArrayList<Widget> that contains all Widgets from all the merged lists, but without any duplicates.

Assume Widget has an overridden equals method that can be used for determining whether two Widgets are duplicates, although there may be a better way:

public ArrayList<Widget> mergeAndRemoveDupes(ArrayList<Widget> widgets...) {
    // ???
}

Looking for the most algorithmically efficient way of accomplishing this. I am happy to use Apache Commons or any other open source libs that would help me out too! Thanks in advance!

Answer 1

For each ArrayList<Widget>, add each element to a Set<Widget> (HashSet or TreeSet, depending on whether they can be ordered in some way, or are hashable) utilizing addAll. Sets contain no duplicates by default.

You can convert this Set back into an (Array)List if you need to at the end.

Note you will need to implement hashCode for your Widget class if you decide to use a HashSet, but if you have an overridden equals, you should do this anyway.

Edit: Here's an example:

//Either the class itself needs to implement Comparable<T>, or a similar
//Comparable instance needs to be passed into a TreeSet 
public class Widget implements Comparable<Widget>
{
    private final String name;
    private final int id;

    Widget(String n, int i)
    {
        name = n;
        id = i;
    }

    public String getName()
    {
        return name;
    }

    public int getId()
    {
        return id;
    }

    //Something like this already exists in your class
    @Override
    public boolean equals(Object o)
    {
        if(o != null && (o instanceof Widget)) {
            return ((Widget)o).getName().equals(name) &&
                   ((Widget)o).getId() == id;
        }
        return false;
    }

    //This is required for HashSet
    //Note that if you override equals, you should override this
    //as well. See: http://stackoverflow.com/questions/27581/overriding-equals-and-hashcode-in-java
    @Override 
    public int hashCode()
    {
        return ((Integer)id).hashCode() + name.hashCode();
    }

    //This is required for TreeSet
    @Override
    public int compareTo(Widget w)
    {
        if(id < w.getId()) return -1;
        else if(id > w.getId()) return 1;
        return name.compareTo(w.getName());
    }

    @Override 
    public String toString()
    {
        return "Widget: " + name + ", id: " + id;
    }
}

If you want to use a TreeSet but don't want to implement Comparable<T> on your Widget class, you can give the set itself a Comparator object:

private Set<Widget> treeSet;
....
treeSet = new TreeSet<Widget>(new Comparator<Widget>() {
            public int compare(Widget w1, Widget w2)
            {
                if(w1.getId() < w2.getId()) return -1;
                else if(w1.getId() > w2.getId()) return 1;
                return w1.getName().compareTo(w2.getName());
            }
           });

Answer 2

I would do it this way

Set<Widget> set = new HashSet<>(list1);
set.addAll(list2);
List<Widget> mergeList = new ArrayList<>(set);