Re: java.util.LinkedList.iterator().remove() time complexity
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.
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