从c#LinkedList中删除节点

Question

我试图从System.Collections.Generic.LinkedList中删除一个节点,其中T是一个具有多个属性的对象.我想基于匹配其中一个属性删除节点,例如T.paint.color ="blue".起初我尝试过:

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

当然,这失败了"在枚举器实例化后修改了集合"错误.MSDN上的示例是一个简单的字符串数组,使用类似于:

sentence.Remove("old");

我的问题是如何(或者如果)我可以使用(使用伪代码):

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

谢谢.

Answer 1

所以这里有两种选择.最简单的代码,但效率最低的选项是只需抓取所有要删除的项目,然后在找到它们后将其全部删除:

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

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

请注意,ToList这里的通话非常重要; 至关重要的是,Where根本不允许推迟基础列表的迭代,否则你将得到相同的并发修改错误.

这里有两个问题.首先,您需要保留要在内存中删除的所有项目.除非你有很多(我的意思很多),也不算太糟糕.更有问题的是,您没有节点对象,您拥有节点的值,因此您需要从头开始遍历整个列表以查找每个对象并将其删除.您已将O(n)操作转换为O(n ^ 2)操作.这是一个问题,即使列表不是巨大的,但只是非常小的.

相反,我们只需要在不使用a的情况下遍历集合,foreach以便我们对Node对象进行引用,这样我们就不会通过正确管理遍历和修改集合的时间/方式来获得并发修改异常.

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方法,这样你就不需要一直打扰这个.可悲的是,它没有一个.但从好的方面来说,您可以添加自己的扩展方法:

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

现在我们可以写:

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