Removing alternate elements in a List<T>

Question

What is the most efficient way to remove alternate (odd indexed or even indexed) elements in an List<T> without using a place holder list variable?

Also it would be appreciated if you could mention the cost with each of your answer.

I'm looking for an efficient way to do this

Thanks in advance

Answer 1

If you call RemoveAt for every item you remove, you will be moving a lot of data. The most efficient is to move the items together that you want to keep, then remove the unused items at the end:

int pos = 0;
for (int i = 0; i < values.Count; i += 2, pos++) {
    values[pos] = values[i];
}
values.RemoveRange(pos, values.Count - pos);

Edit:
This method will process a list of a million ints in 15 ms. Using RemoveAt it will take over three minutes...

Edit2:
You could actually start with pos=1 and i=2 (or 3), as the first item doesn't have to be copied to itself. This makes the code a bit less obvious though.

Answer 2

Just for consideration of a solution that creates a new list, with a list old you could do this:

var newList = old.Where((_, i) => i%2 != 0).ToList();

or, obviously

var newList = l.Where((_, i) => i%2 == 0).ToList();

depending which alternation you choose.

EDIT

The answer is quite a bit quicker. If you read something else here, it's because I measured on a weekend and weekend's brain is funny. :( The closure solution is about 40% quicker while the answer is app. 2 orders of magnitude faster. I suppose it will really depend how big your list becomes!