Usuwanie z obiektu LinkedList

Question

Od previous question zadałem pytanie, RemoveAll jest najczystszym sposobem usunięcia z List<> na podstawie warunku. Ciekawe, jaki jest najlepszy sposób usunięcia z LinkedList, ponieważ nie ma tam funkcji 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); 
    }      

EDIT: DS jest typu LinkedList<ItemClass>

Answer 1

Chociaż nie można usunąć węzły z LinkedList<T> podczas iteracji go foreach można ręcznie iteracyjne LinkedList<T> wykonując właściwość każdego LinkedListNode<T>Next. Wystarczy pamiętać, następny węzeł węzła przed wyjęciem go:

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

---

metodę rozszerzenia:

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

Zastosowanie:

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

Patrz także: Extension Methods (C# Programming Guide)

Answer 2

Jedynym sposobem na usunięcie przedmiotu z System.Collections.Generic.LinkedList<T> jest użycie jednej z metod Remove(). Jednak ta operacja jest szybsza niż usunięcie elementu z formularza List<T> (O(1) zamiast O(n)), ponieważ operacja może być wykonywana lokalnie. Elementy za usuniętym elementem nie muszą być przenoszone, tylko dwa węzły przed i po usuniętym elemencie muszą być ze sobą połączone. removed.Previous.Next = removed.Next; removed.Next.Previous = removed.Previous;. Odbywa się to wewnętrznie, ponieważ właściwości Previous i Next są tylko do odczytu.