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

Sets and linked lists both have constant time removal. Can you use either of those data structures?

There's no way to avoid the O(N) cost of removal from List<T>. You'll need to use a different data structure if this is a problem for you. It may make the code which calculates bulletsToRemove feel nicer too.

ISet<T> has nice methods for calculating differences and intersections between sets of objects.

You lose ordering by using sets, but given you are taking bullets, I'm guessing that is not an issue. You can still enumerate it in constant time.

---

In your case, you might write:

mBullets.ExceptWith(bulletsForDeletion);

Answer 2

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.