从链表中删除元素

Question

根据我之前提出的问题，在基于条件删除List<>中的元素时，RemoveAll是最干净的方法。好奇如何从LinkedList中删除，因为那里没有RemoveAll函数。

List<ItemClass> itemsToErase = new List<ItemClass>();
    foreach(ItemClass itm in DS)
    {
           if(itm.ToBeRemoved)
                itemsToErase .Add(itm);
    }
    foreach(ItemClass eraseItem in itemsToErase)
    {
          DS.Remove(eraseItem );
    }          

编辑：DS 的类型是 LinkedList<ItemClass>

- softwarematter

Answer 1

虽然你不能在使用foreach迭代LinkedList<T>时从中删除节点，但是你可以通过遍历每个LinkedListNode<T>的Next属性手动迭代LinkedList<T>。只需记住在删除节点之前的下一个节点：

var list = new LinkedList<int>(Enumerable.Range(0, 10));
var node = list.First;
while (node != null)
{
    var next = node.Next;
    if (node.Value % 2 == 0)
        list.Remove(node);
    node = next;
}

---

扩展方法：

public static int RemoveAll<T>(this LinkedList<T> list, Predicate<T> match)
{
    if (list == null)
    {
        throw new ArgumentNullException("list");
    }
    if (match == null)
    {
        throw new ArgumentNullException("match");
    }
    var count = 0;
    var node = list.First;
    while (node != null)
    {
        var next = node.Next;
        if (match(node.Value))
        {
            list.Remove(node);
            count++;
        }
        node = next;
    }
    return count;
}

用法：

LinkedList<ItemClass> DS = ...
DS.RemoveAll(itm => itm.ToBeRemoved);

另请参阅：扩展方法（C#编程指南）

- dtb

---

如果您在不止一个地方使用它，这是一个很好的扩展方法的候选。 - svick

@svick：好主意；扩展方法已添加。 - dtb

我是新手扩展方法。您能否请告诉我如何针对我的情况使用这个特定的扩展方法。 - softwarematter

Answer 2

从System.Collections.Generic.LinkedList<T>中删除项的唯一方法是使用其中一个Remove()方法。然而，这个操作比从List<T>中删除一个项要快(O(1)而不是O(n))，因为这个操作可以在本地执行。被删除项后面的项没有被移动，只需要将被删除项前后的两个节点链接起来。removed.Previous.Next = removed.Next; removed.Next.Previous = removed.Previous;。这是在内部完成的，因为Previous和Next属性是只读的。

- Olivier Jacot-Descombes

---

虽然 Remove(LinkedListNode<T>) 是 O(1) 的，但是 Remove(T) 是 O(n) 的，因为它需要先找到要删除的项。 - svick