java - 在java中从列表或数组列表中删除中间元素的最佳方法？

Question

我需要按顺序从排序数据中删除中间元素。最好的方法是什么？由于 LinkedList 操作需要 n/2 时间来删除元素，因此数组列表会更快。但另一方面，数组列表需要时间将所有元素向左移动，这也效率不高。其他数据结构可能有用吗？

Answer 1

删除中间元素由两部分组成:

1. 查找中间元素
2. 删除该元素

ArrayList 随机访问的时间复杂度为 O(1)，因此对于 Array 来说，第一步 很快。虽然LinkedList在删除时是O(1)(给定节点)，所以第二步骤对于List来说很容易。

您想要的是两全其美。

IMO如果您编写自定义(或扩展现有)LinkedList，这很容易实现。您需要额外的 middle 引用变量，它将:

• 如果大小变为奇数，则在插入时移至下一个。
• 如果大小变为奇数，则删除后移至上一个。

您也可以在两种情况下执行偶数，但它们必须相同(偶数或奇数)。