從鏈接列表中刪除

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屬性是隻讀的。