Java, Java, Java

A data structure is used to organize information that a computer can ac- cess and process easily and efficiently. You are already familiar with one type of data structure—arrays, which we discussed in Chapter 9. If you remember, an array is an example of a data structure in which all of the data are of the same type or class and in which individual elements are ac- cessed by their position (index or subscript). An array is an example of a static structure, because its size is fixed for the duration of the program’s execution. (This is a different meaning of static than the Java keyword static.)

The Vector class from Chapter 9 is another example of a data struc-

ture. Like an array, individual vector elements are accessed by their posi- tion. However, unlike arrays, a vector is an example of a dynamic struc- ture—that is, one that can grow and shrink during a program’s execution. These are only two of the many data structures developed by computer scientists. For more advanced problems, it is often necessary to develop specialized structures to store and manipulate information. Some of these structures—linked lists, stacks, queues, binary trees, hash tables—have

become classic objects of study in computer science.

This chapter describes how to implement a linked list and how to use inheritance to extend the list to implement the stack and queue struc- tures. Then the Java Collections Framework implementation of numerous data structures in the java.util package will be described. The data structure classes in this library make use of a new Java construct, called generic types. Finally, the binary tree data structure that is used in the Java Collections Framework will be studied briefly.

Static vs. dynamic

Referring to objects