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.

Your answer is posted here I think: stackoverflow.com/questions/1288696/… — Xepos
– Xepos, Commented Oct 23, 2013 at 18:30
+1. Voting up mainly since there is very detailed answer (ok question otherwise, but likely could be answered by simple search instead) — Alexei Levenkov
– Alexei Levenkov, Commented Oct 23, 2013 at 18:50
Sap, since you appear to be new here, you should know that the encouraged practice is to "accept" one answer or another after enough of them have come in for you to decide which one to accept. You can accept by clicking the check mark on the left below the up/down rating icons. When you accept it, it will turn green. The person who posted it gets 15 reputation points. — philologon
– philologon, Commented Oct 23, 2013 at 19:02
@Xepos: True as that is, Servys' answer is much better and directly answers the question about CarList.Remove that never came up in Antonello's question (the one linked to). What Servy offers is just plain beauty. — philologon
– philologon, Commented Oct 23, 2013 at 19:06

AlexDev · Accepted Answer · 2014-03-31 19:52:35Z

15

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

edited Mar 31, 2014 at 19:52

AlexDev

4,8971 gold badge34 silver badges38 bronze badges

answered Oct 23, 2013 at 18:33

Servy

204k27 gold badges347 silver badges470 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

bopapa_1979 Over a year ago

The second approach is the textbook example from any Computer Science data structures class, and is the correct approach in almost all cases. Since you're using C#, I might suggest wrapping this in a method and passing a predicate rather than hardcoding currentNode.Value.Color == "blue" so you can use the same method to remove nodes based on any condition you like.

Yosi Dahari Over a year ago

Side note - foreach(var car in carsToRemove) carList.Remove(car); not using {} is bad practice.

Servy Over a year ago

@Yosi That's a matter of personal preference. I judge whether or not wrapping a single statement in braces on a case by case basis based on whether or not that particular usage requires the braces for clarity or not. Here it is very obvious what's going on, and there's no real possibility for confusion as to what scope the statement applies to. To me adding braces just adds more filler that I need to sort through, thus harming readability. In cases where it's less clear what block a statement applies to, I use braces.

bopapa_1979 Over a year ago

@Servy, I JUST POSTED THAT SAME METHOD before I saw your comment. But MINE has a usage example!!! Seriously, add the sample to yours, and I'll remove mine :) Also, they're pretty much identical line-for-line, so I guess we passed each other's code review! GREATNESS.

Yosi Dahari Over a year ago

@Servy - can you please refer to if/where it's preferred to use for loop for this purpose?

|

Collectives™ on Stack Overflow

Removing node from c# LinkedList

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related