1

I want to remove an element from list based on a condition. The problem is I can't remove it while iterating it forward since its array like implementation and this changes listing structure and count.

So i read this answered and i was convinced that this should be the solution:how-to-remove-elements-from-a-generic-list-while-iterating-over-it

But someone gave me feedback that this is not easily understandable since we are iterating it backwards, rather we should iterate forward and do i-- whenever removal condition is met.

var list = new List<int>(Enumerable.Range(1, 10));
for (int i = 0; i < list.Count; i++)
{
    if (list[i] > 5)
    {
        list.RemoveAt(i);
        i--;
    }
}
list.ForEach(i => Console.WriteLine(i));

I unit tested this approach and results are as expected but i am still apprehensive that it would be same for all the possible cases since i got this answer nowhere in any forum and everyone had suggested to iterate backwards.

Can anyone please tell if both solutions would behave same or are they different?

Community
  • 1
  • 1
Sahil Sharma
  • 3,847
  • 6
  • 48
  • 98

2 Answers2

4

The preferred way to remove items from a list, in-place, is to do it in reverse with this kind of code:

int index = list.Count - 1;
while (index >= 0)
{
    if (expression identifying item to remove)
        list.RemoveAt(index);
    index--;
}

Now, bear in mind that this only applies to removal in a list in-place, meaning that you don't want to build a new list of the items to keep. If you can do that, build a new list with the items to keep, a LINQ expression is probably better.

So, why is the above approach preferred?

Well, consider this. What does "removing an item from a list" mean anyway? The underlying data structure of a List<T> in C# is an array. Removing an item from an array cannot really be done but what you can do is to move the values inside an array. To "remove" an item from an array you could move all the items that follow it one index up.

This is an operation that will take time relative to the number of items following it.

So let's look at doing this in the "forward approach". In this approach you would start at index 0 and move up every time you find an item to keep, but you would also remove an item by moving every item that follows it one element down.

Let's make a simple example, you have a list of every number from 1 through 10, and you want to remove every even element value (2, 4, 6, 8, etc.).

So you have this:

1 2 3 4 5 6 7 8 9 10

The first item to remove is 2, this will have to move every number that follows it, 3 through 10, one index down. That is 8 numbers moved.

The next item is 4, it will have to move 5 through 10 down, which is 6 numbers. Now we have moved 14 numbers in total.

Next is 6, move 7 through 10 down, that is 4 numbers, now we're up to 18 numbers moved.

Next is 8, move 9 and 10, 2 numbers, we're up to 20 numbers moved.

Since no numbers follow the last one we want to remove, 10, we have moved 20 numbers in total.

Now let's do it in reverse.

First we look at 10, we want to remove this, no numbers follow it, so no moving.

Next we want to remove is 8, there's only one number following it, so we move 9 down one notch. 10 was already removed so it is no longer present.

Next we want to remove is 6. There's two numbers following it, 7 and 9, so move those down, 3 numbers moved in total.

Remove 4, following it is 5, 7 and 9, so now we have moved 6 numbers in total.

Remove 2 - 3, 5, 7 and 9 is following it so now we have moved 10 numbers in total.

So when dealing with a list, it depends entirely on what you mean "behaves the same way".

Will the end result be the same, when we only consider which numbers are left in the final list?

Yes.

Will the total runtime be the same?

No.

Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
  • Sorry to comment an old post and answer, but shouldn't we do "index--" everytime? I think staying at the same index when removing the item at the end of the list (the first we check) would result in an IndexOutOfRangeException. Thus, we could do a for instead of a while. – Rifu Jul 24 '20 at 08:10
  • @Rifu Re-reading the code, and what you are saying seems to be right, let me test it to verify. Can't believe such a bug has been in this answer for so long. – Lasse V. Karlsen Jul 24 '20 at 09:05
  • @Rifu There will not be an exception because at every index, at most one item will be removed. The code works by accident, since the first time it comes to a new index that matches, it will remove the item, and not decrease the index, then the loop will iterate once more, this time it won't match (since items "to the right" would have been removed earlier), so then it decreases the index. I'll remove the else keyword and make it better. Thanks for noticing! – Lasse V. Karlsen Jul 24 '20 at 09:08
  • No problem, happy to help! – Rifu Jul 24 '20 at 12:14
0

I would suggest don't just use the index to remove the items from the list within the iteration. Simple use the Linq Select with where condition. This will result out you a new list actually.

var list = new List<int>(Enumerable.Range(1, 10));
var newList= list.Select(number=>number<=5).ToList();

And now the newList will only contain the items which met the condition you provide in lambda expression.

error_handler
  • 1,191
  • 11
  • 19
  • but it didn't remove the selected elements from the original list. I need to remove them and use the list with subtracted elements somewhere else. – Sahil Sharma Apr 16 '16 at 20:00
  • okay, If I understand your problem correctly, you are going to use the list after removing some items based on some condition. So as my above code does. It wont delete anything from the original list. it will just create a new list for you after filtering the items from the original results using your condition. you can use the new list somewhere else. – error_handler Apr 16 '16 at 20:21