Re: ArrayList.Iterator.remove()
On Jun 30, 4:50 pm, "Donkey Hottie" <don...@fred.pp.fi> wrote:
Just noticed a 'hidden feature of Java' ;)
Removing items an ArrayList (at least with an Iterator) takes ages.
Better - while not obvious - solution is to create an new ArrayList with =
the
remaining elements.
So it seems. removal is futile.
Not so hidden, really.
<http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html>
The size, isEmpty, get, set, iterator, and listIterator operations run
in constant time. The add operation runs in amortized constant time, that
is, adding n elements requires O(n) time. All of the other operations run
in linear time (roughly speaking).
That's for *each* removal.
That's because 'ArrayList#remove()' (through an iterator or
otherwise)
[s]hifts any subsequent elements to the left (subtracts one from their in=
dices).
<http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html#remove
(int)>
The documentation for the collection classes usually indicates the big-
O time of the common operations.
I would expect copying to take longer, however, depending on where one
is in the iteration. Perhaps there's extra machinery in the iterator
logic to normalize the iterator's position within the list.
Or are you copying individual elements as you iterate, skipping over
the "removed" ones? That should be much faster than multiple
removals.
--
Lew