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

Spread the love

Question Description

I have a situation where I will be receiving 2+ ArrayList 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 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 mergeAndRemoveDupes(ArrayList 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!

Practice As Follows

For each ArrayList, add each element to a Set (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, or a similar
//Comparable instance needs to be passed into a TreeSet 
public class Widget implements Comparable
{
    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 on your Widget class, you can give the set itself a Comparator object:

private Set treeSet;
....
treeSet = new TreeSet(new Comparator() {
            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());
            }
           });

Leave a Comment