Code Tapas

savory little bits of programming

January 10, 2013

Standard practice is to iterate over the list backwards like so:

for( int i = items.Count - 1; i >= 0; --i ) { if( shouldRemove( items[i] ) ) item.RemoveAt( i ); }

This approach doesn’t use any extra memory which is nice, but it’s

`O((n/2)`

run time (assuming ^{2})`RemoveAt()`

is `O(n)`

) is less so.

A clever approach I found from Abe Pralle that is `O(n)`

is to fill the gaps as you remove and iterate and then finally truncate the list at the end. Another way to think about it is bubbling the items that need removal to the end of the list.

int gap = 0; for( int i = 0; i < items.Count; ++i ) { if( !shouldRemove( items[i] ) ) { items[gap] = items[i]; ++gap; } } items.RemoveRange( gap, items.Count - gap );

Pretty cool!