We introduced the concept of linked lists in Chapter 16 and provided the fundamentals
of manipulating links. And, in Chapter 17, we introduced the generics
feature of Java 5.0 and used it in defining the SimpleLinkedList class that provides a
higher-level abtraction to the client programmers. Using a SimpleLinkedList, the
client programmers do not have to deal directly with the linked nodes. Instead, they
deal strictly with list objects. The fact that the linked nodes are used in implementation
is hidden from the client programmers. This embodies the software engineering
principle of information hiding. In this chapter, we will expand this concept further
by introducing an abstract data type (ADT). ADTs are reusable software components
that support reliable and flexible software construction.
An abstract data type (ADT) is a mathematical specification of a set of data
and the corresponding set of operations performed on those data. The key point
is that an ADT does not specify how the set of data is actually represented in
memory or how the set of operations is implemented. Nice examples of ADTs
can be found in the Java Collections Framework. When we look in the java.util
package, for example, we see the Java interface List and two classes that implement
the List interface. The List interface represents the List ADT, and the two
classes—ArrayList and LinkedList—implement the List ADT. The ArrayList
uses an array, and the LinkedList uses linked nodes to implement the List ADT,
To study how the ADT is defined and implemented, we will create our own
List ADT and provide two implementations in this chapter which we model after the
java.util.List interface and its two implementations. Ours is a much simplified version
of those in the java.util package. In Chapters 19 and 20, we will study the Stack
and Queue ADTs, respectively.
O b j e c t i v e s
After you have read and studied this chapter, you should be able to
Describe the key features of the List ADT.
Implement the List ADT using an array and
Describe and implement the iterator pattern.
Explain the key differences between the array
and linked implementations of the List ADT.