- Understand the concepts of a dynamic data structure and an Abstract Data Type (ADT).
- Be able to create and use dynamic data structures such as linked lists and binary search trees.
- Understand the stack, queue, set, and map ADTs.
- Be able to use inheritance to define extensible data structures.
- Know how to use the TreeSet, TreeMap, HashSet, and HashMap library classes.
- Be able to use the Java generic type construct.
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.)
tatic.) 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 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 new Java construct, called generic types. Finally, the binary tree data structure that is used in the Java Collections Framework will be studied briefly.