Site MapHelpFeedbackList ADT
List ADT

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, respectively.

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 linked list.

Describe and implement the iterator pattern.

Explain the key differences between the array and linked implementations of the List ADT.

WuOnline Learning Center

Home > Chapter 18