我想使用 List<E>但我将要使用的唯一方法是
E remove(int index)
我对这个方法的返回值感兴趣(删除了E)。我从不需要方法 remove(E e) .
我唯一需要的构造函数是采用 Collection<? extends E> 的构造函数.
如果List是一个 ArrayList , remove(int index)方法的时间复杂度为 O(n)，因为您必须将移除元素之后的元素向左移动一位。
如果List是 LinkedList , remove(int index)方法的时间复杂度也为 O(n)，因为尽管更改元素处的链接需要 O(1) 时间，但您必须在索引 index 处找到该元素。通过遍历 List .
如果我只对使用 remove(int index) 感兴趣方法，是否可以编写 List<E> 的实现？它针对此方法进行了优化，因此 remove(int index)方法的时间复杂度优于 O(n)？
最佳答案
我建议使用 TreeList来自 apache 的 commons-collections。
它是这样优化的
This list implementation utilises a tree structure internally to ensure that all insertions and removals are O(log n).
关于java - 针对 remove(int index) 优化的 List 实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28842102/