Checking two lists for equal items

Question

I'm using this code for checking if two List<T> are equal or not:

public static bool EqualsAll<T>(this IList<T> a, IList<T> b)
{
    if (a == null || b == null)
        return (a == null && b == null);

    if (a.Count != b.Count)
        return false;

    EqualityComparer<T> comparer = EqualityComparer<T>.Default;

    for (int i = 0; i < a.Count; i++)
    {
        if (!comparer.Equals(a[i], b[i]))
            return false;
    }

    return true;
}

Now assume that I'm using this code for checking two big lists. Is this code efficient?

Answer 1

Checking whether two lists are equal is naturally an O(n) operation. So yes, your code looks efficient.

Note that you could also replace your for loop with Enumerable.SequenceEqual

public static bool EqualsAll<T>(this IList<T> a, IList<T> b)
{
    if (a == null || b == null)
        return (a == null && b == null);

    if (a.Count != b.Count)
        return false;

    return a.SequenceEqual(b);
}

If you take a look at its implementation, you'll notice that it's very similar to yours. It might be just a tiny bit less efficient - so if performance is an issue here, measure both approaches, and then weigh readability/maintainability vs performance gains.

On a different note, I would rename the method to SequenceEqual and consider it a "specialization" of Enumerable.SequenceEqual for lists.

I would also consider throwing an exception if either argument is null. This would be consistent with the BCL's own extension methods (Select, Where, ToList, SequenceEqual, Any, All, etc).

Answer 2

Your code is efficient.

Why not expose an overload allowing the caller to pass in a comparer?

public static bool EqualsAll<T>(this IList<T> a, IList<T> b)
{
    return EqualsAll(a, b, null); // there is a slight performance gain in passing null here.
    // It is how it is done in other parts of the framework.
}

public static bool EqualsAll<T>(this IList<T> a, IList<T> b, IEqualityComparer<T> comparer)
{
    if (a == null || b == null) // I agree with dcastro that throwing probably makes more sense here.
        return (a == null && b == null);

    if (a.Count != b.Count)
        return false;

    if (comparer == null)
        comparer = EqualityComparer<T>.Default;

    for (int i = 0; i < a.Count; i++)
    {
        if (!comparer.Equals(a[i], b[i]))
            return false;
    }

    return true;
}

Answer 3

I would also consider throwing an exception if either argument is null. This would be consistent with the BCL's own extension methods

I agree with this, but as an interesting side note as to why you want to throw exceptions consider the following test case.

IList<string> list1 = null;
IList<string> list2 = null;

Assert.IsTrue(list1.EqualsAll(list2));

This test would actually pass but it's certainly a very odd thing to do; considering calling a method on a null value wouldn't normally work. It just so happens extension methods behave differently in this regard.

Whenever you're working with null values consider the following definitions:

• not set
• invalid
• undefined
• not allocated
• not really a list

If you think about nulls in these terms it becomes clear that throwing an exception is the only logical thing to do.