Re: java.util.LinkedList.iterator().remove() time complexity
On Nov 24, 12:06 pm, Mayeul <mayeul.marg...@free.fr> wrote:
On 24/11/2010 10:29, Sebastian wrote:
I would expect that in a linked list, an element can be added or
removed in constant time, assuming that the iterator is already
in the right position.
Exaclty that's the way they (Sun) implemented it.
However, the Javadoc for JDK 1.6 says the following:
a) the iterator method of a LinkedList (defined in
AbstractSequentialList) merely returns a list iterator
over the list.
b) the remove() and set(Object) methods in ListIterator are not defined
in terms of the cursor position; they are defined to operate on the
last element returned by a call to next() or previous().
I am not sure how to understand that.
I'd say, exactly as it is said, without spontaneously inventing
convoluted implications of it for no reason.
:-)
Instead of removing the next item obtained from next(), it removes the
latest item obtained from either next() or previous(). That's it.
BTW, it means you can get the next item with next(), check whether you
want to remove this object, and do remove it if you want to. Likewise
with previous(). Nice.
Does it mean that removal from a
linked list, even through the remove method of an iterator over the
list, is implemented in terms of either the remove(int index)or
the remove(Object o) method?
No, why?
I'd think of easier ways to remember the location of the latest item I
served.
Am I missing something? Is the documentation simply wrong?
The documentation is right, and I do feel you are missing something.
Adding to that: with any decent IDE Sebastian can dive directly into
the source code of LinkedList (or more specifically
java.util.LinkedList.ListItr<E>) and see for himself.
Cheers
robert