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

Question

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.

Answer 1

Probably the easiest way for any list would be:

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

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

Answer 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 `true` iff the given `Collection`s 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.

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

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.

Answer 6

If the cardinality of items doesn't matter (meaning: repeated elements are considered as one), then there is a way to do this without having to sort:

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

This will create a Set out of each List, and then use HashSet's equals method which (of course) disregards ordering.

If cardinality matters, then you must confine yourself to facilities provided by List; @jschoen's answer would be more fitting in that case.

Answer 7

Converting the lists to Guava's Multiset works very well. They are compared regardless of their order and duplicate elements are taken into account as well.

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 8

This is based on @cHao solution. I included several fixes and performance improvements. This runs roughly twice as fast the equals-ordered-copy solution. Works for any collection type. Empty collections and null are regarded as 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 9

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

One approach, as mentioned above, is to sort the lists and then go element-by-element to see if they're equal (which is what List.equals does). This means either you're allowed to modify the lists or you're allowed to copy them -- and without knowing the assignment, I can't know if either/both of those are allowed.

Another approach would be to go through each list, counting how many times each element appears. If both lists have the same counts at the end, they have the same elements. The code for that would be to translate each list to a map of elem -> (# of times the elem appears in the list) and then call equals on the two maps. If the maps are HashMap, each of those translations is an O(N) operation, as is the comparison. That's going to give you a pretty efficient algorithm in terms of time, at the cost of some extra memory.

Answer 10

I had this same problem and came up with a different solution. This one 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 compared to some other solutions:

• less than O(N²) complexity (although I have not tested it's real performance comparing to solutions in other answers here);
• exits early;
• checks for null;
• works even when duplicates are involved: if you have an array [1,2,3,3] and another array [1,2,2,3] most solutions here tell you they are the same when not considering the order. This solution avoids this by removing equal elements from the temporary lists;
• uses semantic equality (equals) and not reference equality (==);
• does not sort itens, so they don't need to be sortable (by implement Comparable) for this solution to work.

Answer 11

One-line method :)

1. Collection's items NOT implement the interface Comparable<? super T>

    static boolean isEqualCollection(Collection<?> a, Collection<?> b) {
        return a == b || (a != null && b != null && a.size() == b.size()
            && a.stream().collect(Collectors.toMap(Function.identity(), s -> 1L, Long::sum)).equals(b.stream().collect(Collectors.toMap(Function.identity(), s -> 1L, Long::sum))));
    }
   

2. Collection's items implement the interface Comparable<? super T>

    static <T extends Comparable<? super T>> boolean  isEqualCollection2(Collection<T> a, Collection<T> b) {
      return a == b || (a != null && b != null && a.size() == b.size() && a.stream().sorted().collect(Collectors.toList()).equals(b.stream().sorted().collect(Collectors.toList())));
    }
   

3. support Android5 & Android6 via https://github.com/retrostreams/android-retrostreams

   static boolean isEqualCollection(Collection<?> a, Collection<?> b) {
    return a == b || (a != null && b != null && a.size() == b.size()
            && StreamSupport.stream(a).collect(Collectors.toMap(Function.identity(), s->1L, Longs::sum)).equals(StreamSupport.stream(b).collect(Collectors.toMap(Function.identity(), s->1L, Longs::sum))));
   }
   

////Test case

    boolean isEquals1 = isEqualCollection(null, null); //true
    boolean isEquals2 = isEqualCollection(null, Arrays.asList("1", "2")); //false
    boolean isEquals3 = isEqualCollection(Arrays.asList("1", "2"), null); //false
    boolean isEquals4 = isEqualCollection(Arrays.asList("1", "2", "2"), Arrays.asList("1", "1", "2")); //false
    boolean isEquals5 = isEqualCollection(Arrays.asList("1", "2"), Arrays.asList("2", "1")); //true
    boolean isEquals6 = isEqualCollection(Arrays.asList("1", 2.0), Arrays.asList(2.0, "1")); //true
    boolean isEquals7 = isEqualCollection(Arrays.asList("1", 2.0, 100L), Arrays.asList(2.0, 100L, "1")); //true
    boolean isEquals8 = isEqualCollection(Arrays.asList("1", null, 2.0, 100L), Arrays.asList(2.0, null, 100L, "1")); //true

Answer 12

If you don't hope to sort the collections and you need the result that ["A" "B" "C"] is not equals to ["B" "B" "A" "C"],

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

is not enough, you propably need to check the size too :

    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

Solution which leverages CollectionUtils subtract 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 14

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

list1.equals(list2)

If you don't care order then use this

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

Answer 15

I think this is a simple solution:

public boolean equalLists(List<String> one, List<String> two) {
    if (one == null && two == null) {
        return true;
    }
    
    if (one == null || two == null) {
        return false;
    }
    
    return new HashSet<>(one).equals(new HashSet<>(two));
}

Answer 16

Best of both worlds [@DiddiZ, @Chalkos]: this one mainly builds upon @Chalkos method, but fixes a bug (ifst.next()), and improves initial checks (taken from @DiddiZ) as well as removes the need to copy the first collection (just removes items from a copy of the second collection).

Not requiring a hashing function or sorting, and enabling an early exist on un-equality, this is the most efficient implementation yet. That is unless you have a collection length in the 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 17

It is an alternative way to check equality of array lists which can 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 18

My solution for this. It is not so cool, but 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 19

Assuming if we can modify one list, with the support of java 8 removeIf

  assertTrue(listA.size(), listB.size());
  listB.removeIf(listA::contains);
  assertTrue(listB.isEmpty());

Answer 20

In that case lists {"a", "b"} and {"b","a"} are equal. And {"a", "b"} and {"b","a","c"} are not equal. If you use list of complex objects, remember to override equals method, as containsAll uses it inside.

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