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

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<String> 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.

This question is related to java collections

The answer is



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.


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<String> elements1, List<String> elements2) {
    // Optional quick test since size must match
    if (elements1.size() != elements2.size()) {
        return false;
    }
    List<String> work = newArrayList(elements2);
    for (String element : elements1) {
        if (!work.remove(element)) {
            return false;
        }
    }
    return work.isEmpty();
}

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.


In addition to Laurence's answer, if you also want to make it null-safe:

private static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    if (list1 == null)
        return list2==null;
    if (list2 == null)
        return list1 == null;
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

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).


Solution for case when two lists have the same elements, but different order:

public boolean isDifferentLists(List<Integer> listOne, List<Integer> listTwo) {
    if(isNullLists(listOne, listTwo)) {
        return false;
    }

    if (hasDifferentSize(listOne, listTwo)) {
        return true;
    }

    List<Integer> listOneCopy = Lists.newArrayList(listOne);
    List<Integer> listTwoCopy = Lists.newArrayList(listTwo);
    listOneCopy.removeAll(listTwoCopy);

    return CollectionUtils.isNotEmpty(listOneCopy);
}

private boolean isNullLists(List<Integer> listOne, List<Integer> listTwo) {
    return listOne == null && listTwo == null;
}

private boolean hasDifferentSize(List<Integer> listOne, List<Integer> listTwo) {
    return (listOne == null && listTwo != null) || (listOne != null && listTwo == null) || (listOne.size() != listTwo.size());
}

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<T> a and List<T> 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<? extends Object> a, List<? extends Object> 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<Object, Integer> tempMap = new HashMap<>();
    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);

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)

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<?> l1, List<?> l2) {
    if (l1 == null && l2 == null) {
        return true;
    } else if (l1 == null || l2 == null) {
        return false;
    }

    if (l1.size() != l2.size()) {
        return false;
    }

    Map<?, Integer> m1 = toMap(l1);
    Map<?, Integer> m2 = toMap(l2);

    return m1.equals(m2);
}

private Map<Object, Integer> toMap(List<?> list) {
    //Effective size, not to resize in the future.
    int mapSize = (int) (list.size() / 0.75 + 1);
    Map<Object, Integer> map = new HashMap<>(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


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

Sample code:

public static '<'T'>' boolean isListDifferent(List'<'T'>' previousList,
        List'<'T'>' newList) {

    int sizePrevoisList = -1;
    int sizeNewList = -1;

    if (previousList != null && !previousList.isEmpty()) {
        sizePrevoisList = previousList.size();
    }
    if (newList != null && !newList.isEmpty()) {
        sizeNewList = newList.size();
    }

    if ((sizePrevoisList == -1) && (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 < 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;
}

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.


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."


Very late to the party but wanted to add this null safe check:

Objects.equals(list1, list2)