c# - 从 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) 操作。即使该列表不是巨大的，而是非常大的，这也是一个问题。

相反，我们只需要在不使用 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");