从C＃链表中删除节点 [英] Removing node from c# LinkedList

问题描述

我试图删除从System.Collections.Generic.LinkedList，其中T是具有多个属性的对象的节点。我想基于匹配的属性，如之一的的 T.paint.color =删除节点蓝色的的。一开始我尝试：

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

当然这失败，出现集合了之后修改枚举数被实例化的错误。 MSDN上的例子是一个简单的字符串数组，并使用类似：

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.

推荐答案

所以，这里有两个选项。最简单的代码，但效果最差的，选择是仅抓住所有的项目删除，然后删除所有你发现他们之后：

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

请注意，了ToList 通话非常重要这里;这是至关重要的其中，不会被允许推迟基础列表迭代可言，否则你会得到同样的并发修改错误。

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.

这里有两个问题。首先，你需要持有的所有项目在内存中删除。不是太糟糕了，除非你有一个的很多的（我的意思是很多）。更大的问题是，你没有节点对象，你有节点的值，所以你需要从一开始遍历整个列表来查找每一个对象并删除它们。你已经变成一个O（n）操作成为O（n ^ 2）操作。这是一个问题，即使该列表不是极大的相，只是不平凡的大小。

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.

相反，我们将只需要步行集合，而不使用的foreach ，使我们不得不对节点对象的引用，所以我们不通过适当的管理得到并发修改异常时/ 。我们如何遍历和修改集合

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;
    }
}

这是不是很漂亮，但它会多的更有效。

现在，最好的LinkedList 将有一个 removeall过的方法，这样你就不需要这一切的时候来打扰。可悲的是，它没有之一。在光明的一面，虽然，你可以添加自己的扩展方法：

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

这篇关于从C＃链表中删除节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！