Удаление из связанного списка C#

ProgramBox

Удаление из связанного списка C#

Post author:admin
Запись опубликована:9 февраля, 2023
Post category:Вопросы по программированию

#c#

Вопрос:

Я пытаюсь удалить узел, если x в настоящее время соответствует int в моем связанном списке.

Я пробовал это, но как только он удаляет узел, он выдает ошибку при проверке цикла foreach

 public void DeleteNode(int x, LinkedList<name> myLinkedList) {
    foreach (name item in myLinkedList) {
         if (item.num.equals(x)) mylinkedList.Remove(x);
    }
}

Надеюсь, это имеет смысл.

Ответ №1:

Да, вы не можете перебирать коллекцию и изменять ее одновременно. Тем не менее, LinkedList<T> позволяет выполнять итерацию явно довольно легко:

 public void DeleteNode(int x, LinkedList<name> myLinkedList) {
    var node = myLinkedList.First;
    while (node != null) {
        var nextNode = node.Next;
        if (node.Value.num == x) {
            myLinkedList.Remove(node);
        }
        node = nextNode;
    }
}

Обратите внимание, что вам не сойдет с рук просто взять node = node.Next; в качестве последней строки; узел становится недействительным при его удалении.

Этот подход позволяет выполнить однократный обход списка за O (n) и, вероятно, будет наиболее эффективным подходом, который вы найдете. Это не требует никакого копирования или работы с коллекцией (скажем List<T> ) с менее эффективной сложностью удаления.

1. Это также имеет то преимущество, что оно равно O (n) вместо O (n ^ 2), учитывая временную сложность Remove(T) versus Remove(LinkedListNode<T>) .

2. @RonWarholic: Безусловно. Я предполагал, что это неявно, но я отредактирую, чтобы указать это 🙂

3. Спасибо, Джон, я все еще получаю сообщение об ошибке в первой части, я не могу преобразовать .LinkedListNode<T> в .LinkedList. Мой связанный список представляет собой набор элементов, а не только 1 int (хотя int — это та часть, которую я сравниваю)

4. @timmy: Какая «первая часть»? Пожалуйста, укажите, какую строку моего кода вы имеете в виду, и точную ошибку. Я отредактирую свой пост, чтобы включить объявление метода.

5. @Jadoon: LinkedList<T> для начала не претендует на потокобезопасность.

Ответ №2:

Если вы вызовете remove во время a foreach , это приведет к аннулированию перечислителя, поэтому это недопустимо.

Измените свой foreach на простой for цикл.

Ответ №3:

В этой ситуации я обычно создаю временную коллекцию и добавляю ее в нее, если ее необходимо удалить. Затем я просматриваю этот список, удаляя его из оригинала.

Ответ №4:

Способ, которым я пишу это, без аннулирования итератора, является:

 foreach(var item in list.Where(w=>w.num.Equals(x)).ToArray())
   list.Remove(item);

1. Это то, что сделал бы художник Шлемиэль.

2. @Джон, честно говоря, я сомневаюсь, что это действительно имеет значение.. Конечно, я использую его только для массивов, но код достаточно надежный для любого типа итератора.

3. @Blindy: Как вы думаете, особенно маловероятно иметь связанный список, скажем, из 10 000 элементов? Это не огромная коллекция, но разница между O (n) и O (n ^ 2) на данный момент довольно велика…

4. @Джон, эта проблема (в основном) ухудшается по сравнению с количеством удаляемых элементов, поэтому, если мы говорим о списке, в котором вы удаляете десятки тысяч элементов достаточно часто, чтобы заметить разницу, то да, это маловероятно.

5. @Blindy: требуется всего лишь удалить несколько сотен элементов из списка из 10 000 элементов, чтобы вызвать головную боль при таком подходе, IMO. Кстати, я действительно был укушен чем-то подобным в реальном мире — по иронии судьбы, немного кода, который должен был оптимизировать удаление одной коллекции из набора. Я потратил целое утро, пытаясь понять, где мой код был неправильным. Не совсем та же ситуация, но такая же разница в характеристиках производительности. Я писал об этом в блоге…

Ответ №5:

Я удаляю элементы из списка следующим образом:

 for (int j = lst.Count - 1; j >= 0; j--)
   {
    var elem= lst[j];
    lst.Remove(elem);
    }

Это выглядит очень близко к обычному «foreach var elem in lst», и именно по этой причине мне это нравится.

Я перехожу от конца к началу, потому что в противном случае вы потеряете индексацию, и вам нужно будет отслеживать количество удаленных элементов.

Ответ №6:

info это класс.

Это позволит найти linkedlist и удалить первый элемент, no значение свойства которого равно 1

 LinkedList<info> infolist = new LinkedList<info>();

string todelete = "1";

info tmpitem = new info();
foreach (var item in infolist)
{
    if (item.no == todelete)
        tmpitem = item;
}
infolist.Remove(tmpitem);

Ответ №7:

 public ListNode RemoveElements(ListNode head, int val)
    {
    if (head == null) return null;
        head.next = RemoveElements(head.next, val);
        return head.val == val ? head.next : head;
        
    }

1. Существует шесть существующих ответов на этот вопрос, включая принятый ответ Джона Скита, набравший наибольшее количество голосов и набравший тридцать голосов . Вы уверены , что ваше решение еще не предоставлено? Если нет, то почему вы считаете, что ваш подход улучшает существующие предложения, которые были одобрены сообществом? Предложение объяснения всегда полезно при переполнении стека, но это особенно важно, когда вопрос был решен к удовлетворению как OP, так и сообщества. Помогите читателям, объяснив, чем отличается ваш ответ и когда он может быть предпочтительнее.