java - ArrayList.remove() 导致滞后

Question

我有一个困扰我一段时间的问题。我有一个软件，可以在其中生成一定数量的物理世界中的对象，并将它们存储在 ArrayList 中。但是，当从 ArrayList 中删除对象时，此实现会产生滞后。

静态数组实现不会导致滞后，但不太实用，因为我不能使用“添加”和“删除”。

我假设 ArrayLists 的滞后是由于内存释放和重新分配造成的。由于我的 ArrayList 具有固定的最大大小，是否可以预先分配一定的内存以避免这些问题？或者有其他解决方案吗？

非常感谢您的帮助！

Answer 1

这里的问题是 anArrayList是内部实现的，正如名称所述，使用数组。这意味着如果不移动您正在使用的索引之后的元素，就不能自由地插入或删除集合的元素。

因此，如果您的集合有很多元素，例如，您删除了第 5 个，那么从第 6 个到列表末尾的所有元素都必须向左移动一个位置。这确实可能很昂贵，并导致O(n)复杂度。

为避免这些问题，您应该根据您将在其上使用的最常见操作选择合适的集合。LinkedList如果您需要迭代、删除（实际上删除需要找到元素，所以只要您已经在枚举它们就很好了）或插入元素，但每当您想要访问特定索引时，您都会遇到麻烦，A可能会很好。

您也可以寻找 aHashSet或 a TreeSet，它们可能适合您的解决方案。

在这些情况下，了解最常见的数据结构如何工作以及哪些是好/坏对于做出适当的选择总是有用的。

Answer 2

我通常不会只是转发别人的答案，但这似乎很合适。