Chapter 17. Data Structures

17.1. Introduction

In previous chapters, we have studied fixed- size data structures such as one-dimensional and multidimensional arrays. This chapter introduces dynamic data structures that grow and shrink at execution time. Linked lists are collections of data items "linked up in a chain"insertions and deletions can be made anywhere in a linked list. Stacks are important in compilers and operating systems; insertions and deletions are made only at one end of a stackits top . Queues represent waiting lines; insertions are made at the back (also referred to as the tail ) of a queue and deletions are made from the front (also referred to as the head ). Binary trees facilitate high-speed searching and sorting of data, eliminating duplicate data items efficiently , representing file-system 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 implementations in this chapter store only Objects . 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 type-wrapper classes in package java.lang . We discuss these classes and boxing in the next two sections, so we can use them in this chapter's examples.

We encourage 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 carefully 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.