Java Reference
In-Depth Information
Chapter
13
List Implementations
That Use Arrays
Contents
Using an Array to Implement the ADT List
An Analogy
The Java Implementation
The Efficiency of Using an Array to Implement the ADT List
Using a Vector to Implement the ADT List
Prerequisites
Appendix D
Designing Classes
Chapter
2
Bag Implementations That Use Arrays
Chapter
4
The Efficiency of Algorithms
Chapter
12
Lists
Objectives
After studying this chapter, you should be able to
•
Implement the ADT list by using either an array that you can resize or an instance of
Vector
•
Discuss the advantages and disadvantages of the two implementations presented
Y
ou have seen several examples of how to use the ADT list in a program. This
chapter presents three different ways that you can implement a list in Java. We begin
by using an array to represent the entries in a list. As in earlier implementations of
other ADTs, when you use all of the space in an array, you can move the data to a
larger array. Alternately, you can use an instance of the Java class
Vector
to represent
the list entries. The result is like using an array that can expand, since the underlying
implementation of
Vector
uses such an array. But this list implementation is simpler
to write than our first one, because
Vector
does the work for you. Our final imple-
mentation uses a chain of linked nodes. Because you can insert and remove entries at
any position within a list, the array-based and linked implementations are a bit more
challenging than the previous ADT implementations we have encountered so far.
