Java ArrayList - how can I tell if two lists are equal, order not mattering?
I have two ArrayLists of type Answer (self-made class).
I'd like to compare the two lists to see if they contain the same contents, but without order mattering.
Example:
//These should be equal.
ArrayList<String> listA = {"a", "b", "c"}
ArrayList<String> listB = {"b", "c", "a"}
List.equals states that two lists are equal if they contain the same size, contents, and order of elements. I want the same thing, but without order mattering.
Is there a simple way to do this? Or will I need to do a nested for loop, and manually check each index of both lists?
Note: I can't change them from ArrayList to another type of list, they need to remain that.
Solution 1:
Probably the easiest way for any list would be:
listA.containsAll(listB) && listB.containsAll(listA)
Solution 2:
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);
}
Solution 3:
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
trueiff the givenCollections 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 benullb- the second collection, must not benullReturns:
trueiff the collections contain the same elements with the same cardinalities.
Solution 4:
// 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;
}
Solution 5:
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.