java.util.LinkedList.iterator().remove() time complexity

[Sebastian]

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.

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. 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? Which in a LinkedList would need to
traverse the list, making removal a linear time operation.

Am I missing something? Is the documentation simply wrong?

-- Sebastian

 

[Mayeul]

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.

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.

 

[Screamin' Lord Byron]

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.

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.

As I understand it, it means that cursor position is not an element
position. Cursor is "in between elements", and remove() and set() are
performed on the element that the iterator just "consumed", being via
call to next() or previous().

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? Which in a LinkedList would need to
traverse the list, making removal a linear time operation.

I think it's the other way around. When you call remove() on a List,
it's done via ListIterator.

Anyway, that's my understanding, which could be wrong.

 

[Robert Klemme]

Exaclty that's the way they (Sun) implemented it.

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.


No, why?
I'd think of easier ways to remember the location of the latest item I
served.


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

 

[Joshua Cranmer]

I am not sure how to understand that. 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? Which in a LinkedList would need to
traverse the list, making removal a linear time operation.

What it means is that it does the right thing when you try to use it
like this:

List<Integer> list =
new LinkedList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
// Remove all even elements
if (it.next() % 2 == 0)
it.remove();
}

The iterator for LinkedLists happens to be implemented in terms of
having a pointer to a node in the linked list, specifically the last one
retrieved [1]. Removing that node is then an O(1) operation.

The wording may be a bit complicated, but it's basically describing the
sanest implementation: the iterator is a pointer to the element.
Operations like remove() removes the element being pointed to; next()
moves to the next element(); etc.

[1] I'm not sure about this part, but it's the easiest way to fulfill
the contracts of ListIterator.

 

[Sebastian]

Am 24.11.2010 15:09, schrieb Joshua Cranmer:

I am not sure how to understand that. 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? Which in a LinkedList would need to
traverse the list, making removal a linear time operation.

[snip}

The iterator for LinkedLists happens to be implemented in terms of
having a pointer to a node in the linked list, specifically the last one
retrieved [1]. Removing that node is then an O(1) operation.

The wording may be a bit complicated, but it's basically describing the
sanest implementation: the iterator is a pointer to the element.
Operations like remove() removes the element being pointed to; next()
moves to the next element(); etc.

[snip]

Thanks. I was confused by the ListIterator doc saying explicitly that it
was not using the iterator's current position for deletion, which made
me think it didn't have a pointer to the element. Silly of me.
-- Sebastian

 

[Lew]

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.

It doesn't even require an IDE. "unzip ... cat" or equivalents
suffice.

 

[Roedy Green]

Am I missing something? Is the documentation simply wrong?

If you use an IDE, it will let you drill into Sun's code for the
iteration, and you can see for yourself what it does. See
http://mindprod.com/jgloss/ide.html