Java Structures

“IT’S A WONDERFUL TIME TO BE ALIVE.” At least that’s what I’ve found myself

saying over the past couple of decades. When I first started working with com-

puters, they were resources used by a privileged (or in my case, persistent) few.

They were physically large, and logically small. They were cast from iron. The

challenge was to make these behemoths solve complex problems quickly.

Today, computers are everywhere. They are in the office and at home. They

speak to us on telephones; they zap our food in the microwave. They make

starting cars in New England a possibility. Everyone’s using them. What has

aided their introduction into society is their diminished size and cost, and in-

creased capability. The challenge is to make these behemoths solve complex

problems quickly.

Thus, while the computer and its applications have changed over time, the

challenge remains the same: How can we get the best performance out of the

current technology? The design and analysis of data structures lay the funda-

mental groundwork for a scientific understanding of what computers can do

efficiently. The motivations for data structure design work accomplished three

decades ago in assembly language at the keypunch are just as familiar to us to-

day as we practice our craft in modern languages on computers on our laps. The

focus of this material is the identification and development of relatively abstract

principles for structuring data in ways that make programs efficient in terms of

their consumption of resources, as well as efficient in terms of “programmability.”

In the past, my students have encountered this material in Pascal, Modula-2,

and, most recently, C++. None of these languages has been ideal, but each has

been met with increasing expectation. This text uses The Java Programming

Language1—“Java”—to structure data. Java is a new and exciting language

that has received considerable public attention. At the time of this writing, for

example, Java is one of the few tools that can effectively use the Internet as a

computing resource. That particular aspect of Java is not touched on greatly

in this text. Still, Internet-driven applications in Java will need supporting data

structures. This book attempts to provide a fresh and focused approach to the

design and implementation of classic structures in a manner that meshes well

with existing Java packages. It is hoped that learning this material in Java

will improve the way working programmers craft programs, and the way future

designers craft languages.