[Page 818 (
In previous chapters, we have studied
such as one-dimensional and multidimensional arrays. This chapter introduces
dynamic data structures
that grow and shrink at execution time.
are collections of data items "linked up in a chain"insertions and deletions can be made
in a linked list.
are important in compilers and operating systems; insertions and deletions are made only at one end of a stackits
represent waiting lines; insertions are made at the back (also referred to as the
) of a queue and deletions are made from the front (also referred to as the
facilitate high-speed searching and sorting of data, eliminating duplicate data items
directories, compiling expressions into machine language and many other interesting applications.
We will discuss each of these major types of data structures and implement programs that create and manipulate them. We use classes, inheritance and composition to create and package these data structures for reusability and maintainability. In Chapter 19, Collections, we discuss Java's predefined classes that implement the data structures discussed in this chapter.
The examples presented here are practical programs that can be used in advanced courses and in industrial applications. The exercises include a rich collection of useful applications.
This chapter's examples manipulate primitive values for simplicity. However, most of the data-structure
in this chapter store only
. J2SE 5.0 has added a new feature, called boxing, that allows primitive values to be converted to and from objects for use in cases like this. The objects that represent primitive values are instances of Java's so-called
classes in package
. We discuss these classes and boxing in the
two sections, so we can use them in this chapter's examples.
you to attempt the major project described in the special section entitled
Building Your Own Compiler
. You have been using a Java compiler to translate your Java programs to bytecodes so that you could execute these programs on your computer. In this project, you will actually build your own compiler. It will read a file of statements written in a simple, yet powerful high-level language similar to early versions of the popular language BASIC. Your compiler will translate these statements into a file of Simpletron Machine Language (SML) instructionsSML is the language you learned in the Chapter 7 special section,
Building Your Own Computer
. Your Simpletron Simulator program will then execute the SML program produced by your compiler! Implementing this project by using an object-oriented approach will give you a wonderful opportunity to exercise most of what you have learned in this book. The special section
walks you through the specifications of the high-level language and describes the algorithms you will need to convert each high-level language statement into machine-language instructions. If you enjoy being challenged, you might attempt the many enhancements to both the compiler and the Simpletron Simulator suggested in the exercises.