Geek Answers Handbook

List-optimized implementation for deletion (int index)

I want to use List<E>, but the only way I'm ever going to use is

E remove(int index)

I am interested in the return value of this method (deleted E). I never need a method remove(E e).

The only constructor I will ever need is to take it Collection<? extends E>.

If it Listis ArrayList, the method remove(int index)has a time complexity of O (n), because you have to shuffle the elements after the deleted element in one place on the left.

If it Listis LinkedList, the method remove(int index)also has O (n) time complexity, because although it takes O (1) time to change the links in an element, you have to find the element in index index, intersecting List.

If I’m only interested in a method remove(int index), is it possible to write an implementation List<E>that he optimized for this method, so that the method remove(int index)has time complexity better than O (n)?

+4
source share
3 answers

I would suggest using TreeList from apache collection collections.

It is optimized so that

, , O (log n).

+3

TreeList. Java , Apache Commons TreeList. , .

+1

If you don't care about reordering, you can do the deletion in O (1) using an array by replacing the element with the deletion using the last element.

As an example,

@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);
}

(However, note that this behaves differently than indicated by the interface List.)

0
source

More articles:


All Articles