CODEWITHSUNDEEP
javacollections
Grundlefleck
Grundlefleck

Reputation: 129227

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.

Upvotes: 349

Views: 625609

Answers (22)

alperk01
alperk01

Reputation: 343

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

Upvotes: 0

Pierre
Pierre

Reputation: 35246

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.

Upvotes: 1

Shahriar Zaman
Shahriar Zaman

Reputation: 938

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
}

Upvotes: 0

Laurence Gonsalves
Laurence Gonsalves

Reputation: 143144

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:

Upvotes: 477

grandmaximum
grandmaximum

Reputation: 131

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

Upvotes: 7

Mateusz Niedbal
Mateusz Niedbal

Reputation: 346

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

Upvotes: -1

jp93k
jp93k

Reputation: 1

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

Upvotes: 0

Attila Hejja
Attila Hejja

Reputation: 79

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

Upvotes: 0

Delark
Delark

Reputation: 1323

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.

Upvotes: 0

dutoitns
dutoitns

Reputation: 2253

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

Upvotes: 0

daiscog
daiscog

Reputation: 12057

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

Upvotes: 48

Alexander Oh
Alexander Oh

Reputation: 25631

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

Upvotes: 2

Reimeus
Reimeus

Reputation: 159754

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

Objects.equals(list1, list2)

Upvotes: 22

Felixuko
Felixuko

Reputation: 60

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

Upvotes: 2

Andrew
Andrew

Reputation: 224

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

Upvotes: 9

Pavlo Zvarych
Pavlo Zvarych

Reputation: 645

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

Upvotes: 2

Jaydip Halake
Jaydip Halake

Reputation: 87

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

Upvotes: 1

Lee Meador
Lee Meador

Reputation: 12985

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

Upvotes: 4

David Zhao
David Zhao

Reputation: 4514

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)

Upvotes: -1

amischiefr
amischiefr

Reputation: 4880

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.

Upvotes: -3

Tom
Tom

Reputation: 21902

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.

Upvotes: 116

daveb
daveb

Reputation: 76181

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

Upvotes: 8

Related Questions