The collections api - Data Structures and Problem Solving Using Java - page 257

1 public static void removeEvensVer1( List<Integer> lst )
2 {
3

figure 6.22
Removes the even
numbers in a list;
quadratic on all
types of lists

int i = 0;

while( i < lst.size( ) ) 4

if( lst.get( i ) % 2 == 0 ) 5

lst.remove( i ); 6

else 7

i++; 8

9 }

1 public static void removeEvensVer2( List<Integer> lst )
2 {
3

figure 6.23
Removes the even
numbers in a list;
doesn't work
because of
ConcurrentModifica-
tionException

for( Integer x : lst )

if( x % 2 == 0 )

4

lst.remove( x ); 5

6 }

Figure 6.23 shows one attempt to rectify the problem. Instead of using
get , we use an iterator to step through the list. This is efficient. But then we
use the Collection 's remove method to remove an even-valued item. This is not
an efficient operation because the remove method has to search for the item
again, which takes linear time. But if we run the code, we find out that the sit-
uation is even worse: the program generates a ConcurrentModificationException
because when an item is removed, the underlying iterator used by the enhanced
for loop is invalidated. (The code in Figure 6.22 explains why: we cannot expect
the enhanced for loop to understand that it must advance only if an item is not
removed.)
Figure 6.24 shows an idea that works: after the iterator finds an even-
valued item, we can use the iterator to remove the value it has just seen. For a
LinkedList , the call to the iterator's remove method is only constant time,
because the iterator is at (or near) the node that needs to be removed. Thus, for
a LinkedList , the entire routine takes linear time, rather than quadratic time.

1 public static void removeEvensVer3( List<Integer> lst )
2 {
3

figure 6.24
Removes the even
numbers in a list;
quadratic on
ArrayList , but linear
time for LinkedList

Iterator<Integer> itr = lst.iterator( );

4
5

while( itr.hasNext( ) )

if( itr.next( ) % 2 == 0 ) 6

itr.remove( );

7

8 }