Java Reference
In-Depth Information
. . .
}
public interface ListIterator
{
Object next();
boolean hasNext();
void add(Object element);
void remove();
void set(Object element);
. . .
}
Here we show only the fundamental operations on array lists and linked lists. Other
operations can be composed from these fundamental operations. For example, you
can add or remove an element in an array list by moving all elements beyond the
insertion or removal index, calling
get
and
set
multiple times.
Of course, the
ArrayList
class has methods to add and remove elements in the
middle, even if they are slow. Conversely, the
LinkedList
class has
get
and
set
methods that let you access any element in the linked list, albeit very inefficiently, by
performing repeated sequential accesses.
In fact, the term
ArrayList
signifies that its implementors wanted to combine the
interfaces of an array and a list. Somewhat confusingly, both the
ArrayList
and
the
LinkedList
class implement an interface called
List
that defines operations
both for random access and for sequential access.
That terminology is not in common use outside the Java library. Instead, let us adopt
a more traditional terminology. We will call the abstract types array and list. The
Java library provides concrete implementations
ArrayList
and
LinkedList
for
these abstract types. Other concrete implementations are possible in other libraries. In
fact, Java arrays are another implementation of the abstract array type.
To understand an abstract data type completely, you need to know not just its
fundamental operations but also their relative efficiency.
684
