从链接列表中删除

Question

从previous question我问，RemoveAll是根据条件从List<>中删除的最简洁的方法。很想知道从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>

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

另请参见：Extension Methods (C# Programming Guide)

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属性是只读的。