Java ArrayList - how can I determine if two lists are equal, order doesn't matter?

Question

I have two ArrayList type Answer (self-made class).

I would like to compare the two lists to see if they contain the same content, but without regard to order.

Example:

 //These should be equal. ArrayList<String> listA = {"a", "b", "c"} ArrayList<String> listB = {"b", "c", "a"} 

List.equals claims that two lists are equal if they contain the same size, content and order of elements. I want the same thing, but without the meaning of order.

Is there an easy way to do this? Or will I need to do a nested for loop and manually check each index of both lists?

Note: I cannot change them from ArrayList to another type of list, they should remain like this.

Answer 1

You can sort both lists using Collections.sort() , and then use the equals method. The best solution is to first check to see if they have the same length before ordering, if they are not, then they are not equal, then sorted, and then use equal ones. For example, if you had two list of strings, it would be something like this:

 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 ARS one = new ArrayList<String>(one); two = new ArrayList<String>(two); Collections.sort(one); Collections.sort(two); return one.equals(two); } 

Answer 2

Probably the easiest way for any list:

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

Answer 3

Apache Commons Collections to help 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 if this Collection contains exactly the same elements with exactly the same power.

That is, if the power of e in is equal to the power of e in b, for each element e in or b.

Options:

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

Returns: true if the collections contain the same elements with the same power.

Answer 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; } 

Answer 5

If the number of elements does not matter (meaning that the repeating elements are considered as a whole), then there is a way to do this without sorting:

boolean result = new HashSet<>(listA).equals(new HashSet<>(listB));

This will create a Set from each List , and then use the equals HashSet method which (of course) ignores the order.

If cardinality matters, you should limit yourself to the possibilities provided by List ; @jschoen's answer would be more appropriate in this case.

Answer 6

This is based on @cHao's solution. I have included several fixes and performance improvements. This works about twice as fast as a solution with an equal copy order. Works for any type of collection. Empty collections and zero are considered equal. Use to your advantage;)

 /** * Returns if both {@link Collection Collections} contains the same elements, in the same quantities, regardless of order and collection type. * <p> * Empty collections and {@code null} are regarded as equal. */ public static <T> boolean haveSameElements(Collection<T> col1, Collection<T> col2) { if (col1 == col2) return true; // If either list is null, return whether the other is empty if (col1 == null) return col2.isEmpty(); if (col2 == null) return col1.isEmpty(); // If lengths are not equal, they can't possibly match if (col1.size() != col2.size()) return false; // Helper class, so we don't have to do a whole lot of autoboxing class Count { // Initialize as 1, as we would increment it anyway public int count = 1; } final Map<T, Count> counts = new HashMap<>(); // Count the items in col1 for (final T item : col1) { final Count count = counts.get(item); if (count != null) count.count++; else // If the map doesn't contain the item, put a new count counts.put(item, new Count()); } // Subtract the count of items in col2 for (final T item : col2) { final Count count = counts.get(item); // If the map doesn't contain the item, or the count is already reduced to 0, the lists are unequal if (count == null || count.count == 0) return false; count.count--; } // At this point, both collections are equal. // Both have the same length, and for any counter to be unequal to zero, there would have to be an element in col2 which is not in col1, but this is checked in the second loop, as @holger pointed out. return true; } 

Answer 7

I would say that these answers miss the trick.

Flea, in his basic, wonderful and concise book, Effective Java, says in paragraph 47 “Know and use libraries,” “To summarize, don't reinvent the wheel.” And he gives some very clear reasons why not.

Here are a few answers that suggest methods from CollectionUtils from CollectionUtils Apache Commons Collections, but none of them have found the most beautiful and elegant way to answer this question :

 Collection<Object> culprits = CollectionUtils.disjunction( list1, list2 ); if( ! culprits.isEmpty() ){ // ... then in most cases you will ardently wish to do something to these culprits: // at the very least, name-and-shame them. } 

Culprits : that is, elements that are not common to both Lists . Determining which culprits belong to list1 and which list2 is relatively simple 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 that it is not a software failure , but inherent in the subtleties / ambiguities of the desired task.

---

NB. At first, I was disappointed that none of the CollectionUtils methods provides an overloaded version that allows you to impose your own Comparator (so that you can override equals to suit your goals).

But from collection4 4.0 there is a new class, Equator which "defines equality between objects of type T". When they look at the source code of collection4 CollectionUtils.java they seem to use this with some methods, but as far as I can tell, this does not apply to methods at the top of the file using the CardinalityHelper class ... which include disjunction and intersection .

I assume that the Apache people have not reached this point yet because it is not trivial: you need to create something like the class "AbstractEquatingCollection", which instead of using the methods inherent in its equals and hashCode elements will have to use those from Equator for all the main methods such as add , contains , etc. In fact, when you look at the source code, AbstractCollection does not implement add , nor does its abstract subclasses such as AbstractSet ... you have to wait for specific classes such as HashSet and ArrayList to be implemented before add . Pretty headache.

I believe that while watching this space. An obvious intermediate solution would be to wrap all your elements in a special wrapper class that uses equals and hashCode to implement the type of equality you want, and then manipulate the Collections these wrapper objects.

Answer 8

Think about how you do it yourself, without a computer or programming language. I give you two lists of elements, and you should tell me if they contain the same elements. How do you do this?

One approach, as mentioned above, is to sort the lists and then the phased elements to make sure they are equal (which is what List.equals does). This means that you are allowed to modify the lists or you are allowed to copy them - and, without knowing the purpose, I do not know if this is allowed / both of them.

Another approach would be to go through each list by counting how many times each item appears. If both lists have the same count at the end, they have the same items. The code for this would be to transfer each list to an elem -> (# of times the elem appears in the list) map elem -> (# of times the elem appears in the list) , and then call equals on two maps. If the cards are HashMap , each of these transfers is an O (N) operation, like a comparison. This will give you a fairly efficient algorithm in terms of time, due to some additional memory.

Answer 9

I had the same problem and came up with a different solution. This also works when duplicates are involved:

 public static boolean equalsWithoutOrder(List<?> fst, List<?> snd){ if(fst != null && snd != null){ if(fst.size() == snd.size()){ // create copied lists so the original list is not modified List<?> cfst = new ArrayList<Object>(fst); List<?> csnd = new ArrayList<Object>(snd); Iterator<?> ifst = cfst.iterator(); boolean foundEqualObject; while( ifst.hasNext() ){ Iterator<?> isnd = csnd.iterator(); foundEqualObject = false; while( isnd.hasNext() ){ if( ifst.next().equals(isnd.next()) ){ ifst.remove(); isnd.remove(); foundEqualObject = true; break; } } if( !foundEqualObject ){ // fail early break; } } if(cfst.isEmpty()){ //both temporary lists have the same size return true; } } }else if( fst == null && snd == null ){ return true; } return false; } 

Advantages over some other solutions:

• less complexity O (N²) (although I have not tested its real performance compared to the solutions in other answers here);
• comes out earlier;
• checks for null;
• even works when using duplicates: if you have an array [1,2,3,3] and another array [1,2,2,3] , most of the solutions here tell you that they are the same if you don't take into account the order. This solution avoids this by removing equal items from temporary lists;
• uses semantic equality ( equals ) rather than referential equality ( == );
• does not sort itens, therefore for this solution it is not necessary to sort ( implement Comparable ).

Answer 10

Converting lists in Guava Multiset works very well. They are compared regardless of their order, and duplicate elements are also taken into account.

 static <T> boolean equalsIgnoreOrder(List<T> a, List<T> b) { return ImmutableMultiset.copyOf(a).equals(ImmutableMultiset.copyOf(b)); } assert equalsIgnoreOrder(ImmutableList.of(3, 1, 2), ImmutableList.of(2, 1, 3)); assert !equalsIgnoreOrder(ImmutableList.of(1), ImmutableList.of(1, 1)); 

Answer 11

A solution that uses the CollectionUtils subtraction method:

 import static org.apache.commons.collections15.CollectionUtils.subtract; public class CollectionUtils { static public <T> boolean equals(Collection<? extends T> a, Collection<? extends T> b) { if (a == null && b == null) return true; if (a == null || b == null || a.size() != b.size()) return false; return subtract(a, b).size() == 0 && subtract(a, b).size() == 0; } } 

Answer 12

If you don’t want to sort the collections, and you need a result that ["A" "B" "C"] is not equal to ["B" "B" "A" "C"],

 l1.containsAll(l2)&&l2.containsAll(l1) 

not enough, you also need to check the size:

  List<String> l1 =Arrays.asList("A","A","B","C"); List<String> l2 =Arrays.asList("A","B","C"); List<String> l3 =Arrays.asList("A","B","C"); System.out.println(l1.containsAll(l2)&&l2.containsAll(l1));//cautions, this will be true System.out.println(isListEqualsWithoutOrder(l1,l2));//false as expected System.out.println(l3.containsAll(l2)&&l2.containsAll(l3));//true as expected System.out.println(isListEqualsWithoutOrder(l2,l3));//true as expected public static boolean isListEqualsWithoutOrder(List<String> l1, List<String> l2) { return l1.size()==l2.size() && l1.containsAll(l2)&&l2.containsAll(l1); } 

Answer 13

If you care about order, just use the equals method:

 list1.equals(list2) 

If you don't need order, use this.

 Collections.sort(list1); Collections.sort(list2); list1.equals(list2) 

Answer 14

Best of both worlds [@DiddiZ, @Chalkos]: this one is mainly based on the @Chalkos method, but it fixes the error (ifst.next ()) and improves the initial checks (taken from @DiddiZ) and also removes the need to copy the first collection ( just removes the items from the copy of the second collection).

Without requiring hashing or sorting, as well as the possibility of early existence in case of inequality, this is still the most effective implementation. That is, if you do not have a collection length of thousands or more, and a very simple hashing function.

 public static <T> boolean isCollectionMatch(Collection<T> one, Collection<T> two) { if (one == two) return true; // If either list is null, return whether the other is empty if (one == null) return two.isEmpty(); if (two == null) return one.isEmpty(); // If lengths are not equal, they can't possibly match if (one.size() != two.size()) return false; // copy the second list, so it can be modified final List<T> ctwo = new ArrayList<>(two); for (T itm : one) { Iterator<T> it = ctwo.iterator(); boolean gotEq = false; while (it.hasNext()) { if (itm.equals(it.next())) { it.remove(); gotEq = true; break; } } if (!gotEq) return false; } // All elements in one were found in two, and they're the same size. return true; } 

Answer 15

This is an alternative way to check if lists of arrays are equal, which may contain null values:

 List listA = Arrays.asList(null, "b", "c"); List listB = Arrays.asList("b", "c", null); System.out.println(checkEquality(listA, listB)); // will return TRUE private List<String> getSortedArrayList(List<String> arrayList) { String[] array = arrayList.toArray(new String[arrayList.size()]); Arrays.sort(array, new Comparator<String>() { @Override public int compare(String o1, String o2) { if (o1 == null && o2 == null) { return 0; } if (o1 == null) { return 1; } if (o2 == null) { return -1; } return o1.compareTo(o2); } }); return new ArrayList(Arrays.asList(array)); } private Boolean checkEquality(List<String> listA, List<String> listB) { listA = getSortedArrayList(listA); listB = getSortedArrayList(listB); String[] arrayA = listA.toArray(new String[listA.size()]); String[] arrayB = listB.toArray(new String[listB.size()]); return Arrays.deepEquals(arrayA, arrayB); } 

Answer 16

My solution for this. It's not so cool, but it works well.

 public static boolean isEqualCollection(List<?> a, List<?> b) { if (a == null || b == null) { throw new NullPointerException("The list a and b must be not null."); } if (a.size() != b.size()) { return false; } List<?> bCopy = new ArrayList<Object>(b); for (int i = 0; i < a.size(); i++) { for (int j = 0; j < bCopy.size(); j++) { if (a.get(i).equals(bCopy.get(j))) { bCopy.remove(j); break; } } } return bCopy.isEmpty(); } 

Answer 17

In this case, the lists {"a", "b"} and {"b", "a"} are equal. And {"a", "b"} and {"b", "a", "c"} are not equal. If you use a list of complex objects, be sure to override the equals method, as containsAll uses it internally.

 if (oneList.size() == secondList.size() && oneList.containsAll(secondList)){ areEqual = true; }