Java Reference
In-Depth Information
list ADT. Interface
List
defines the member functions that any list implementa-
tion inheriting from it must support, along with their parameters and return types.
We increase the flexibility of the list ADT by writing it as a Java generic.
True to the notion of an ADT, an interface does not specify how operations
are implemented. Two complete implementations are presented later in this sec-
tion, both of which use the same list ADT to define their operations, but they are
considerably different in approaches and in their space/time tradeoffs.
Figure 4.1 presents our list ADT. Class
List
is a generic of one parameter,
named
E
for “element”.
E
serves as a placeholder for whatever element type the
user would like to store in a list. The comments given in Figure 4.1 describe pre-
cisely what each member function is intended to do. However, some explanation
of the basic design is in order. Given that we wish to support the concept of a se-
quence, with access to any position in the list, the need for many of the member
functions such as
insert
and
moveToPos
is clear. The key design decision em-
bodied in this ADT is support for the concept of a current position. For example,
member
moveToStart
sets the current position to be the first element on the list,
while methods
next
and
prev
move the current position to the next and previ-
ous elements, respectively. The intention is that any implementation for this ADT
support the concept of a current position. The current position is where any action
such as insertion or deletion will take place.
Since insertions take place at the current position, and since we want to be able
to insert to the front or the back of the list as well as anywhere in between, there are
actually n + 1 possible “current positions” when there are n elements in the list.
It is helpful to modify our list display notation to show the position of the
current element. I will use a vertical bar, such as h20; 23 j 12; 15i to indicate
the list of four elements, with the current position being to the right of the bar at
element 12. Given this configuration, calling
insert
with value 10 will change
the list to be h20; 23 j 10; 12; 15i.
If you examine Figure 4.1, you should find that the list member functions pro-
vided allow you to build a list with elements in any desired order, and to access
any desired position in the list. You might notice that the
clear
method is not
necessary, in that it could be implemented by means of the other member functions
in the same asymptotic time. It is included merely for convenience.
Method
getValue
returns a reference to the current element. It is considered
a violation of
getValue
's preconditions to ask for the value of a non-existent ele-
ment (i.e., there must be something to the right of the vertical bar). In our concrete
list implementations, assertions are used to enforce such preconditions. In a com-
mercial implementation, such violations would be best implemented by the Java
exception mechanism.
A list can be iterated through as shown in the following code fragment.
