从C#链表中删除节点

Question

从C#链表中删除节点

7

我正在尝试从一个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");

感谢您的选择。

- Sap

你的答案已经发布在这里了，我想：https://dev59.com/PUjSa4cB1Zd3GeqPJu0- - Xepos

+1. 投票赞成，主要是因为有非常详细的答案（问题本身还好，但很可能可以通过简单搜索来回答）。 - Alexei Levenkov

Sap，既然您似乎是新来的，您应该知道鼓励的做法是在足够多的答案出现后选择一个答案进行“接受”。您可以通过点击上下评分图标下方左侧的复选标记来接受。当您接受它时，它将变为绿色。发布它的人将获得15个声望点数。 - philologon

@Xepos：虽然如此，Servys的回答更好，直接回答了Antonello的问题（链接中提到的那个问题）中从未涉及的CarList.Remove。Servy所提供的只是纯粹的美感。 - philologon

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Servy · Accepted Answer

这里有两个选项。最容易编码但效果最差的选项是，只需获取所有要删除的项目，然后在找到它们后全部删除：

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