Iterate through 2 Lists

Question

I have a List<T1> of items and a second List<T2> of items. Both lists are sorted alphabetically by the property A. I know that the list of items in List<T2> are a subset of List<T1> and no items in List<T2> exists that don't exist in List<T1>.

I need to iterate through List<T1> and change a variable every time it matches a variable in List<T2>. What is the fastest and best way to do this? I am assuming I need to iterate through both lists but I know doing a nested foreach wouldn't make sense.

Answer 1

For this type of thing, I prefer a double walking for loop. See the example below.

var super = new List<Contact>();
super.Add(new Contact() {Name = "John"});
super.Add(new Contact() {Name = "Larry"});
super.Add(new Contact() {Name = "Smith"});
super.Add(new Contact() {Name = "Corey"});

var sub = new List<Contact>();
sub.Add(new Contact() {Name = "Larry"});
sub.Add(new Contact() {Name = "Smith"});

var subCount = 0;
for(int i=0; i<super.Count && subCount < sub.Count; i++)
{
    if (super[i].Name == sub[subCount].Name)
    {
        Act(super[i], sub[subCount]);
        subCount++;
    }
}

Where Act(...) performs whatever action you are looking to do.

The loop increments the super list each time, but only increments the sub list when you find a match.

Note that this only works because of your two assumptions. 1) The lists are both sorted and 2) The second list is a subset of the first.

Answer 2

If the lists aren't too large, this simplest way to do this is to call Contains:

foreach(var item in list1) {
    if (list2.Contains(item) {
        //Do something
    }
}

You can make it faster by calling BinarySearch using a custom IComparer<T>, like this:

class MyComparer : IComparer<YourClass> {
    private MyComparer() { }
    public static readonly MyComparer Instance = new MyComparer();

    public int CompareTo(YourClass a, YourClass b) {
        //TODO: Handle nulls
        return a.SomeProperty.CompareTo(b.SomeProperty);
    }
}
foreach(var item in list1) {
    if (list2.BinarySearch(item, MyComparer.Instance) >= 0) {
        //Do something
    }
}

In .Net 3.5, you can make it faster by using a HashSet<T>:

var hashset = new HashSet<YourClass>(list2);
foreach(var item in list1) {
    if (hashset.Contains(item) {
        //Do something
    }
}

If your lists are very large, you should measure the performance of each option and choose accordingly.
Otherwise, go for one of the first option, which is simplest.