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

6.5.3 running time for List s

In Section 6.5.2 we saw that for some operations, ArrayList is a better
choice than LinkedList , and for other operations the reverse is true. In this
section, rather than discuss the times informally, we will analyze the run-
ning times in terms of Big-Oh. Initially, we concentrate on the following
subset of operations:

add (at the end) n

n add (at the front)

remove (at the end)

n

n remove (at the front)

get and set n

n contains

ArrayList costs
For the ArrayList , adding at the end simply involves placing an item at the
next available array slot, and incrementing the current size. Occasionally we
have to resize the capacity of the array, but as this is an extremely rare opera-
tion, one can argue that it does not affect the running time. Thus the cost of
adding at the end of an ArrayList does not depend on the number of items
stored in the ArrayList and is
Similarly, removing from the end of the ArrayList simply involves decre-
menting the current size, and is get and set on the ArrayList become
array indexing operations, which are typically taken to be constant-time,
operations.
Needless to say, when we are discussing the cost of a single operation on
a collection, it is hard to envision anything better than constant time,
per operation. To do better than this would require that as the collection gets
larger, operations actually get faster, which would be very unusual.
However, not all operations are on an ArrayList . As we have seen, if
we add at the front of the ArrayList , then every element in the ArrayList must
be shifted one index higher. Thus if there are N elements in the ArrayList ,
adding at the front is an operation. Similarly, removing from the front
of the ArrayList requires shifting all the elements one index lower, which is also
an operation. And a contains on an ArrayList is an operation,
because we potentially have to sequentially examine every item in the ArrayList .
Needless to say,

O 1 () .

O 1 () .

O ( )

O 1 (),

O ( )

O ( N )

O ( N ) O ( N )

O ( N ) per operation is not as good as O ( )

O ( N )

per opera-

tion. In fact, when one considers that the contains operation is and is

basically an exhaustive search, one can argue that O ( N ) per operation for a

basic collection operation is about as bad as it gets.