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 lt String gt  listA     a    b    c   ArrayList lt String gt  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

User · Answer

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  amp  amp l2 containsAll l1    is not enough  you propably need to check the size too        List lt String gt  l1  Arrays asList  A   A   B   C        List lt String gt  l2  Arrays asList  A   B   C        List lt String gt  l3  Arrays asList  A   B   C         System out println l1 containsAll l2  amp  amp l2 containsAll l1     cautions  this will be true     System out println isListEqualsWithoutOrder l1 l2     false as expected      System out println l3 containsAll l2  amp  amp l2 containsAll l3     true as expected     System out println isListEqualsWithoutOrder l2 l3     true as expected       public static boolean isListEqualsWithoutOrder List lt String gt  l1  List lt String gt  l2            return l1 size    l2 size    amp  amp  l1 containsAll l2  amp  amp l2 containsAll l1

User · Answer

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    amp  amp  oneList containsAll secondList            areEqual   true

User · Answer

Apache Commons Collections to the rescue once again   List lt String gt  listA   Arrays asList  a    b    b    c    List lt String gt  listB   Arrays asList  b    c    a    b    System out println CollectionUtils isEqualCollection listA  listB       true    nbsp     List lt String gt  listC   Arrays asList  a    b    c    List lt String gt  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

User · Answer

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 lt String gt  one  List lt String gt  two            if  one    null  amp  amp  two    null           return true             if  one    null  amp  amp  two    null            one    null  amp  amp  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 lt String gt  one        two   new ArrayList lt String gt  two           Collections sort one       Collections sort two             return one equals two

User · Answer

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 lt Object gt  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

User · Answer

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 lt String gt  list1  final List lt String gt  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 lt String  Count gt  counts   new HashMap lt  gt             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 lt String  Count gt  entry   counts entrySet              if  entry getValue   count    0  return false             return true

User · Answer

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 - gt     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

User · Answer

Probably the easiest way for any list would be   listA containsAll listB   amp  amp  listB containsAll listA

User · Answer

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 lt   gt  fst  List lt   gt  snd     if fst    null  amp  amp  snd    null       if fst size      snd size              create copied lists so the original list is not modified       List lt   gt  cfst   new ArrayList lt Object gt  fst         List lt   gt  csnd   new ArrayList lt Object gt  snd          Iterator lt   gt  ifst   cfst iterator          boolean foundEqualObject        while  ifst hasNext              Iterator lt   gt  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  amp  amp  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

User · Answer

One-line method     Collection s items NOT implement the interface Comparable lt   super T gt   static boolean isEqualCollection Collection lt   gt  a  Collection lt   gt  b         return a    b     a    null  amp  amp  b    null  amp  amp  a size      b size             amp  amp  a stream   collect Collectors toMap Function identity    s - gt  1L  Long  sum   equals b stream   collect Collectors toMap Function identity    s - gt  1L  Long  sum           Collection s items implement the interface Comparable lt   super T gt   static  lt T extends Comparable lt   super T gt  gt  boolean  isEqualCollection2 Collection lt T gt  a  Collection lt T gt  b       return a    b     a    null  amp  amp  b    null  amp  amp  a size      b size    amp  amp  a stream   sorted   collect Collectors toList    equals b stream   sorted   collect Collectors toList            support Android5  amp  Android6 via https   github com retrostreams android-retrostreams static boolean isEqualCollection Collection lt   gt  a  Collection lt   gt  b     return a    b     a    null  amp  amp  b    null  amp  amp  a size      b size             amp  amp  StreamSupport stream a  collect Collectors toMap Function identity    s- gt 1L  Longs  sum   equals StreamSupport stream b  collect Collectors toMap Function identity    s- gt 1L  Longs  sum               Test case     boolean isEquals1   isEqualCollection null  null     true     boolean isEquals2   isEqualCollection null  Arrays asList  quot 1 quot    quot 2 quot       false     boolean isEquals3   isEqualCollection Arrays asList  quot 1 quot    quot 2 quot    null     false     boolean isEquals4   isEqualCollection Arrays asList  quot 1 quot    quot 2 quot    quot 2 quot    Arrays asList  quot 1 quot    quot 1 quot    quot 2 quot       false     boolean isEquals5   isEqualCollection Arrays asList  quot 1 quot    quot 2 quot    Arrays asList  quot 2 quot    quot 1 quot       true     boolean isEquals6   isEqualCollection Arrays asList  quot 1 quot   2 0   Arrays asList 2 0   quot 1 quot       true     boolean isEquals7   isEqualCollection Arrays asList  quot 1 quot   2 0  100L   Arrays asList 2 0  100L   quot 1 quot       true     boolean isEquals8   isEqualCollection Arrays asList  quot 1 quot   null  2 0  100L   Arrays asList 2 0  null  100L   quot 1 quot       true

User · Answer

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      lt p gt     Empty collections and   code null  are regarded as equal      public static  lt T gt  boolean haveSameElements Collection lt T gt  col1  Collection lt T gt  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 lt T  Count gt  counts   new HashMap lt  gt             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

User · Answer

Solution which leverages CollectionUtils subtract method   import static org apache commons collections15 CollectionUtils subtract   public class CollectionUtils     static public  lt T gt  boolean equals Collection lt   extends T gt  a  Collection lt   extends T gt  b        if  a    null  amp  amp  b    null        return true      if  a    null    b    null    a size      b size          return false      return subtract a  b  size      0  amp  amp  subtract a  b  size      0

User · Answer

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 lt String gt  getSortedArrayList List lt String gt  arrayList        String   array   arrayList toArray new String arrayList size           Arrays sort array  new Comparator lt String gt                   Override         public int compare String o1  String o2                        if  o1    null  amp  amp  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 lt String gt  listA  List lt String gt  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

User · Answer

My solution for this  It is not so cool  but works well   public static boolean isEqualCollection List lt   gt  a  List lt   gt  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 lt   gt  bCopy   new ArrayList lt Object gt  b        for  int i   0  i  lt  a size    i               for  int j   0  j  lt  bCopy size    j                  if  a get i  equals bCopy get j                      bCopy remove j                   break                                     return bCopy isEmpty

User · Answer

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  lt T gt  boolean isCollectionMatch Collection lt T gt  one  Collection lt T gt  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 lt T gt  ctwo   new ArrayList lt  gt  two        for  T itm   one            Iterator lt T gt  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

User · Answer

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 lt  gt  listA  equals new HashSet lt  gt  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

User · Answer

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

User · Answer

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  lt T gt  boolean equalsIgnoreOrder List lt T gt  a  List lt T gt  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

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

Examples related to java

Examples related to arraylist