Removing node from c# LinkedList

Question

I am trying to delete a node from a System.Collections.Generic.LinkedList, where T is an object with multiple properties. I would like to delete the node based on matching one of the properties, such as T.paint.color = "blue". At first I tried:

foreach (Car carNode in carList)
{
    if (carNode.paint.color == "blue")
    {
         carList.Remove(carNode);
    }
}

Of course this fails with the "Collection was modified after the enumerator was instantiated" error. The example on MSDN is a simple array of strings and uses something like:

sentence.Remove("old");

My question is how (or if) I can use something like (using pseudo code):

carList.Remove(the node where carList.paint.color == "blue");

Thanks.

Answer 1

So there are two options here. The easiest to code, but least effective, option is to just grab all of the items to remove and then remove them all after you've found them:

var carsToRemove = carList.Where(carNode => carNode.paint.color == "blue")
    .ToList();

foreach(var car in carsToRemove)
    carList.Remove(car);

Note that the ToList call is very important here; it's essential that Where not be allowed to defer iteration of the underlying list at all, or else you'll get the same concurrent modification errors.

There are two problems here. First, you need to hold all of the items to remove in memory. Not too bad unless you have a lot (and I mean a lot). More problematic is that you don't have node objects, you have the values of the nodes, so you need to traverse the whole list from the start to find each object and remove them. You've turned an O(n) operation into an O(n^2) operation. That's a problem even if the list isn't ginormous, but just non-trivially sized.

Instead we'll simply need to walk the collection without using a foreach so that we have references to the Node objects, and so that we don't get concurrent modification exceptions by properly managing when/how we traverse and modify the collection.

var currentNode = list.First;
while (currentNode != null)
{
    if (currentNode.Value.color == "blue")
    {
        var toRemove = currentNode;
        currentNode = currentNode.Next;
        list.Remove(toRemove);
    }
    else
    {
        currentNode = currentNode.Next;
    }
}

It's not quite as pretty, but it'll be much more efficient.

Now, ideally LinkedList would have a RemoveAll method so that you don't need to bother with this all of the time. Sadly, it doesn't have one. On the bright side though, you can just add your own extension method:

public static void RemoveAll<T>(this LinkedList<T> list, Func<T, bool> predicate)
{
    var currentNode = list.First;
    while (currentNode != null)
    {
        if (predicate(currentNode.Value))
        {
            var toRemove = currentNode;
            currentNode = currentNode.Next;
            list.Remove(toRemove);
        }
        else
        {
            currentNode = currentNode.Next;
        }
    }
}

Now we can just write:

carList.RemoveAll(car => car.paint.color == "blue");