java.util.LinkedList.iterator().remove() time complexity
Sebastian
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.
--
Mayeul
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
> 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
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.
>
> Am I missing something? Is the documentation simply wrong?
>
> -- Sebastian
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
Sebastian
> On 11/24/2010 04:29 AM, Sebastian wrote:
>> 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.
>
> 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.
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.
--
Lew
Roedy Green
<seba...@undisclosed.invalid> wrote, quoted or indirectly quoted
someone who said :
>
>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
--
Roedy Green Canadian Mind Products
http://mindprod.com
If you give your kitchen floor a quick steam mop every few days, you will find you never have to get out buckets and brushes for deep cleaning. Similary, if you keep your code tidy, refactoring as you go, you probably won't need major rewrites.