Section 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 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 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
ArrayList class from Chapter 9 is another example of a data structure. Like an array, individual ArrayList elements are accessed by their position. However, unlike arrays, an ArrayList is an example of a dynamic structure —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 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 Java construct, called generic types. Finally, the binary tree data structure that is used in the Java Collections Framework will be studied briefly.You have attempted of activities on this page.
