How do I compare two lists for equality (not caring about order) C#

I have two lists and I want them to be checked to see if they have the same elements. I also want to ignore the order of the two lists.
I just want it to check if they contain the same values.

Since we have now many implementations that have a complexity of O(n²), i’ll post the one i mentioned in the comment above.

    public static bool CompareLists<T>(List<T> aListA, List<T> aListB)
    {
        if (aListA == null || aListB == null || aListA.Count != aListB.Count)
            return false;
        if (aListA.Count == 0)
            return true;

        Dictionary<T, int> lookUp = new Dictionary<T, int>();
        // create index for the first list
        for(int i = 0; i < aListA.Count; i++)
        {
            int count = 0;
            if (!lookUp.TryGetValue(aListA[i], out count))
            {
                lookUp.Add(aListA[i], 1);
                continue;
            }
            lookUp[aListA[i]] = count + 1;
        }
        for (int i = 0; i < aListB.Count; i++)
        {
            int count = 0;
            if (!lookUp.TryGetValue(aListB[i], out count))
            {
                // early exit as the current value in B doesn't exist in the lookUp (and not in ListA)
                return false;
            }
            count--;
            if (count <= 0)
                lookUp.Remove(aListB[i]);
            else
                lookUp[aListB[i]] = count;
        }
        // if there are remaining elements in the lookUp, that means ListA contains elements that do not exist in ListB
        return lookUp.Count == 0;
    }

This has a linear complexity (O(n) or if you prefer O(2n) but that’s actually pointless). A dictionary lookup has a constant complexity (O(1)). So the overall performance of this method should grow linearly with the number of elements.
“List.Contains” has a complexity of O(n). In most of the other solutions here you would execute List.Contains “n”-times so you get a quadratic complexity (O(n²))
If you have trouble understanding what’s happening, here are some explanations:

  • First we do an early exit if one (or both) of the lists is null or if they have a different element count. In this case the lists can’t be “equal”. We don’t consider the case when both lists are null as “equal”.
  • The second early exit is a special case when both lists exist, but are empty. This is considered “equal”.
  • The first loop will iterate through all elements in ListA and check if that element is already in the dictionary. If it is, we simply increase the value that is stored in the dictionary and update the value in the dictionary. If it isn’t yet in the dictionary, we add it with a count of 1
  • After the first loop we have a dictionary of all elements of ListA without duplicates.
  • The second loop iterates over all elements in ListB. It again checks if the element exists in the dictionary. However this time if it doesn’t exist, we just found an element in ListB that doesn’t exist in ListA. If the element is found in the dictionary we decrease the counter for that element by 1. If the counter hits “0” we “used up” all elements of that type and we remove it from the dictionary. Otherwise we simply update the counter for that element.
  • If all items in ListA exist in ListB we should have matched all elements properly and the counter for each element type should have reached “0”. Since we removed elements that have reached “0” the Dictionary should be empty at the end. If it is empty then ListA and ListB contains the same elements. If there are elements remaining, some elements from ListA are missing in ListB

As an example

List<int> A = new List<int>(new int[] { 1, 5, 6, 7, 3, 1 });
List<int> B = new List<int>(new int[] { 6, 3, 5, 1, 1, 7 });
if (CompareLists(A, B))
    Debug.Log("Equal");
else
    Debug.Log("Not equal");

This prints “Equal”. If we add another “1” at the end of ListA and another “5” to ListB

List<int> A = new List<int>(new int[] { 1, 5, 6, 7, 3, 1, 1 });
List<int> B = new List<int>(new int[] { 6, 3, 5, 1, 1, 7, 5 });

It will print “Not equal” as ListA has three times a "1"s and only one “5” while ListB has two "1"s and two "5"s

First, are they the same length?
Second, is every element of list A to be found in list B?

You can write this easily in LINQ using .Contains().

You can make it go faster by doing a pass through list A to build an index, then a pass through list B to check against the index.

It’s slightly more complex if the lists may contain duplicates.

You can use the Intersect method. Here is a simple console application :

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        var nums1 = new int[] { 2, 4, 6, 8, 10, 9 };
        var nums2 = new int[] { 1, 3, 6, 9, 12, 2 };

        if (nums1.Intersect(nums2).Any()) // check if there is equal items
        {
            var equalItems = nums1.Intersect(nums2); // get list of equal items (2, 6, 9)

            foreach (var item in equalItems)
            {
                Console.WriteLine(item);
            }
        }
    }
}

For anyone coming across this,

It’s easier if you just sort the two lists/arrays. Then json serialize them and compare the two strings.

using System;
using Newtonsoft.Json;
					
public class Program
{
	public static void Main()
	{
		string[] list1 = new string[] {"a", "b", "c", "d"};
		string[] list2 = new string[] {"d", "b", "c", "a"};
		
		Array.Sort(list1);
		Array.Sort(list2);
		Console.WriteLine(JsonConvert.SerializeObject(list1) == JsonConvert.SerializeObject(list2));
	}
}

You can obviously convert that to a function pretty easily. Probably return false if they are different sizes to save on some processing. Not necessarily computationally the most efficient, but it works and it’s easy to understand.

Here you go, it has a Generic type of elements so it’s portable everywhere for you

that’s the code:

using System.Collections.Generic;
using UnityEngine;

public class ListComparing : MonoBehaviour {

	List<string> names1 = new List<string>(new string[] {"Jordan", "Jake", "Mike", "John", "Sandra"});
	List<string> names2 = new List<string>(new string[] {"Mike", "John", "Jake", "Sandra", "Jordan"});

	List<int> ages1 = new List<int>(new int[] {3, 15, 7, 10});
	List<int> ages2 = new List<int>(new int[] {7, 15, 10, 3});

	void Start ()
	{
		//Here we give the generic value a type of string parameter to compare the lists by a string value
		print( 
			"The list of names1 and names2 equality is: " + 
			CompareLists<string> (names1, names2) 
		);

		//Here we give the generic value a type of int parameter to compare the lists by an int value
		print( 
			"The list of ages1 and ages2 equality is: " + 
			CompareLists<int> (ages1, ages2) 
		);
	}

	//A method of type bool to give you the result of equality between two lists
	bool CompareLists<T> (List<T> list1, List<T> list2)
	{
		//here we check the count of list elements if they match, it can work also if the list count doesn't meet, to do it just comment out this if statement
		if (list1.Count != list2.Count)
			return false;

		//here we check and find every element from the list1 in the list2
		foreach (var item in list1)
			if (list2.Find(i => i.Equals(item)) == null)
				return false;

		//here we check and find every element from the list2 in the list1 to make sure they don't have repeated and mismatched elements
		foreach (var item in list2)
			if (list1.Find(i => i.Equals(item)) == null)
				return false;

		//return true because we didn't find any missing element
		return true;
	}
}

The easiest way in my opinions is the following:
You have your two list

List A = new List();
List B = new List();

Now we want to check if they have the same element:
You can sort both of the lists and check if they are equal or not using LINQ.
if you want to keep the original lists unchanged you can create two copies of your original list and compare the copies this way you do not change the order in your original lists

private bool CheckIfListsAreQual()
    {
        List<int> ACopy = new List<int>(A);
        List<int> BCopy = new List<int>(B);
        A.Sort();
        B.Sort();
        return playerSelection.SequenceEqual(boardSelection);//using System.Linq; (at this at top of script)
    }`