java - 哪个更适合实现中位数算法的中位数 - ArrayList 或 Linkedlist？

Question

我正在尝试在 Java 中实现中位数算法的中位数。我想知道这两个列表实现中的哪一个在列表遍历和比较方面成本更低？谢谢！

Answer 1

AnArrayList应该稍微更有效，因为该算法需要对数据结构进行一些随机访问，该数据结构需要 O(1)ArrayList和 O(n) LinkedList。

LinkedList对于删除操作（O(1) forLinkedList和 O(n) for ArrayList）更有效，但在您的算法中不应该是这种情况。