更适合于实现中位数算法ArrayList或Linkedlist

Question

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

Answer 1

ArrayList的效率应该稍高，因为该算法需要对数据结构进行一些随机访问，其中ArrayList采用O（1），LinkedList采用O（n）。

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