How to remove from List<T> efficiently (C#)?

Question

If I understood correctly (and please correct me if i'm wrong), list is implemented by array in .NET, which means that every deletion of an item in the list will cause re-allocation of all the list (which in turn means O(n)).

I'm developing a game, in the game i have many bullets fly in the air on any giving moment, let's say 100 bullets, each frame I move them by few pixels and check for collision with objects in the game, I need to remove from the list every bullet that collided.

So I collect the collided bullet in another temporary list and then do the following:

foreach (Bullet bullet in bulletsForDeletion)
    mBullets.Remove(bullet);

Because the loop is O(n) and the remove is O(n), I spend O(n^2) time to remove.

Is there a better way to remove it, or more suitable collection to use?

Answer 1

Create a new list:

var newList = `oldList.Except(deleteItems).ToList()`.

Try to use functional idioms wherever possible. Don't modify existing data structures, create new ones.

This algorithm is O(N) thanks to hashing.