针对 remove(int index) 优化的 List 实现

Question

我想使用 List<E>，但我将要使用的唯一方法是

E remove(int index)

我对这个方法的 return 值感兴趣（删除了 E）。我从不需要方法 remove(E e).

我唯一需要的构造函数是 Collection<? extends E>.

如果List是一个ArrayList，remove(int index)方法的时间复杂度为O(n)，因为你必须将移除元素之后的元素向左移动一位。

如果List是LinkedList，remove(int index)方法的时间复杂度也为O(n)，因为虽然改变一个元素的链接需要O(1)的时间，您必须通过遍历 List.

找到索引 index 处的元素

如果我只对使用 remove(int index) 方法感兴趣，是否可以编写针对此方法优化的 List<E> 的实现，以便 remove(int index) 方法时间复杂度比 O(n) 好吗？

Answer 1

我建议使用来自 apache 的 commons-collections 的 TreeList。

经过优化，

This list implementation utilises a tree structure internally to ensure that all insertions and removals are O(log n).

Answer 2

您可以使用 TreeList。虽然 Java 没有它的实现，但您可以使用 Apache Commons TreeList。您可以检查它是否打算在中间插入和删除时表现出色。

Answer 3

如果您不关心顺序的变化，您可以通过将要删除的元素与最后一个元素交换来使用数组在 O(1) 中进行删除。

例如，

@Override
public E remove(int index) {
    int size = size();
    if(index < 0 || size <= index) {
        throw new IndexOutOfBoundsException(String.valueOf(index));
    }

    E last = super.remove(size - 1);
    return set(index, last);
}

（但是，请注意，这与 List 接口指定的行为不同。）

针对 remove(int index) 优化的 List 实现

A List implementation that is optimised for remove(int index)

java

list

time-complexity