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

For an ArrayList , even though the iterator is at the point that needs to be
removed, the remove is still expensive, because array items must be shifted, so
as expected, the entire routine still takes quadratic time for an ArrayList .
If we run the code in Figure 6.24, passing a LinkedList<Integer> , it takes
0.015 sec. for a 400,000 item list , and 0.031 sec. for an 800,000 item
LinkedList , and is clearly a linear-time routine, because the running time increases
by the same factor as the input size. When we pass an ArrayList<Integer> , the
routine takes about 1 minutes for a 400,000 item ArrayList , and about five
minutes for an 800,000 item ArrayList ; the four-fold increase in running time
when the input increases by only a factor of two is consistent with quadratic
behavior.
A similar situation occurs for add. The Iterator interface does not pro-
vide an add method, but ListIterator does. We have not shown that method
in Figure 6.17. Exercise 6.23 asks you to use it.

1

-

stacks and queues

6.6

In this section, we describe two containers: the stack and queue. In principle, both
have very simple interfaces (but not in the Collections API) and very efficient
implementations. Even so, as we will see, they are very useful data structures.

6.6.1 stacks

A stack is a data structure in which access is restricted to the most recently
inserted item. It behaves very much like the common stack of bills, stack of
plates, or stack of newspapers. The last item added to the stack is placed on
the top and is easily accessible, whereas items that have been in the stack for a
while are more difficult to access. Thus the stack is appropriate if we expect to
access only the top item; all other items are inaccessible.
In a stack, the three natural operations of insert , remove , and find are
renamed push , pop , and top . These basic operations are illustrated in Figure 6.25.
The interface shown in Figure 6.26 illustrates the typical protocol. It is
similar to the protocol previously seen in Figure 6.1. By pushing items and
then popping them, we can use the stack to reverse the order of things.

A stack restricts
access to the most
recently inserted
item.

Each stack operation should take a constant amount of time, independent
of the number of items in the stack. By analogy, finding today's newspaper in
a stack of newspapers is fast, no matter how deep the stack is. However, arbi-
trary access in a stack is not efficiently supported, so we do not list it as an
option in the protocol.

Stack operations
take a constant
amount of time.