Simple way to find if two different lists contain exactly the same elements

Question

What is the simplest way to find if two Lists contain exactly the same elements  in the standard Java libraries    It shouldn t matter if the two Lists are the same instance or not  and it shouldn t matter if the type parameter of the Lists are different   e g   List list1 List lt String gt  list2          construct etc  list1 add  A    list2 add  A        the function  given these two lists  should return true   There s probably something staring me in the face I know  -     EDIT  To clarify  I was looking for the EXACT same elements and number of elements  in order

User · Answer

I posted a bunch of stuff in comments I think it warrants its own answer.

As everyone says here, using equals() depends on the order. If you don't care about order, you have 3 options.

Option 1

Use containsAll(). This option is not ideal, in my opinion, because it offers worst case performance, O(n^2).

Option 2

There are two variations to this:

2a) If you don't care about maintaining the order ofyour lists... use Collections.sort() on both list. Then use the equals(). This is O(nlogn), because you do two sorts, and then an O(n) comparison.

2b) If you need to maintain the lists' order, you can copy both lists first. THEN you can use solution 2a on both the copied lists. However this might be unattractive if copying is very expensive.

This leads to:

Option 3

If your requirements are the same as part 2b, but copying is too expensive. You can use a TreeSet to do the sorting for you. Dump each list into its own TreeSet. It will be sorted in the set, and the original lists will remain intact. Then perform an equals() comparison on both TreeSets. The TreeSetss can be built in O(nlogn) time, and the equals() is O(n).

Take your pick :-).

EDIT: I almost forgot the same caveat that Laurence Gonsalves points out. The TreeSet implementation will eliminate duplicates. If you care about duplicates, you will need some sort of sorted multiset.

User · Answer

In addition to Laurence s answer  if you also want to make it null-safe   private static  lt T gt  boolean listEqualsIgnoreOrder List lt T gt  list1  List lt T gt  list2        if  list1    null          return list2  null      if  list2    null          return list1    null      return new HashSet lt  gt  list1  equals new HashSet lt  gt  list2

User · Answer

Sample code   public static   lt  T  gt   boolean isListDifferent List  lt  T  gt   previousList          List  lt  T  gt   newList         int sizePrevoisList   -1      int sizeNewList   -1       if  previousList    null  amp  amp   previousList isEmpty              sizePrevoisList   previousList size              if  newList    null  amp  amp   newList isEmpty              sizeNewList   newList size               if   sizePrevoisList    -1   amp  amp   sizeNewList    -1             return false             if  sizeNewList    sizePrevoisList            return true             List n prevois   new ArrayList previousList       List n new   new ArrayList newList        try           Collections sort n prevois           Collections sort n new         catch  ClassCastException exp            return true             for  int i   0  i  lt  sizeNewList  i              Object obj prevois   n prevois get i           Object obj new   n new get i           if  obj new equals obj prevois                    Object are same           else               return true                       return false

User · Answer

Solution for case when two lists have the same elements  but different order   public boolean isDifferentLists List lt Integer gt  listOne  List lt Integer gt  listTwo        if isNullLists listOne  listTwo             return false             if  hasDifferentSize listOne  listTwo             return true             List lt Integer gt  listOneCopy   Lists newArrayList listOne       List lt Integer gt  listTwoCopy   Lists newArrayList listTwo       listOneCopy removeAll listTwoCopy        return CollectionUtils isNotEmpty listOneCopy      private boolean isNullLists List lt Integer gt  listOne  List lt Integer gt  listTwo        return listOne    null  amp  amp  listTwo    null     private boolean hasDifferentSize List lt Integer gt  listOne  List lt Integer gt  listTwo        return  listOne    null  amp  amp  listTwo    null      listOne    null  amp  amp  listTwo    null      listOne size      listTwo size

User · Answer

Very late to the party but wanted to add this null safe check   Objects equals list1  list2

User · Answer

If you care about order  then just use the equals method   list1 equals list2    From the javadoc      Compares the specified object with   this list for equality  Returns true   if and only if the specified object is   also a list  both lists have the same   size  and all corresponding pairs of   elements in the two lists are equal     Two elements e1 and e2 are equal if    e1  null   e2  null     e1 equals e2     In other words  two   lists are defined to be equal if they   contain the same elements in the same   order  This definition ensures that   the equals method works properly   across different implementations of   the List interface    If you want to check independent of order  you could copy all of the elements to Sets and use equals on the resulting Sets   public static  lt T gt  boolean listEqualsIgnoreOrder List lt T gt  list1  List lt T gt  list2        return new HashSet lt  gt  list1  equals new HashSet lt  gt  list2        A limitation of this approach is that it not only ignores order  but also frequency of duplicate elements  For example  if list1 was   A    B    A   and list2 was   A    B    B   the Set approach would consider them to be equal   If you need to be insensitive to order but sensitive to the frequency of duplicates you can either    sort both lists  or copies  before comparing them  as done in this answer to another question or copy all elements to a Multiset

User · Answer

Tom s answer is excellent I agree fully with his answers   An interesting aspect of this question is  whether you need the List type itself and its inherent ordering   If not you can degrade to Iterable or Collection which gives you some flexibility on passing around data structures that are sorted on insertion time  rather than at the time when you want to check   If the order never matters  and you don t have duplicate elements  consider using a Set   If the order matters but is defined by insertion time  and you don t have duplicates  consider a LinkedHashSet which is like a TreeSet but is ordered by insertion time  duplicates are not counted   This also gives you O 1  amortized access insted of O log n

User · Answer

It depends on what concrete List class you are using   The abstract class AbstractCollection has a method called containsAll Collection  that takes another collection   a List is a collection  and      Returns true if this collection contains all of the elements in the specified collection     So if an ArrayList is being passed in you can call this method to see if they are exactly the same          List foo   new ArrayList        List bar   new ArrayList        String str    foobar        foo add str       bar add str        foo containsAll bar     The reason for containsAll   is because it iterates through the first list looking for the match in the second list   So if they are out of order equals   will not pick it up   EDIT  I just want to make a comment here about the amortized running time of performing the various options being offered   Is running time important   Sure   Is it the only thing you should consider   No   The cost of copying EVERY single element from your lists into other lists takes time  and it also takes up a good chunk of memory  effectively doubling the memory you are using    So if memory in your JVM isn t a concern  which it should generally be  then you still need to consider the time it takes to copy every element from two lists into two TreeSets   Remember it is sorting every element as it enters them     My final advice   You need to consider your data set and how many elements you have in your data set  and also how large each object in your data set is before you can make a good decision here   Play around with them  create one each way and see which one runs faster   It s a good exercise

User · Answer

You can use Apache s org apache commons collections library  http   commons apache org collections apidocs org apache commons collections ListUtils html  public static boolean isEqualList java util Collection list1                                java util Collection list2

User · Answer

Try this version which does not require order to be the same but does support having multiple of the same value  They match only if each has the same quantity of any value   public boolean arraysMatch List lt String gt  elements1  List lt String gt  elements2           Optional quick test since size must match     if  elements1 size      elements2 size              return false            List lt String gt  work   newArrayList elements2       for  String element   elements1            if   work remove element                 return false                      return work isEmpty

User · Answer

I know this is an old thread  but none of the other answers fully solved my use case  I guess Guava Multiset might do the same  but there is no example here   Please excuse my formatting  I am still new to posting on stack exchange  Additionally let me know if there are any errors   Lets say you have List lt T gt  a and List lt T gt  b and you want to check if they are equal with the following conditions   1  O n  expected running time 2  Equality is defined as  For all elements in a or b  the number of times the element occurs in a is equal to the number of times the element occurs in b  Element equality is defined as T equals    private boolean listsAreEquivelent List lt   extends Object gt  a  List lt   extends Object gt  b        if a  null            if b  null                  Here 2 null lists are equivelent  You may want to change this              return true            else               return false                      if b  null            return false            Map lt Object  Integer gt  tempMap   new HashMap lt  gt         for Object element   a            Integer currentCount   tempMap get element           if currentCount    null                tempMap put element  1             else               tempMap put element  currentCount 1                       for Object element   b            Integer currentCount   tempMap get element           if currentCount    null                return false            else               tempMap put element  currentCount-1                       for Integer count   tempMap values              if count    0                return false                      return true      Running time is O n  because we are doing O 2 n  insertions into a hashmap and O 3 n  hashmap selects  I have not fully tested this code  so beware       Returns true  listsAreEquivelent Arrays asList  A   A   B   Arrays asList  B   A   A     listsAreEquivelent null null     Returns false  listsAreEquivelent Arrays asList  A   A   B   Arrays asList  B   A   B     listsAreEquivelent Arrays asList  A   A   B   Arrays asList  A   B     listsAreEquivelent Arrays asList  A   A   B   null

User · Answer

Check both lists are not nulls  If their sizes are different  then these lists are not equal  Build maps consisting of the lists  elements as keys and their repeats as values and compare the maps   Assumptions  if both lists are nulls  I consider them equal   private boolean compareLists List lt   gt  l1  List lt   gt  l2        if  l1    null  amp  amp  l2    null            return true        else if  l1    null    l2    null            return false             if  l1 size      l2 size              return false             Map lt    Integer gt  m1   toMap l1       Map lt    Integer gt  m2   toMap l2        return m1 equals m2      private Map lt Object  Integer gt  toMap List lt   gt  list          Effective size  not to resize in the future      int mapSize    int   list size     0 75   1       Map lt Object  Integer gt  map   new HashMap lt  gt  mapSize        for  Object o   list            Integer count   map get o           if  count    null                map put o  1             else               map put o    count                        System out println map       return map      Please  note  method equals should be properly defined for these objects  https   stackoverflow com a 24814634 4587961

User · Answer

List equals    http   java sun com j2se 1 5 docs api java util List html equals java lang Object

User · Answer

list1 equals list2     If your list contains a custom Class MyClass  this class must override the equals function    class MyClass       int field 0     0verride   public boolean equals Object other                    if this  other  return true          if other  null      other instanceof MyClass   return false          return this field   MyClass class cast other  field                  Note  if you want to test equals on a java util Set rather than a java util List  then your object must override the hashCode  function

User · Answer

The equals method on List will do this  Lists are ordered  so to be equal two Lists must have the same elements in the same order   return list1 equals list2

User · Answer

If you re using  or are happy to use  Apache Commons Collections  you can use CollectionUtils isEqualCollection which  returns true iff the given Collections contain exactly the same elements with exactly the same cardinalities

[java] Simple way to find if two different lists contain exactly the same elements?

Examples related to java

Examples related to collections