WIXLIB

Preface to the First Edition“I T ’ S A WONDERFUL TIME TO BE ALIVE .” At least that’s what I’ve found myselfsaying over the past couple of decades. When I first started working with computers, 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. Thechallenge was to make these behemoths solve complex problems quickly.Today, computers are everywhere. They are in the office and at home. Theyspeak to us on telephones; they zap our food in the microwave. They makestarting cars in New England a possibility. Everyone’s using them. What hasaided their introduction into society is their diminished size and cost, and increased capability. The challenge is to make these behemoths solve complexproblems quickly.Thus, while the computer and its applications have changed over time, thechallenge remains the same: How can we get the best performance out of thecurrent technology? The design and analysis of data structures lay the fundamental groundwork for a scientific understanding of what computers can doefficiently. The motivations for data structure design work accomplished threedecades ago in assembly language at the keypunch are just as familiar to us today as we practice our craft in modern languages on computers on our laps. Thefocus of this material is the identification and development of relatively abstractprinciples for structuring data in ways that make programs efficient in terms oftheir 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 hasbeen met with increasing expectation. This text uses The Java ProgrammingLanguage1 —“Java”—to structure data. Java is a new and exciting languagethat has received considerable public attention. At the time of this writing, forexample, Java is one of the few tools that can effectively use the Internet as acomputing resource. That particular aspect of Java is not touched on greatlyin this text. Still, Internet-driven applications in Java will need supporting datastructures. This book attempts to provide a fresh and focused approach to thedesign and implementation of classic structures in a manner that meshes wellwith existing Java packages. It is hoped that learning this material in Javawill improve the way working programmers craft programs, and the way futuredesigners craft languages.Pedagogical Implications. This text was developed specifically for use withCS2 in a standard Computer Science curriculum. It is succinct in its approach,and requires, perhaps, a little more effort to read. I hope, though, that this text1Java is a trademark of Sun Microsystems, Incorporated.

xiiPreface to the First EditionSESWEWNENWNSListnimbecomes not a brief encounter with object-oriented data structure design, but atouchstone for one’s programming future.The material presented in this text follows the syllabus I have used for several years at Williams. As students come to this course with experience usingJava, the outline of the text may be followed directly. Where students are newto Java, a couple of weeks early in the semester will be necessary with a goodcompanion text to introduce the student to new concepts, and an introductoryJava language text or reference manual is recommended. For students that needa quick introduction to Java we provide a tutorial in Appendix B. While the textwas designed as a whole, some may wish to eliminate less important topicsand expand upon others. Students may wish to drop (or consider!) the section on induction (Section 5.2.2). The more nontraditional topics—including,for example, iteration and the notions of symmetry and friction—have been included because I believe they arm programmers with important mechanisms forimplementing and analyzing problems. In many departments the subtleties ofmore advanced structures—maps (Chapter 15) and graphs (Chapter 16)—maybe considered in an algorithms course. Chapter 6, a discussion of sorting, provides very important motivating examples and also begins an early investigationof algorithms. The chapter may be dropped when better examples are at hand,but students may find the refinements on implementing sorting interesting.Associated with this text is a Java package of data structures that is freelyavailable over the Internet for noncommercial purposes. I encourage students,educators, and budding software engineers to download it, tear it down, build itup, and generally enjoy it. In particular, students of this material are encouragedto follow along with the code online as they read. Also included is extensivedocumentation gleaned from the code by javadoc. All documentation—withinthe book and on the Web—includes pre- and postconditions. The motivation forthis style of commenting is provided in Chapter 2. While it’s hard to be militantabout commenting, this style of documentation provides an obvious, structuredapproach to minimally documenting one’s methods that students can appreciateand users will welcome. These resources, as well as many others, are availablefrom McGraw-Hill at http://www.mhhe.com/javastructures.Three icons appear throughout the text, as they do in the margin. Thetop “compass” icon highlights the statement of a principle—a statement thatencourages abstract discussion. The middle icon marks the first appearance ofa particular class from the structure package. Students will find these files atMcGraw-Hill, or locally, if they’ve been downloaded. The bottom icon similarlymarks the appearance of example code.Finally, I’d like to note an unfortunate movement away from studying theimplementation of data structures, in favor of studying applications. In theextreme this is a disappointing and, perhaps, dangerous precedent. The designof a data structure is like the solution to a riddle: the process of developing theanswer is as important as the answer itself. The text may, however, be used as areference for using the structure package in other applications by selectivelyavoiding the discussions of implementation.

Preface to the Second EditionSince the first edition of Java Structures support for writing programs in Java2has grown considerably. At that time the Java Development Toolkit consistedof 504 classes in 23 packages3 In Java 1.2 (also called Java 2) Sun rolled out1520 classes in 59 packages. This book is ready for Java 1.4, where the numberof classes and packages continues to grow.Most computer scientists are convinced of the utility of Java for programming in a well structured and platform independent manner. While there arestill significant arguments about important aspects of the language (for example, support for generic types), the academic community is embracing Java, forexample, as the subject of the Computer Science Advanced Placement Examination.It might seem somewhat perplexing to think that many aspects of the original Java environment have been retracted (or deprecated) or reconsidered. Thedevelopers at Sun have one purpose in mind: to make Java the indispensablelanguage of the current generation. As a result, documenting their progress onthe development of data structures gives us valuable insight into the process ofdesigning useful data structures for general purpose programming. Those students and faculty considering a move to this second edition of Java Structureswill see first-hand some of the decisions that have been made in the intervening years. During that time, for example, the Collection-based classes wereintroduced, and are generally considered an improvement. Another force—one similar to calcification—has left a trail of backwards compatible featuresthat are sometimes difficult to understand. For example, the Iterator classwas introduced, but the Enumeration class was not deprecated. One subject ofthe first edition—the notion of Comparable classes—has been introduced intoa number of important classes including String and Integer. This is a stepforward and a reconsideration of what we have learned about that material haslead to important improvements in the text.Since the main purpose of the text is to demonstrate the design and behaviorof traditional data structures, we have not generally tracked the progress ofJava where it blurs the view. For example, Java 2 introduces a List interface(we applaud) but the Vector class has been extended to include methods thatare, essentially, motivated by linked lists (we wonder). As this text points outfrequently, the purpose of an interface is often to provide reduced functionality.If the data structure does not naturally provide the functionality required by theapplication, it is probably not an effective tool for solving the problem: searchelsewhere for an effective structure.23The Java Programming Language is a trademark of Sun Microsystems, Incorporated.David Flanagan, et al., Java in a Nutshell, O’Reilly & Associates.

xivPreface to the Second EditionAs of this writing, more than 100, 000 individuals have searched for anddownloaded the structure package. To facilitate using the comprehensive setof classes with the Java 2 environment, we have provided a number of featuresthat support the use of the structure package in more concrete applications.Please see Appendix C.Also new to this edition are more than 200 new problems, several dozenexercises, and over a dozen labs we regularly use at Williams.Acknowledgments. Several students, instructors, and classes have helped toshape this edition of Java Structures. Parth Doshi and Alex Glenday—diligentWilliams students—pointed out a large number of typos and stretches of logic.Kim Bruce, Andrea Danyluk, Jay Sachs, and Jim Teresco have taught this courseat Williams over the past few years, and have provided useful feedback. I tipmy hat to Bill Lenhart, a good friend and advisor, who has helped improve thistext in subtle ways. To Sean Sandys I am indebted for showing me new ways toteach new minds.The various reviewers have made, collectively, hundreds of pages of comments that have been incorporated (as much as possible) into this edition:Eleanor Hare and David Jacobs (Clemson University), Ram Athavale (NorthCarolina State University), Yannick Daoudi (McGill University), Walter Daugherty (Texas A&M University), Subodh Kumar (Johns Hopkins University), ToshimiMinoura (Oregon State University), Carolyn Schauble (Colorado State University), Val Tannen (University of Pennsylvania), Frank Tompa (University of Waterloo), Richard Wiener (University of Colorado at Colorado Springs), CynthiaBrown Zickos (University of Mississippi), and my good friend Robbie Moll (University of Massachusetts). Deborah Trytten (University of Oklahoma) has reviewed both editions! Still, until expert authoring systems are engineered, authors will remain human. Any mistakes left behind or introduced are purelythose of the author.The editors and staff at McGraw-Hill–Kelly Lowery, Melinda Dougharty, JohnWannemacher, and Joyce Berendes–have attempted the impossible: to keep mewithin a deadline. David Hash, Phil Meek, and Jodi Banowetz are responsiblefor the look and feel of things. I am especially indebted to Lucy Mullins, JudyGantenbein, and Patti Evers whose red pens have often shown me a better way.Betsy Jones, publisher and advocate, has seen it all and yet kept the faith:thanks.Be aware, though: long after these pages are found to be useless folly, mybest work will be recognized in my children, Kate, Megan, and Ryan. Noneof these projects, of course, would be possible without the support of my bestfriend, my north star, and my partner, Mary.Enjoy!Duane A. BaileyWilliamstown, May 2002

Preface to the 7 EditionIn your hand is a special edition of Java Structures designed for use with twosemesters of Williams’ course on data structures, Computer Science 136. Thisversion is only marginally different than the preceding edition, but is positionedto make use of Java 5 (the trademarked name for version 1.5 of the JDK).Because Java 5 may not be available (yet) on the platform you use, most of thecode available in this book will run on older JDK’s. The one feature that wouldnot be available is Java’s new Scanner class from the java.util package; analternative is my ReadStream class, which is lightly documented in Section B.3.1on page 494. It is a feature of the structure package soon to be removed.In making this book available in this paperbound format, my hope is thatyou find it a more inviting place to write notes: additions, subtractions, andupdates that you’re likely to have discussed in class. Sometimes you’ll identifyimprovements, and I hope you’ll pass those along to me. In any case, you candownload the software (as hundreds of thousands have done in the past) andmodify it as you desire.On occasion, I will release new sections you can incorporate into your text,including a discussion of how the structure package can make use of generictypes.I have spent a considerable amount of time designing the structure package. The first structures were available 8 years ago when Java was still in itsinfancy. Many of the structures have since been incorporated (directly or indirectly) into Sun’s own JDK. (Yes, we’ve sold a few books in California.) Still, Ifeel the merit of my approach is a slimness that, in the end, you will not findsurprising.Meanwhile, for those of you keeping track, the following table (adaptedfrom the 121 cubic inch, 3 pound 6 ounce, Fifth edition of David Flanagan’sessential Java in a Nutshell) demonstrates the growth of Java’s support:JDK1.01.11.2 (Java 2)1.31.41.5 (Java 62FeaturesFirst public versionInner classesCollection classesA “maintenance” release.Improvments, including assertGenerics, autoboxing, and “varargs.”Seeing this reminds me of the comment made by Niklaus Wirth, designer ofPascal and the first two releases of Modula. After the design team briefed himon the slew of new features to be incorporated into Modula 3, he parried: “But,what features have you removed?” A timeless question.

xviPreface to the 7 EditionAcknowledgments. This book was primarily written for students of WilliamsCollege. The process of publishing and reviewing a text tends to move the focusoff campus and toward the bottom line. The Route 7 edition4 —somewherebetween editions 2 and 3—is an initial attempt to bring that focus back to thosestudents who made it all possible.For nearly a decade, students at many institutions have played an importantrole in shaping these resources. In this edition, I’m especially indebted to KatieCreel ’10 (Williams) and Brian Bargh ’07 (Messiah): thanks!Many colleagues, including Steve Freund ’95 (Stanford, now at Williams),Jim Teresco ’92 (Union, now at Mount Holyoke), and especially Gene Chase ’65(M.I.T., now at Messiah) continue to nudge this text in a better direction. BrentHeeringa ’99 (Morris, now at Williams) showers all around him with youthfulenthusiasm.And a most special thanks to Bill Mueller for the shot heard around theworld—the game-winning run that showed all things were possible. Called byJoe Castiglione ’68 (Colgate, now at Fenway):“Three-and-one to Mueller. One out, nineth inning. 10-9 Yankees,runner at first. Here’s the pitch.swing and a High Drive Deep toRight.Back Goes Sheffield to the Bullpen.AND IT IS GONE!.ANDTHE RED SOX HAVE WON IT!.ON A WALKOFF TWO RUN HOMERBY BILL MUELLER OFF MARIANO RIVERA! CAN YOU BELIEVE IT?!”Have I been a Red Sox fan all my life? Not yet.Finally, nothing would be possible without my running mate, my Sox buddy,and my best friend, Mary.Cheers!Duane A. Bailey ’82 (Amherst, now at Williams)Williamstown, September 20074Route 7 is a scenic byway through the Berkshires and Green Mountains that eddies a bit as itpasses through Williamstown and Middlebury.

Chapter 0IntroductionConcepts:. Approaches to this material. PrinciplesThis is an important notice.Please have it translated.—The Phone CompanyY OUR MOTHER probably provided you with constructive toys, like blocks orTinkertoys1 or Lego bricks. These toys are educational: they teach us to thinkspatially and to build increasingly complex structures. You develop modulesthat can be stuck together and rules that guide the building process.If you are reading this book, you probably enjoyed playing with constructive toys. You consider writing programs an artistic process. You have grownfrom playing with blocks to writing programs. The same guidelines for buildingstructures apply to writing programs, save one thing: there is, seemingly, nolimit to the complexity of the programs you can write.Well, almost. When writ

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