我有一个游戏循环，它绘制了一个对象列表，该列表称为"mylist"，包含大约1000个对象，对象(特别是快速飞行并击中物体的子弹)需要不断地从列表中添加和删除，每秒几个对象。
如果我理解正确的话，如果列表容量足够大，那么插入列表实际上是免费的，问题在于删除是O(n)，因为首先我需要在列表中找到项目，其次它在删除后创建一个新列表。
如果我可以聚合所有的移除并使它们每帧一次，这将是有效的，因为我将使用mylist.Except(listToRemove)，这将是在O(n)。但遗憾的是，我做不到。
链表也有问题，因为我需要在列表中找到对象。
谁有更好的建议?HashSet呢?支持O(1)的插拔。如果您需要排序，请使用树数据结构或LinkedList + Dictionary，这可以让您快速找到节点。
BCL有SortedList、SortedSet和SortedDictionary。除了一个之外，其他的都很慢，但我永远记不住哪一个是"好"的。
如果您正在进行搜索，那么您最好的选择是使用平均情况为O(1)和最坏情况为O(n)的Dictionary(当您散列到同一桶时)。
如果你需要保持顺序，你可以使用任何平衡二叉搜索树的实现，你的性能将是O(logn)。
在。net中，这简单地归结为
字典-插入/删除O(1)(平均情况)
SortedDictionary -保留有序操作的顺序，插入/删除O(logn)
所以理想情况下，您希望使用具有O(1)或O(log n)删除和插入的数据结构。字典类型的数据结构可能是理想的，因为它们具有恒定的平均插入和删除时间复杂度。我建议使用HashSet，然后在你的游戏对象基类上重写GetHashCode()。
这里是所有不同的字典/哈希表数据结构的更多细节。
时间复杂度。下面是所有类似字典的数据结构和它们的时间复杂度:
Type Find by key Remove Add
HashSet O(1)* O(1)* O(1)**
Dictionary O(1)* O(1)* O(1)**
SortedList O(log n) O(n) O(n)
SortedDictionary O(log n) O(log n) O(log n)
* O(n)与碰撞
** 0 (n) .
HashSet vs Dictionary
HashSet和Dictionary之间的区别在于，Dictionary在KeyValuePair上工作，而在HashSet上，关键字是对象本身(它的GetHashCode()方法)。
SortedList vs SortedDictionary
只有当你需要维持订单时，你才应该考虑这些。不同之处在于SortedDictionary使用红黑树，而SortedList使用排序数组作为键和值。
- 我的博客文章-。net简单的集合和字典
- MSDN - HashSet
- MSDN - Dictionary
- MSDN - SortedDictionary
- MSDN - SortedList
性能方面，如果不从任何类型的列表中插入或删除任何内容，您可能会看到最好的结果。分配一个足够大的数组，并标记你所有的对象是否应该渲染。
考虑到你的需求，然而，这都可能是过早的优化;您可以每秒30次重新创建包含1000个元素的整个列表，而不会看到任何性能下降。
我建议阅读一下Braid的创造者所做的关于在独立电子游戏中使用正确数据结构的幻灯片:http://the-witness.net/news/2011/06/how-to-program-independent-games/(tl;dr只是使用数组)。