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

6.5.4 removing from and adding
to the middle of a List

The List interface contains two operations:

void add( int idx, AnyType x );
void remove( int idx );

that allow the adding of an item to a specified index and removing of an item
from a specified index. For an ArrayList , these operations are in general

O ( N ) ,

because of the item shifting that is required.
For a LinkedList , in principle one would expect that if we know where the
change is being made, then we should be able to do it efficiently by splicing
links in the linked list. For instance, it is easy to see that in principle, remov-
ing a single node from a doubly linked list requires changing some links in the
preceding and succeeding nodes. However, these operations are still

O ( N ) in

a LinkedList because it takes time to find the node.
This is precisely why the Iterator provides a remove method. The idea is that
often an item is being removed only after we have examined it and decided to
discard it. This is similar to the idea of picking up items from the floor: as you
search the floor, if you see an item, you immediately pick it up because you are
already there.
As an example, we provide a routine that removes all even-valued items
in a list. Thus if the list contains 6, 5, 1, 4, 2, then after the method is invoked
it will contain 5, 1.
There are several possible ideas for an algorithm that deletes items from
the list as they are encountered. Of course, one idea is to construct a new list
containing all the odd numbers, and then clear the original list and copy the
odd numbers back into it. But we are more interested in writing a clean ver-
sion that avoids making a copy, and instead removes items from the list as
they are encountered.
This is almost certainly a losing strategy for an ArrayList , since removing
from almost anywhere in an ArrayList is expensive. (It is possible to design a
different algorithm for ArrayList that works in place, but let us not worry
about that now.) In a LinkedList , there is some hope, since as we know,
removing from a known position can be done efficiently by rearranging some
links.
Figure 6.22 shows the first attempt. On an ArrayList , as expected, the
remove is not efficient, so the routine takes quadratic time. A LinkedList
exposes two problems. First, the call to get is not efficient, so the routine takes
quadratic time. Additionally, the call to remove is equally inefficient, because
as we have seen, it is expensive to get to position i .

O ( N )