351

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.

Improve this question
2
  • Do the elements have to be in the same order? Commented Jul 2, 2009 at 17:31
  • This might never affect you but beware that hibernate persistent sets sometimes don't honour the equals contract - search see opensource.atlassian.com/projects/hibernate/browse/HHH-3799 Commented Jul 2, 2009 at 19:32

22 Answers 22

Reset to default
480

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 <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) { return new HashSet<>(list1).equals(new HashSet<>(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:

Improve this answer
Sign up to request clarification or add additional context in comments.

19 Comments

Couldn't you use containsAll if you want to check independent of order?
I don't know about the implementation details of containsAll, but it seems like it could be bad. If containsAll calls contains() over and over, you will have an O(n^2) alg. The sets overall should be O(nlogn)
Actually, if the sets are just going to be O(nlogn), another approach is to call Collections.sort() on a list, and then use equals. If you want to preserve order though, you would need to copy the list, and that may be expensive and favor the set solution... so you have to think about your situation :-).
Just as a quick comment for those who use containsAll(): Remember to check that both lists have the same size beforehand! This allows you to use just one single call to containsAll().
@Dennis The size check really only works if you know that each list contains only distinct elements. For example, given a = [x, y, x] and b = [x, y, z] then the sizes are equal and b.containsAll(a) will return true, but b contains an element not in a.
|
117

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.

Improve this answer

9 Comments

If you care about duplicates you can always test that the size of the collections are equal before any other tests.
More specifically, if having duplicates indicates inequality, the size of the lists must be the same before any equality check has a chance to succeed.
@laz: checking the size won't work if different elements are duplicated in the two lists. eg: [A, A, B] vs [A, B, B] are equal size.
ContainsAll would I think give the wrong answer, you would need to containsAll both ways. a.containsAll(b) && b.containsAll(a)
ContainsAll(), even if called both ways, still wouldn't give the right results if frequency of elements is significant: Arrays.asList(1,2,3,3).containsAll(Arrays.asList(1,2,2,3)) && Arrays.asList(1,2,2,3).containsAll(Arrays.asList(1,2,3,3)) gives true instead of false.
|
49

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

Improve this answer

1 Comment

Very nice hashmap-based implementation. The runtime should be O(n), and if there are lots of repeating elements, it uses minimal memory to keep track (basically tracks the frequency (cardinality) of elements using a map for each collection). Downside is it has an additional O(n) memory usage.
23

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

Objects.equals(list1, list2)
Improve this answer

Comments

9

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);
Improve this answer

7 Comments

Lists are not ordered unless you sort them.
Sigh@Myself. Such an obvious answer. You know it's been too long a day when you can't even Ctrl+F a web page any longer. :)
@mmyers: items in lists are not ordered unless you sort them. Lists themselves have an implicit ordering of items (by index), which don't change unless you change the items in the list. (vs. Sets or Collections where there's not a guarantee of consistent ordering if you iterate through them twice)
I think what daveb means by saying lists are ordered is that List.equals takes the order of the elements into consideration to determine equality. See the Javadoc.
What I mean is that a list containing {"A", "B"} and a list containing {"B", "A"} would be unequal with this method. That may very well be what is intended, but I wanted to make sure no one was overlooking it.
|
9

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);
Improve this answer

Comments

7 
private boolean listHaveEqualObjects(List<?> list1, List<?> list2){ return list1.containsAll(list2) && list2.containsAll(list1);
Improve this answer

2 Comments

please add a short discription to describe how your solution is different from other solutions.
better: list1.containsAll(list2) && list2.size() == list1.size();
4

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(); }
Improve this answer

3 Comments

work.remove(element) is O(n), so this solution is O(n^2)
Or O(n1 * n2) which is sort of the same
I have also used same strategy because it is handling all scenarios and collection size is not that big then O(n^2) not matters
2

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()); }
Improve this answer

2 Comments

I think you don't need to copy listTwo.
You might also like to note why you used removeAll() instead of containsAll() (my understanding is that if listTwo contains duplicates that are contained just once in listOne, the containsAll() approach would incorrectly report the lists as equal).
2

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)); }
Improve this answer

2 Comments

You can simplify the checks: if (list1 == null) return list2==null; if (list2 == null) return false;
Doesn't work if the lists are [a,a,b,c] & [a,b,c] and will return true unless adding an additional check to ensure the size of the lists are same.
2

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

Improve this answer

Comments

1

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; }
Improve this answer

Comments

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

Improve this answer

3 Comments

should the line: return this.field== MyClass.class.cast(other); be return this.field== MyClass.class.cast(other).field;
@alpere oh! you're right ! I'm gonna fix it. Thanks !
Check for other==null is redundant - just if (!(other instanceof MyClass)) return false; is enough, because null is not an instance of any class, ie null instanceof anyclass returns false
0

My solution is for the cases where you don't care about the ordering within the Lists - in other words: Lists with the same elements but DIFFERENT ordering will be considered to have the same contents.

Example: ["word1", "word2"] and ["word2", "word1"] is considered to have the same content.

I've addressed ordering, I also just need to say something about duplicates. Lists need to have the same number of elements to be considered equal.

Example: ["word1"] and ["word1", "word1"] is considered to NOT have the same content.

My solution:

public class ListUtil { public static <T> boolean hasSameContents(List<T> firstList, List<T> secondList) { if (firstList == secondList) { // same object return true; } if (firstList != null && secondList != null) { if (firstList.isEmpty() && secondList.isEmpty()) { return true; } if (firstList.size() != secondList.size()) { return false; } List<T> tmpSecondList = new ArrayList<>(secondList); Object currFirstObject = null; for (int i=1 ; i<=firstList.size() ; i++) { currFirstObject = firstList.get(i-1); boolean removed = tmpSecondList.remove(currFirstObject); if (!removed) { return false; } if (i != firstList.size()) { // Not the last element if (tmpSecondList.isEmpty()) { return false; } } } if (tmpSecondList.isEmpty()) { return true; } } return false; } }

I've tested it with Strings as follows:

@Test public void testHasSameContents() throws Exception { // comparing with same list => no duplicate elements Assert.isTrue(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("one", "two", "three"))); // comparing with same list => duplicate elements Assert.isTrue(ListUtil.hasSameContents(List.of("one", "two", "three", "one"), List.of("one", "two", "three", "one"))); // compare with disordered list => no duplicate elements Assert.isTrue(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("three", "two", "one"))); // compare with disordered list => duplicate elements Assert.isTrue(ListUtil.hasSameContents(List.of("one", "two", "three", "one"), List.of("three", "two", "one", "one"))); // comparing with different list => same size, no duplicate elements Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("four", "five", "six"))); // comparing with different list => same size, duplicate elements Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "two"), List.of("one", "two", "three"))); Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("one", "two", "two"))); // comparing with different list => different size, no duplicate elements Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three", "four"), List.of("one", "two", "three"))); Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("one", "two", "three", "four"))); // comparing with different list => different sizes, duplicate elements Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three", "one"), List.of("one", "two", "three"))); Assert.isFalse(ListUtil.hasSameContents(List.of("one", "two", "three"), List.of("one", "two", "three", "one"))); }
Improve this answer

Comments

0

I know this migth be extremely late but I personally use this function. If someone wants to do some benchmark testing that would be great.

public static<X> boolean areEqual(List<X> a, List<X> b, BiPredicate<X, X> AEqualsB) { boolean aIsNull = a == null; boolean bIsNull = b == null; if (aIsNull || bIsNull) { return aIsNull == bIsNull; } int size = a.size(); boolean sameSize = size == b.size(); if (!sameSize) {return false;} else { for (int i = 0; i < size; i++) { X aX = a.get(i), bX = b.get(i); boolean areEqual = AEqualsB.test(aX, bX); if (!areEqual) { return false; } } return true; } }

BTW I am aware the first 5 lines could be simplified with an XOR "^" plus an else, but believe it or not it is difficult for me to come with the correct XOR.

I guess the efficiency of it would depend on the type of predicate, but at the same time it allows you to check for custom potential equalitites, while disregarding differences that may not matter for the coder.

Here is an example of the code.

ListUtils.areEqual(newElements, oldElements, Element::areEqual) public boolean areEqual(Element e) { return optionalAdapterId() == e.optionalAdapterId() && value == e.value && valueTotal == e.valueTotal && stockTotal == e.stockTotal && element_title.equals(e.element_title); }

As for what efficiency goes, I am of the idea that any iteration is always expensive, that's why whenever I need to use this function with large lists, I perform its operation on a separate thread, and retrieve the response on the one that requires it, even though it would be very nice to KNOW at which point, is it beneficial to do it on a different thread, what is the number of items that would require such threading, that information would be added on the documentation.

Improve this answer

Comments

0

here is a way to compare two collection that considers duplications in them. As a consequence, the collection sizes not necessarily are the same. So, it will looking in 'actual' for 'expected':

 private static <T> boolean containsAllExpected(Collection<T> actual, Collection<T> expected) { if (actual == null && expected == null) { return true; } if (actual == null || expected == null) { return false; } Collection<T> a = new ArrayList<>(actual); Collection<T> e = new ArrayList<>(expected); Iterator<T> ei = e.iterator(); while (ei.hasNext()) { T item = ei.next(); if (a.contains(item)) { ei.remove(); a.remove(item); } else { return false; } } return true; }

Enjoy :)

Improve this answer

Comments

0

This should do the trick in O(n) time.

public static <T> boolean isEqualCollection(Collection<T> c1, Collection<T> c2){ if(nonNull(c1) && nonNull(c2)){ Map<T, Long> c1Counts = c1.stream().collect(Collectors.groupingBy(i -> i, Collectors.counting())); for(T item : c2) { Long count = c1Counts.getOrDefault(item, 0L); if(count.equals(0L)){ return false; } else { c1Counts.put(item, count - 1L); } } return true; } return isNull(c1) && isNull(c2); }
Improve this answer

Comments

0

Maybe not the best solution, but it works.

data class(val a: Int) { override fun hashCode(): Int { // provide your implementation } } val list1 = listOf<D>(D(1), D(2), D(3)) val list2 = listOf<D>(D(1), D(2), D(3)) fun <T> isSame(list1: List<T>, list2: List<T>): Boolean { if (list1.size != list2.size) return false val hash1 = list1.map { it.hashCode() }.toSet() val hash2 = list2.map { it.hashCode() }.toSet() return (hash1.intersect(hash2)).size == hash1.size }
Improve this answer

Comments

0 
public static int size(final Collection collection) { return collection == null ? 0 : collection.size(); } // Works for duplicate objects and null values in the collection public static <T> boolean areSame(final Collection<T> l1, final Collection<T> l2) { if (size(l1) == 0 && size(l2) == 0) return true; if (size(l1) != size(l2)) return false; Map<Object, Integer> countMap = new HashMap<>(); // object -> count for (T t : l1) { // unique lists which are not same will be returned by this condition if (!l2.contains(t)) return false; // Map holds the object count for duplicate objects like ("a", "b", "b") Integer count = countMap.get(t); countMap.put(t, (count == null ? 0 : count) + 1); } for (T t : l2) { Integer count = countMap.get(t); if (count == null || count == 0) return false; // Must be at least one object in map --count; if (count == 0) countMap.remove(t); else countMap.put(t, count); } return countMap.size() == 0; }

Test cases:

@Test public void testAreSame(){ List<String> l1 = Arrays.asList(); List<String> l2 = Arrays.asList("a"); assertFalse(CollectionUtil.areSame(l1, l2)); l1 = Arrays.asList("b", "c", "d"); l2 = Arrays.asList("d", "b", "c"); assertTrue(CollectionUtil.areSame(l1, l2)); l1 = Arrays.asList("b", "c", "d"); l2 = Arrays.asList("d", "a", "c"); assertFalse(CollectionUtil.areSame(l1, l2)); l1 = Arrays.asList("b", "c", "d", "e"); l2 = Arrays.asList("d", "b", "c"); assertFalse(CollectionUtil.areSame(l1, l2)); l1 = Arrays.asList("a", "a", "b"); l2 = Arrays.asList("b", "b", "a"); assertFalse(CollectionUtil.areSame(l1, l2)); l1 = Arrays.asList("a", null, null); l2 = Arrays.asList(null, null, "a"); assertTrue(CollectionUtil.areSame(l1, l2)); l1 = Arrays.asList("a", "b", null); l2 = Arrays.asList("b", null, "a"); assertTrue(CollectionUtil.areSame(l1, l2)); }
Improve this answer

Comments

-1

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)
Improve this answer

5 Comments

This also requires list elements to be in the same order.
you can sort the list before comparing
Sure, you can do that provided the types stored in the list or sortable (or you have a comparator set up). However, the Apache implementation algorithm is no different than the regular list1.equals(list2), except for being static. I do see where I misunderstood the question and it was in fact asking how to compare list items in the same order. My bad!
@DavidZhao : link is dead.
commons.apache.org/proper/commons-collections/apidocs/org/…
-1

!Collections.disjoint(Collection1, Collection2) will return true if they have same elements

Improve this answer

1 Comment

this will return true if they have any of the same elements, not if they have exactly the same elements.
-3

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.

Improve this answer

5 Comments

Wouldn't it have to be foo.containsAll(bar) && bar.containsAll(foo); ?
No, it goes through every element in foo and sees if bar contains that element. It then ensures that the length is the same of the two lists. If for every foo there is an element in bar such that foo.element == bar.element and foo.length == bar.length then they contain the same elements.
do we know if there is an efficiency guarantee? or is this typically O(n^2)?
Like any other array that iterates through looking for a matching element the worst case running time is going to be O(n^2). In this case, it looks like the implementation is indeed iterating through one element at a time looking for the match. I won't speculate on the amortized running time, but yes the worst case is O(n^2).
This doesn't work: {1,2,2}.containsAll({1,1,2}) and vice-verse, and the two lists have the same size.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.