Section 16.1. Introduction

[Page 768]

16.1. Introduction

A data structure is used to organize information that a computer can access and process easily and efficiently. You are already familiar with one type of data structurearrays, 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 accessed 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 structure. Like an array, individual vector elements are accessed by their position. However, unlike arrays, a vector is an example of a dynamic structurethat 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 structureslinked lists, stacks, queues, binary trees, hash tableshave 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 structures. 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 used in the Java Collections Framework will be studied briefly.