Java ArrayList - how can I tell if two lists are equal, order not mattering?

Question

Probably the easiest way for any list would be:

listA.containsAll(listB) && listB.containsAll(listA)

You could sort both lists using Collections.sort() and then use the equals method. A slighly better solution is to first check if they are the same length before ordering, if they are not, then they are not equal, then sort, then use equals. For example if you had two lists of Strings it would be something like:

public  boolean equalLists(List<String> one, List<String> two){     
    if (one == null && two == null){
        return true;
    }

    if((one == null && two != null) 
      || one != null && two == null
      || one.size() != two.size()){
        return false;
    }

    //to avoid messing the order of the lists we will use a copy
    //as noted in comments by A. R. S.
    one = new ArrayList<String>(one); 
    two = new ArrayList<String>(two);   

    Collections.sort(one);
    Collections.sort(two);      
    return one.equals(two);
}

Apache Commons Collections to the rescue once again:

List<String> listA = Arrays.asList("a", "b", "b", "c");
List<String> listB = Arrays.asList("b", "c", "a", "b");
System.out.println(CollectionUtils.isEqualCollection(listA, listB)); // true

 

List<String> listC = Arrays.asList("a", "b", "c");
List<String> listD = Arrays.asList("a", "b", "c", "c");
System.out.println(CollectionUtils.isEqualCollection(listC, listD)); // false

Docs:

org.apache.commons.collections4.CollectionUtils

public static boolean isEqualCollection(java.util.Collection a,
                                        java.util.Collection b)

Returns true iff the given Collections contain exactly the same elements with exactly the same cardinalities.

That is, iff the cardinality of e in a is equal to the cardinality of e in b, for each element e in a or b.

Parameters:

• a - the first collection, must not be null
• b - the second collection, must not be null

Returns: true iff the collections contain the same elements with the same cardinalities.

// helper class, so we don't have to do a whole lot of autoboxing
private static class Count {
    public int count = 0;
}

public boolean haveSameElements(final List<String> list1, final List<String> list2) {
    // (list1, list1) is always true
    if (list1 == list2) return true;

    // If either list is null, or the lengths are not equal, they can't possibly match 
    if (list1 == null || list2 == null || list1.size() != list2.size())
        return false;

    // (switch the two checks above if (null, null) should return false)

    Map<String, Count> counts = new HashMap<>();

    // Count the items in list1
    for (String item : list1) {
        if (!counts.containsKey(item)) counts.put(item, new Count());
        counts.get(item).count += 1;
    }

    // Subtract the count of items in list2
    for (String item : list2) {
        // If the map doesn't contain the item here, then this item wasn't in list1
        if (!counts.containsKey(item)) return false;
        counts.get(item).count -= 1;
    }

    // If any count is nonzero at this point, then the two lists don't match
    for (Map.Entry<String, Count> entry : counts.entrySet()) {
        if (entry.getValue().count != 0) return false;
    }

    return true;
}

I'd say these answers miss a trick.

Bloch, in his essential, wonderful, concise Effective Java, says, in item 47, title "Know and use the libraries", "To summarize, don't reinvent the wheel". And he gives several very clear reasons why not.

There are a few answers here which suggest methods from CollectionUtils in the Apache Commons Collections library but none has spotted the most beautiful, elegant way of answering this question:

Collection<Object> culprits = CollectionUtils.disjunction( list1, list2 );
if( ! culprits.isEmpty() ){
  // ... do something with the culprits, i.e. elements which are not common

}

Culprits: i.e. the elements which are not common to both Lists. Determining which culprits belong to list1 and which to list2 is relatively straightforward using CollectionUtils.intersection( list1, culprits ) and CollectionUtils.intersection( list2, culprits ).
However it tends to fall apart in cases like { "a", "a", "b" } disjunction with { "a", "b", "b" } ... except this is not a failing of the software, but inherent to the nature of the subtleties/ambiguities of the desired task.

You can always examine the source code (l. 287) for a task like this, as produced by the Apache engineers. One benefit of using their code is that it will have been thoroughly tried and tested, with many edge cases and gotchas anticipated and dealt with. You can copy and tweak this code to your heart's content if need be.

---

NB I was at first disappointed that none of the CollectionUtils methods provides an overloaded version enabling you to impose your own Comparator (so you can redefine equals to suit your purposes).

But from collections4 4.0 there is a new class, Equator which "determines equality between objects of type T". On examination of the source code of collections4 CollectionUtils.java they seem to be using this with some methods, but as far as I can make out this is not applicable to the methods at the top of the file, using the CardinalityHelper class... which include disjunction and intersection.

I surmise that the Apache people haven't got around to this yet because it is non-trivial: you would have to create something like an "AbstractEquatingCollection" class, which instead of using its elements' inherent equals and hashCode methods would instead have to use those of Equator for all the basic methods, such as add, contains, etc. NB in fact when you look at the source code, AbstractCollection does not implement add, nor do its abstract subclasses such as AbstractSet... you have to wait till the concrete classes such as HashSet and ArrayList before add is implemented. Quite a headache.

In the mean time watch this space, I suppose. The obvious interim solution would be to wrap all your elements in a bespoke wrapper class which uses equals and hashCode to implement the kind of equality you want... then manipulate Collections of these wrapper objects.