Java Structures
Java Structures
√
The 7 Edition
(Software release 33)
Duane A. Bailey
Williams College
September 2007
√
This 7 text copyrighted 2005-2007 by
0 Introduction 1
0.1 Read Me . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 He Can’t Say That, Can He? . . . . . . . . . . . . . . . . . . . . . 2
3 Vectors 43
3.1 The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Example: The Word List Revisited . . . . . . . . . . . . . . . . . . 47
3.3 Example: Word Frequency . . . . . . . . . . . . . . . . . . . . . . 48
3.4 The Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Extensibility: A Feature . . . . . . . . . . . . . . . . . . . . . . . . 53
3.6 Example: L-Systems . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.7 Example: Vector-Based Sets . . . . . . . . . . . . . . . . . . . . . 57
3.8 Example: The Matrix Class . . . . . . . . . . . . . . . . . . . . . . 60
3.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
iv Contents
4 Generics 69
4.1 Motivation (in case we need some) . . . . . . . . . . . . . . . . . 70
4.1.1 Possible Solution: Specialization . . . . . . . . . . . . . . 71
4.2 Implementing Generic Container Classes . . . . . . . . . . . . . . 72
4.2.1 Generic Associations . . . . . . . . . . . . . . . . . . . . 72
4.2.2 Parameterizing the Vector Class . . . . . . . . . . . . . . 74
4.2.3 Restricting Parameters . . . . . . . . . . . . . . . . . . . . 79
4.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5 Design Fundamentals 81
5.1 Asymptotic Analysis Tools . . . . . . . . . . . . . . . . . . . . . . 81
5.1.1 Time and Space Complexity . . . . . . . . . . . . . . . . . 82
5.1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.1.3 The Trading of Time and Space . . . . . . . . . . . . . . . 91
5.1.4 Back-of-the-Envelope Estimations . . . . . . . . . . . . . . 92
5.2 Self-Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2.1 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2.2 Mathematical Induction . . . . . . . . . . . . . . . . . . . 101
5.3 Properties of Design . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.3.1 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.3.2 Friction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.5 Laboratory: How Fast Is Java? . . . . . . . . . . . . . . . . . . . . 115
6 Sorting 119
6.1 Approaching the Problem . . . . . . . . . . . . . . . . . . . . . . 119
6.2 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.3 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.4 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.6 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.7 Sorting Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.8 Ordering Objects Using Comparators . . . . . . . . . . . . . . . . 140
6.9 Vector-Based Sorting . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.11 Laboratory: Sorting with Comparators . . . . . . . . . . . . . . . 147
8 Iterators 161
8.1 Java’s Enumeration Interface . . . . . . . . . . . . . . . . . . . . 161
8.2 The Iterator Interface . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.3 Example: Vector Iterators . . . . . . . . . . . . . . . . . . . . . . 165
8.4 Example: Rethinking Generators . . . . . . . . . . . . . . . . . . 167
8.5 Example: Filtering Iterators . . . . . . . . . . . . . . . . . . . . . 170
8.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
8.7 Laboratory: The Two-Towers Problem . . . . . . . . . . . . . . . 175
9 Lists 179
9.1 Example: A Unique Program . . . . . . . . . . . . . . . . . . . . . 182
9.2 Example: Free Lists . . . . . . . . . . . . . . . . . . . . . . . . . . 183
9.3 Partial Implementation: Abstract Lists . . . . . . . . . . . . . . . 186
9.4 Implementation: Singly Linked Lists . . . . . . . . . . . . . . . . 188
9.5 Implementation: Doubly Linked Lists . . . . . . . . . . . . . . . . 201
9.6 Implementation: Circularly Linked Lists . . . . . . . . . . . . . . 206
9.7 Implementation: Vectors . . . . . . . . . . . . . . . . . . . . . . . 209
9.8 List Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
9.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
9.10 Laboratory: Lists with Dummy Nodes . . . . . . . . . . . . . . . . 215
15 Maps 369
15.1 Example Revisited: The Symbol Table . . . . . . . . . . . . . . . . 369
15.2 The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
15.3 Simple Implementation: MapList . . . . . . . . . . . . . . . . . . 372
15.4 Constant Time Maps: Hash Tables . . . . . . . . . . . . . . . . . . 374
15.4.1 Open Addressing . . . . . . . . . . . . . . . . . . . . . . . 375
15.4.2 External Chaining . . . . . . . . . . . . . . . . . . . . . . 383
15.4.3 Generation of Hash Codes . . . . . . . . . . . . . . . . . . 385
15.4.4 Hash Codes for Collection Classes . . . . . . . . . . . . . . 391
15.4.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . 392
15.5 Ordered Maps and Tables . . . . . . . . . . . . . . . . . . . . . . 392
15.6 Example: Document Indexing . . . . . . . . . . . . . . . . . . . . 395
15.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
15.8 Laboratory: The Soundex Name Lookup System . . . . . . . . . . 401
16 Graphs 403
16.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
16.2 The Graph Interface . . . . . . . . . . . . . . . . . . . . . . . . . 404
16.3 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
16.3.1 Abstract Classes Reemphasized . . . . . . . . . . . . . . . 408
16.3.2 Adjacency Matrices . . . . . . . . . . . . . . . . . . . . . . 410
16.3.3 Adjacency Lists . . . . . . . . . . . . . . . . . . . . . . . . 416
16.4 Examples: Common Graph Algorithms . . . . . . . . . . . . . . . 422
16.4.1 Reachability . . . . . . . . . . . . . . . . . . . . . . . . . . 422
16.4.2 Topological Sorting . . . . . . . . . . . . . . . . . . . . . . 424
16.4.3 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . 427
16.4.4 All Pairs Minimum Distance . . . . . . . . . . . . . . . . . 428
16.4.5 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . 429
16.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
16.6 Laboratory: Converting Between Units . . . . . . . . . . . . . . . 439
A Answers 441
A.1 Solutions to Self Check Problems . . . . . . . . . . . . . . . . . . 441
A.2 Solutions to Odd-Numbered Problems . . . . . . . . . . . . . . . 451
C Collections 511
C.1 Collection Class Features . . . . . . . . . . . . . . . . . . . . . . . 511
C.2 Parallel Features . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
C.3 Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
D Documentation 513
D.1 Structure Package Hierarchy . . . . . . . . . . . . . . . . . . . . . 513
D.2 Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
Index 517
for Mary,
my wife and best friend
without
the model of my mentors,
the comments of my colleagues,
the support of my students,
the friendship of my family
this book would never be
thank you!
Preface to the First Edition
“I T ’ 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.
Pedagogical Implications. This text was developed specifically for use with
CS2 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 text
becomes not a brief encounter with object-oriented data structure design, but a
touchstone for one’s programming future.
The material presented in this text follows the syllabus I have used for sev-
eral years at Williams. As students come to this course with experience using
Java, the outline of the text may be followed directly. Where students are new
to Java, a couple of weeks early in the semester will be necessary with a good
N
companion text to introduce the student to new concepts, and an introductory
NW
NE
Java language text or reference manual is recommended. For students that need
W
SE
was designed as a whole, some may wish to eliminate less important topics
and expand upon others. Students may wish to drop (or consider!) the sec-
tion on induction (Section 5.2.2). The more nontraditional topics—including,
for example, iteration and the notions of symmetry and friction—have been in-
cluded because I believe they arm programmers with important mechanisms for
implementing and analyzing problems. In many departments the subtleties of
more advanced structures—maps (Chapter 15) and graphs (Chapter 16)—may
be considered in an algorithms course. Chapter 6, a discussion of sorting, pro-
vides very important motivating examples and also begins an early investigation
of 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 freely
available over the Internet for noncommercial purposes. I encourage students,
educators, and budding software engineers to download it, tear it down, build it
List up, and generally enjoy it. In particular, students of this material are encouraged
to follow along with the code online as they read. Also included is extensive
documentation gleaned from the code by javadoc. All documentation—within
the book and on the Web—includes pre- and postconditions. The motivation for
this style of commenting is provided in Chapter 2. While it’s hard to be militant
about commenting, this style of documentation provides an obvious, structured
approach to minimally documenting one’s methods that students can appreciate
and users will welcome. These resources, as well as many others, are available
from McGraw-Hill at http://www.mhhe.com/javastructures.
Three icons appear throughout the text, as they do in the margin. The
top “compass” icon highlights the statement of a principle—a statement that
nim encourages abstract discussion. The middle icon marks the first appearance of
a particular class from the structure package. Students will find these files at
McGraw-Hill, or locally, if they’ve been downloaded. The bottom icon similarly
marks the appearance of example code.
Finally, I’d like to note an unfortunate movement away from studying the
implementation of data structures, in favor of studying applications. In the
extreme this is a disappointing and, perhaps, dangerous precedent. The design
of a data structure is like the solution to a riddle: the process of developing the
answer is as important as the answer itself. The text may, however, be used as a
reference for using the structure package in other applications by selectively
avoiding the discussions of implementation.
Preface to the Second Edition
Since the first edition of Java Structures support for writing programs in Java2
has grown considerably. At that time the Java Development Toolkit consisted
of 504 classes in 23 packages3 In Java 1.2 (also called Java 2) Sun rolled out
1520 classes in 59 packages. This book is ready for Java 1.4, where the number
of classes and packages continues to grow.
Most computer scientists are convinced of the utility of Java for program-
ming in a well structured and platform independent manner. While there are
still significant arguments about important aspects of the language (for exam-
ple, support for generic types), the academic community is embracing Java, for
example, as the subject of the Computer Science Advanced Placement Exami-
nation.
It might seem somewhat perplexing to think that many aspects of the origi-
nal Java environment have been retracted (or deprecated) or reconsidered. The
developers at Sun have one purpose in mind: to make Java the indispensable
language of the current generation. As a result, documenting their progress on
the development of data structures gives us valuable insight into the process of
designing useful data structures for general purpose programming. Those stu-
dents and faculty considering a move to this second edition of Java Structures
will see first-hand some of the decisions that have been made in the interven-
ing years. During that time, for example, the Collection-based classes were
introduced, and are generally considered an improvement. Another force—
one similar to calcification—has left a trail of backwards compatible features
that are sometimes difficult to understand. For example, the Iterator class
was introduced, but the Enumeration class was not deprecated. One subject of
the first edition—the notion of Comparable classes—has been introduced into
a number of important classes including String and Integer. This is a step
forward and a reconsideration of what we have learned about that material has
lead to important improvements in the text.
Since the main purpose of the text is to demonstrate the design and behavior
of traditional data structures, we have not generally tracked the progress of
Java 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 that
are, essentially, motivated by linked lists (we wonder). As this text points out
frequently, the purpose of an interface is often to provide reduced functionality.
If the data structure does not naturally provide the functionality required by the
application, it is probably not an effective tool for solving the problem: search
elsewhere for an effective structure.
As of this writing, more than 100, 000 individuals have searched for and
downloaded the structure package. To facilitate using the comprehensive set
of classes with the Java 2 environment, we have provided a number of features
that 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 dozen
exercises, and over a dozen labs we regularly use at Williams.
Acknowledgments. Several students, instructors, and classes have helped to
shape this edition of Java Structures. Parth Doshi and Alex Glenday—diligent
Williams students—pointed out a large number of typos and stretches of logic.
Kim Bruce, Andrea Danyluk, Jay Sachs, and Jim Teresco have taught this course
at Williams over the past few years, and have provided useful feedback. I tip
my hat to Bill Lenhart, a good friend and advisor, who has helped improve this
text in subtle ways. To Sean Sandys I am indebted for showing me new ways to
teach new minds.
The various reviewers have made, collectively, hundreds of pages of com-
ments that have been incorporated (as much as possible) into this edition:
Eleanor Hare and David Jacobs (Clemson University), Ram Athavale (North
Carolina State University), Yannick Daoudi (McGill University), Walter Daugh-
erty (Texas A&M University), Subodh Kumar (Johns Hopkins University), Toshimi
Minoura (Oregon State University), Carolyn Schauble (Colorado State Univer-
sity), Val Tannen (University of Pennsylvania), Frank Tompa (University of Wa-
terloo), Richard Wiener (University of Colorado at Colorado Springs), Cynthia
Brown Zickos (University of Mississippi), and my good friend Robbie Moll (Uni-
versity of Massachusetts). Deborah Trytten (University of Oklahoma) has re-
viewed both editions! Still, until expert authoring systems are engineered, au-
thors will remain human. Any mistakes left behind or introduced are purely
those of the author.
The editors and staff at McGraw-Hill–Kelly Lowery, Melinda Dougharty, John
Wannemacher, and Joyce Berendes–have attempted the impossible: to keep me
within a deadline. David Hash, Phil Meek, and Jodi Banowetz are responsible
for the look and feel of things. I am especially indebted to Lucy Mullins, Judy
Gantenbein, 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, my
best work will be recognized in my children, Kate, Megan, and Ryan. None
of these projects, of course, would be possible without the support of my best
friend, my north star, and my partner, Mary.
Enjoy!
Duane A. Bailey
Williamstown, May 2002
√
Preface to the 7 Edition
In your hand is a special edition of Java Structures designed for use with two
semesters of Williams’ course on data structures, Computer Science 136. This
version is only marginally different than the preceding edition, but is positioned
to 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 the
code available in this book will run on older JDK’s. The one feature that would
not be available is Java’s new Scanner class from the java.util package; an
alternative is my ReadStream class, which is lightly documented in Section B.3.1
on 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 that
you find it a more inviting place to write notes: additions, subtractions, and
updates that you’re likely to have discussed in class. Sometimes you’ll identify
improvements, and I hope you’ll pass those along to me. In any case, you can
download the software (as hundreds of thousands have done in the past) and
modify 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 generic
types.
I have spent a considerable amount of time designing the structure pack-
age. The first structures were available 8 years ago when Java was still in its
infancy. Many of the structures have since been incorporated (directly or indi-
rectly) into Sun’s own JDK. (Yes, we’ve sold a few books in California.) Still, I
feel the merit of my approach is a slimness that, in the end, you will not find
surprising.
Meanwhile, for those of you keeping track, the following table (adapted
from the 121 cubic inch, 3 pound 6 ounce, Fifth edition of David Flanagan’s
essential Java in a Nutshell) demonstrates the growth of Java’s support:
Cheers!
4 Route 7 is a scenic byway through the Berkshires and Green Mountains that eddies a bit as it
passes through Williamstown and Middlebury.
Chapter 0
Introduction
Y OUR MOTHER probably provided you with constructive toys, like blocks or
Tinkertoys1 or Lego bricks. These toys are educational: they teach us to think
spatially and to build increasingly complex structures. You develop modules
that can be stuck together and rules that guide the building process.
If you are reading this book, you probably enjoyed playing with construc-
tive toys. You consider writing programs an artistic process. You have grown
from playing with blocks to writing programs. The same guidelines for building
structures apply to writing programs, save one thing: there is, seemingly, no
limit to the complexity of the programs you can write. I lie.
Well, almost. When writing large programs, the data structures that main-
tain the data in your program govern the space and time consumed by your
running program. In addition, large programs take time to write. Using differ-
ent structures can actually have an impact on how long it takes to write your
program. Choosing the wrong structures can cause your program to run poorly
or be difficult or impossible to implement effectively.
Thus, part of the program-writing process is choosing between different
structures. Ideally you arrive at solutions by analyzing and comparing their
various merits. This book focuses on the creation and analysis of traditional
data structures in a modern programming environment, The Java Programming
Language, or Java for short.
0.1 Read Me
As might be expected, each chapter is dedicated to a specific topic. Many of the
topics are concerned with specific data structures. The structures we will inves-
tigate are abstracted from working implementations in Java that are available
to you if you have access to the Internet.2 Other topics concern the “tools of the
trade.” Some are mathematical and others are philosophical, but all consider
the process of programming well.
The topics we cover are not all-inclusive. Some useful structures have been
left out. Instead, we will opt to learn the principles of programming data struc-
tures, so that, down the road, you can design newer and better structures your-
self.
Perhaps the most important aspect of this book is the set of problems at the
end of each section. All are important for you to consider. For some problems
I have attempted to place a reasonable hint or answer in the back of the book.
Why should you do problems? Practice makes perfect. I could show you how to
Unicycles: the ride a unicycle, but if you never practiced, you would never learn. If you study
ultimate riding and understand these problems, you will find your design and analytical skills
structure. are improved. As for your mother, she’ll be proud of you.
Sometimes we will introduce problems in the middle of the running text—
these problems do not have answers (sometimes they are repeated as formal
problems in the back of the chapter, where they do have answers)—they should
be thought about carefully as you are reading along. You may find it useful to
have a pencil and paper handy to help you “think” about these problems on the
fly.
Exercise 0.1 Call3 your Mom and tell her you’re completing your first exercise. If
you don’t have a phone handy, drop her a postcard. Ask her to verify that she’s
proud of you.
This text is brief and to the point. Most of us are interested in experimenting.
We will save as much time as possible for solving problems, perusing code, and
practicing writing programs. As you read through each of the chapters, you
might find it useful to read through the source code online. As we first consider
the text of files online, the file name will appear in the margin, as you see here.
Structure The top icon refers to files in the structure package, while the bottom icon
refers to files supporting examples.
One more point—this book, like most projects, is an ongoing effort, and
the latest thoughts are unlikely to have made it to the printed page. If you
are in doubt, turn to the website for the latest comments. You will also find
online documentation for each of the structures, generated from the code using
Example javadoc. It is best to read the online version of the documentation for the
most up-to-date details, as well as the documentation of several structures not
formally presented within this text.
3 Don’t e-mail her. Call her. Computers aren’t everything, and they’re a poor medium for a mother’s
pride.
0.2 He Can’t Say That, Can He? 3
NW
NE
W
Principle 1 The principled programmer understands a principle well enough to
E
SW
SE
form an opinion about it. S
Problems
Solutions to the odd-numbered problems begin on page 451.
0.1 All odd problems have answers. Where do you find answers to prob-
lems? (Hint: See page 451.)
0.2 You are an experienced programmer. What five serious pieces of advice
would you give a new programmer?
0.3 Surf to the website associated with this text and review the resources
available to you.
0.4 Which of the following structures are described in this text (see Append-
ix D): BinarySearchTree, BinaryTree, BitSet, Map, Hashtable, List?
0.5 Surf to http://www.javasoft.com and review the Java resources avail-
able from Sun, the developers of Java.
0.6 Review documentation for Sun’s java.util package. (See the Core
API Documentation at http://www.javasoft.com.) Which of the following
data structures are available in this package: BinarySearchTree, BinaryTree,
BitSet, Dictionary, Hashtable, List?
0.7 Check your local library or bookstore for Java reference texts.
0.8 If you haven’t done so already, learn how to use your local Java pro-
gramming environment by writing a Java application to write a line of text.
(Hint: Read Appendix B.)
0.9 Find the local documentation for the structure package. If none is to
be found, remember that the same documentation is available over the Internet
from http://www.cs.williams.edu/JavaStructures.
0.10 Find the examples electronically distributed with the structure pack-
age. Many of these examples are discussed later in this text.
Chapter 1
C OMPUTER SCIENCE DOES NOT SUFFER the great history of many other disci-
plines. While other subjects have well-founded paradigms and methods, com-
puter science still struggles with one important question: What is the best method
to write programs? To date, we have no best answer. The focus of language de-
signers is to develop programming languages that are simple to use but provide
the power to accurately and efficiently describe the details of large programs
and applications. The development of Java is one such effort.
Throughout this text we focus on developing data structures using object-
oriented programming. Using this paradigm the programmer spends time devel- OOP:
oping templates for structures called classes. The templates are then used to Object-oriented
construct instances or objects. A majority of the statements in object-oriented programming.
programs involve sending messages to objects to have them report or change
their state. Running a program involves, then, the construction and coordina-
tion of objects. In this way languages like Java are object-oriented.
In all but the smallest programming projects, abstraction is a useful tool
for writing working programs. In programming languages including Pascal,
Scheme, and C, the details of a program’s implementation are hidden away in
its procedures or functions. This approach involves procedural abstraction. In
object-oriented programming the details of the implementation of data struc-
tures are hidden away within its objects. This approach involves data abstrac-
tion. Many modern programming languages use object orientation to support
basic abstractions of data. We review the details of data abstraction and the
design of formal interfaces for objects in this chapter.
6 The Object-Oriented Method
1 Apple cider is often used to flavor donuts in New England, but that decision decidedly changes
the flavor of the donut for the better. Some of the best apple cider donuts can be found at Atkin’s
apple farm in Amherst, Massachusetts.
1.2 The Object Model 7
Counted string
Data L I C K E T Y S P L I T !
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 n
Count 13
Terminated string
E
Data L I C K E T Y S P L I T ! O
S
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 n
Figure 1.1 Two methods of implementing a string. A counted string explicitly records
its length. The terminated string’s length is determined by an end-of-string mark.
2 This is not quite the truth. For a discussion of the facts, see Appendix B.8.
1.3 Object-Oriented Terminology 9
Exercise 1.1 Nearly everything can be improved. Are there improvements that
might be made to the gcd method? Can you write the method iteratively? Is
iteration an improvement?
As with the Ratio class, data fields are usually declared protected. To ma-
nipulate protected fields the user must invoke public methods. The following
example demonstrates the manipulation of the Ratio class:
The substance of these methods has purposefully been removed because, again,
it is unimportant for us to know exactly how a BankAccount is implemented.
We have ways to construct and compare BankAccounts, as well as ways to read
the account number or balance, or update the balance.
Let’s look at the implementation of these methods, individually. To build a
new bank account, you must use the new operator to call the constructor with
two parameters. The account number provided never changes over the life of
the BankAccount—if it were necessary to change the value of the account num-
ber, a new BankAccount would have to be made, and the balance would have to
be transferred from one to the other. The constructor plays the important role
of performing the one-time initialization of the account number field. Here is
the code for a BankAccount constructor:
Notice that the BankAccount equals method calls the equals method of the key,
a String. Both BankAccount and String are nonprimitive types, or examples
of Objects. Every object in Java has an equals method. If you don’t explicitly
provide one, the system will write one for you. Generally speaking, one should
assume that the automatically written or default equals method is of little use.
This notion of “equality” of objects is often based on the complexities of our
abstraction; its design must be considered carefully.
One can ask the BankAccount about various aspects of its state by calling its
getAccount or getBalance methods:
public String getAccount()
// post: returns the bank account number of this account
{
return account;
}
These methods do little more than pass along the information found in the
account and balance fields, respectively. We call such methods accessors. In a
different implementation of the BankAccount, the balance would not have to be
explicitly stored—the value might be, for example, the difference between two
fields, deposits and drafts. Given the interface, it is not much of a concern to
the user which implementation is used.
We provide two more methods, deposit and withdraw, that explicitly mod-
ify the current balance. These are mutator methods:
translation. For each string passed as the argument to the main method, the
dictionary is searched to determine the appropriate translation.
When this application is run with the arguments hop on pop, the results are
ophay
onay
oppay
While this application may seem rather trivial, it is easy to imagine a large-scale
application with similar needs.3
We now consider the design of the Association. Notice that while the type
of data maintained is different, the purpose of the Association is very similar
to that of the BankAccount class we discussed in Section 1.4. An Association
is a key-value pair such that the key cannot be modified. Here is the interface
for the Association class:
import java.util.Map;
3 Pig Latin has played an important role in undermining court-ordered restrictions placed on music Association
piracy. When Napster—the rebel music trading firm—put in checks to recognize copyrighted music
by title, traders used Pig Latin translators to foil the recognition software!
16 The Object-Oriented Method
For the moment, we will ignore the references to Map and Map.entry; these will
be explained later, in Chapter 15. What distinguishes an Association from a
more specialized class, like BankAccount, is that the fields of an Association
are type Object. The use of the word Object in the definition of an Association
makes the definition very general: any value that is of type Object—any non-
primitive data type in Java—can be used for the key and value fields.
Unlike the BankAccount class, this class has two different constructors:
protected Object theKey; // the key of the key-value pair
protected Object theValue; // the value of the key-value pair
When necessary, the method setValue can be used to change the value associ-
ated with the key. Thus, the setValue method simply takes its parameter and
assigns it to the value field:
There are other methods that are made available to users of the Association
class, but we will not discuss the details of that code until later. Some of the
methods are required, some are useful, and some are just nice to have around.
While the code may look complicated, we take the time to implement it cor- N
NW
NE
E
SW
SE
S
Principle 2 Free the future: reuse code.
18 The Object-Oriented Method
2. Identify, given your operations, those data that support the state of your
object. Information about an object’s state is carried within the object
between operations that modify the state. Since there may be many ways
to encode the state of your object, your description of the state may be
very general.
3. Identify any rules of consistency. In the Ratio class, for example, it would
not be good to have a zero denominator. Also, the numerator and denom-
inator should be in lowest terms.
5. Identify the types and kinds of information that, though declared pro-
tected, can efficiently provide the information needed by the public
methods. Important choices about the internals of a data structure are
usually made at this time. Sometimes, competing approaches are devel-
oped until a comparative evaluation can be made. That is the subject of
much of this book.
Let’s consider these lines. One of the first lines (labeled declaration) de-
clares a reference to a WordList. For a reference to refer to an object, the object
must be constructed. We require, therefore, a constructor for a WordList. The
construction line allocates an initially empty list of words ultimately contain-
ing as many as 10 words. We provide an upper limit on the number of words
that are potentially stored in the list. (We’ll see later that providing such infor-
mation can be useful in designing efficient data structures.) On the next three
lines, three (dubious) words are added to the list.
The while loop accomplishes the task of playing Hangman with the user.
This is possible as long as the list of words is not empty. We use the isEmpty
method to test this fact. At the beginning of each round of Hangman, a random
word is selected (selectAny), setting the targetWord reference. To make things
interesting, we presume that the selectAny method selects a random word each
time. Once the round is finished, we use the remove method to remove the word
from the word list, eliminating it as a choice in future rounds.
There are insights here. First, we have said very little about the Hangman
game other than its interaction with our rather abstract list of words. The details
of the screen’s appearance, for example, do not play much of a role in under-
standing how the WordList structure works. We knew that a list was necessary
for our program, and we considered the program from the point of view of the
object. Second, we don’t really know how the WordList is implemented. The
words may be stored in an array, or in a file on disk, or they may use some tech-
nology that we don’t currently understand. It is only important that we have
faith that the structure can be implemented. We have sketched out the method
headers, or signatures, of the WordList interface, and we have faith that an im-
plementation supporting the interface can be built. Finally we note that what
we have written is not a complete program. Still, from the viewpoint of the
WordList structure, there are few details of the interface that are in question.
A reasoned individual should be able to look at this design and say “this will
work—provided it is implemented correctly.” If a reviewer of the code were to
ask a question about how the structure works, it would lead to a refinement of
our understanding of the interface.
We have, then, the following required interface for the WordList class:
20 The Object-Oriented Method
We will leave the implementation details of this example until later. You might
consider various ways that the WordList might be implemented. As long as
the methods of the interface can be supported by your data structure, your
implementation is valid.
Exercise 1.3 Finish the sketch of the WordList class to include details about the
state variables.
Again, other approaches might be equally valid. No matter how we might rep-
resent a Rect, however, it seems that all rectangular regions with horizontal
and vertical sides can be specified with four integers. We can, then, construct a
Rect by specifying, say, the left and top coordinates and the width and height.
For consistency’s sake, it seems appropriate to allow rectangles to be drawn
anywhere (even off the screen), but the width and height should be non-negative
22 The Object-Oriented Method
values. We should make sure that these constraints appear in the documenta-
tion associated with the appropriate constructors and methods. (See Section 2.2
for more details on how to write these comments.)
Given our thinking, we have some obvious Rect constructors:
public Rect()
// post: constructs a trivial rectangle at origin
We should feel pleased with the progress we have made. We have developed
the signatures for the rectangle interface, even though we have no immediate
application. We also have some emerging answers on approaches to implement-
ing the Rect internally. If we declare our Rect data protected, we can insulate
ourselves from changes suggested by inefficiencies we may yet discover.
Exercise 1.4 Given this sketch of the Rect interface, how would you declare the
private data associated with the Rect object? Given your approach, describe how
you might implement the center(int x, int y) method.
1.8 Interfaces
Sometimes it is useful to describe the interface for a number of different classes,
without committing to an implementation. For example, in later sections of this
text we will implement a number of data structures that are able to be modified
by adding or removing values. We can, for all of these classes, specify a few of
their fundamental methods by using the Java interface declaration:
Notice that the body of each method has been replaced by a semicolon. It
is, in fact, illegal to specify any code in a Java interface. Specifying just the
method signatures in an interface is like writing boilerplate for a contract with-
out committing to any implementation. When we decide that we are interested
in constructing a new class, we can choose to have it implement the Structure
interface. For example, our WordList structure of Section 1.6 might have made
use of our Structure interface by beginning its declaration as follows:
When the WordList class is compiled by the Java compiler, it checks to see that
each of the methods mentioned in the Structure interface—add, remove, size, WordList
and the others—is actually implemented. In this case, only isEmpty is part of
the WordList specification, so we must either (1) not have WordList implement
the Structure interface or (2) add the methods demanded by Structure.
Interfaces may be extended. Here, we have a possible definition of what it
means to be a Set:
NW
NE
did later, when you optimize your implementation.
E
SW
SE
S
Principle 3 Design and abide by interfaces as though you were the user.
NW
NE
W
E
If the data are protected, you cannot access them from outside the class, and
SW
SE
S
1.10 Conclusions
The construction of substantial applications involves the development of com-
plex and interacting structures. In object-oriented languages, we think of these
structures as objects that communicate through the passing of messages or,
more formally, the invocation of methods.
We use object orientation in Java to write the structures found in this book.
It is possible, of course, to design data structures without object orientation, but
any effective data structuring model ultimately depends on the use of some form
of abstraction that allows the programmer to avoid considering the complexities
of particular implementations.
In many languages, including Java, data abstraction is supported by sepa-
rating the interface from the implementation of the data structure. To ensure
that users cannot get past the interface to manipulate the structure in an uncon-
trolled fashion, the system controls access to fields, methods, and classes. The
implementor plays an important role in making sure that the structure is usable,
given the interface. This role is so important that we think of implementation
as supporting the interface—sometimes usefully considered a contract between
the implementor and the user. This analogy is useful because, as in the real
world, if contracts are violated, someone gets upset!
Initial design of the interfaces for data structures arises from considering
how they are used in simple applications. Those method calls that are required
by the application determine the interface for the new structure and constrain,
in various ways, the choices we make in implementing the object.
In our implementation of an Association, we can use the Object class—
that class inherited by all other Java classes—to write very general data struc-
tures. The actual type of value that is stored in the Association is determined
by the values passed to the constructors and mutators of the class. This abil-
ity to pass a subtype to any object that requires a super type is a strength of
object-oriented languages—and helps to reduce the complexity of code.
26 The Object-Oriented Method
Problems
Solutions to the odd-numbered problems begin on page 451.
1.1 Which of the following are primitive Java types: int, Integer, double,
Double, String, char, Association, BankAccount, boolean, Boolean?
1.2 Which of the following variables are associated with valid constructor
calls?
BankAccount a,b,c,d,e,f;
Association g,h;
a = new BankAccount("Bob",300.0);
b = new BankAccount(300.0,"Bob");
c = new BankAccount(033414,300.0);
d = new BankAccount("Bob",300);
e = new BankAccount("Bob",new Double(300));
f = new BankAccount("Bob",(double)300);
g = new Association("Alice",300.0);
h = new Association("Alice",new Double(300));
1.3 For each pair of classes, indicate which class extends the other:
a. java.lang.Number, java.lang.Double
b. java.lang.Number, java.lang.Integer
c. java.lang.Number, java.lang.Object
d. java.util.Stack, java.util.Vector
1.10 Conclusions 27
e. java.util.Hashtable, java.util.Dictionary
Top view
Side view
1.11 Laboratory: The Day of the Week
Calculator
Month 1 2 3 4 5 6 7 8 9 10 11 12
Adjustment 1 4 4 0 2 5 0 3 6 1 4 6
If the year is divisible by 4 (it’s a leap year) and the date is January or February,
you must subtract 1 from the adjustment.
Remembering this table is equivalent to remembering how many days are in
each month. Notice that 144 is 122 , 025 is 52 , 036 is 62 , and 146 is a bit more
than 122 . Given this, the algorithm is fairly simple:
1. Write down the date numerically. The date consists of a month between
1 and 12, a day of the month between 1 and 31, and the number of
years since 1900. Grace Hopper, computer language pioneer, was born
December 9, 1906. That would be represented as year 6. Jana the Giraffe,
of the National Zoo, was born on January 18, 2001. That year would be
represented as year 101.
• the month adjustment from the given table (e.g., 6 for Admiral Hop-
per)
• the day of the month
• the year
4 This particular technique is due to John Conway, of Princeton University. Professor Conway
answers 10 day of the week problems before gaining access to his computer. His record is at the
time of this writing well under 15 seconds for 10 correctly answered questions. See “Scientist
at Work: John H. Conway; At Home in the Elusive World of Mathematics,” The New York Times,
October 12, 1993.
30 The Object-Oriented Method
• the whole number of times 4 divides the year (e.g., 25 for Jana the
Giraffe)
3. Compute the remainder of the sum of step 2, when divided by 7. The
remainder gives the day of the week, where Saturday is 0, Sunday is 1, etc.
Notice that we can compute the remainders before we compute the sum.
You may also have to compute the remainder after the sum as well, but if
you’re doing this in your head, this considerably simplifies the arithmetic.
6 + 30 + 75 + 18
6 + 2 + 5 + 4 = 17 ≡ 3 mod 7
2. You can find out how many thousandths of seconds have elapsed since
the 1960s, by calling the Java method, System.currentTimeMillis(). It In 2001,
returns a value of type long. We can use this to measure the duration of 1 trillion millis
an experiment, with code similar to the following: since the ’60s.
Dig that!
long start = System.currentTimeMillis();
//
// place experiment to be timed here
//
long duration = System.currentTimeMillis()-start;
System.out.println("time: "+(duration/1000.0)+" seconds.");
The granularity of this timer isn’t any better than a thousandth of a second.
Still, we’re probably not in Conway’s league yet.
After you finish your program, you will find you can quickly learn to answer
10 of these day of the week challenges in less than a minute.
Thought Questions. Consider the following questions as you complete the lab:
1. True or not: In Java is it true that (a % 7) == (a - a/7*7) for a >= 0?
2. It’s rough to start a week on Saturday. What adjustments would be nec-
essary to have a remainder of 0 associated with Sunday? (This might
allow a mnemonic of Nun-day, One-day, Twos-day, Wednesday, Fours-day,
Fives-day, Saturday.)
3. Why do you subtract 1 in a leap year if the date falls before March?
4. It might be useful to compute the portion of any calculation associated
with this year, modulo 7. Remembering that value will allow you to opti- For years
mize your most frequent date calculations. What is the remainder associ- divisible by 28:
ated with this year? think zero!
Notes:
Chapter 2
Comments, Conditions,
and Assertions
Concepts:
. Preconditions /* This is bogus code.
. Postconditions Wizards are invited to improve it. */
. Assertions —Anonymous
. Copyrighting code
what should be going on. When the output from the program’s code does not
Semiformal match the result of the formula, something is clearly wrong with your logic. But
convention: a which logic? The writing of mathematical comments is a level of detail most
meeting of tie programmers would prefer to avoid.
haters. A compromise is a semiformal convention for comments that provide a rea-
sonable documentation of when and what a program does. In the code associ-
ated with this book, we see one or two comments for each method or function
that describe its purpose. These important comments are the precondition and
postcondition.
The authors of this square root function expect that the parameter is not a
sqrt negative number. It is, of course, legal in Java to call a function or method if
the precondition is not met, but it might not produce the desired result. When
there is no precondition on a procedure, it may be called without failure.
The postcondition describes the state of the program once the routine has
been completed, provided the precondition was met. Every routine should have
some postcondition. If there were not a postcondition, then the routine would
not change the state of the program, and the routine would have no effect!
Always provide postconditions.
Pre- and postconditions do not force you to write code correctly. Nor do they
help you find the problems that do occur. They can, however, provide you with
a uniform method for documenting the programs you write, and they require
more thought than the average comment. More thought put into programs
lowers your average blood pressure and ultimately saves you time you might
spend more usefully playing outside, visiting museums, or otherwise bettering
your mind.
2.2 Assertions
In days gone by, homeowners would sew firecrackers in their curtains. If the
house were to catch fire, the curtains would burn, setting off the firecrackers. It
And the was an elementary but effective fire alarm.
batteries never An assertion is an assumption you make about the state of your program. In
needed Java, we will encode the assertion as a call to a function that verifies the state
replacing. of the program. That function does nothing if the assertion is true, but it halts
2.2 Assertions 35
NW
NE
early warning if you are about to be burned by your logic.
E
SW
SE
Principle 5 Test assertions in your code. S
The Assert class provides several functions to help you test the state of your
program as it runs:
public class Assert
{
static public void pre(boolean test, String message)
// pre: result of precondition test
Assert
// post: does nothing if test true, otherwise abort w/message
Each of pre, post, invariant, and condition methods test to see if its first
argument—the assertion—is true. The message is used to indicate the condition
tested by the assertion. Here’s an example of a check to make sure that the
precondition for the sqrt function was met:
public static double sqrt(double x)
// pre: x is nonnegative
// post: returns the square root of x
{
Assert.pre(x >= 0,"the value is nonnegative.");
double guess = 1.0;
double guessSquared = guess * guess;
Should we call sqrt with a negative value, the assertion fails, the message
is printed out, and the program comes to a halt. Here’s what appears at the
display:
structure.FailedPrecondition:
Assertion that failed: A precondition: the value is nonnegative.
at Assert.pre(Assert.java:17)
at sqrt(examples.java:24)
at main(examples.java:15)
The first two lines of this message indicate that a precondition (that x was non-
negative) failed. This message was printed within Assert.pre on line 17 of the
source, found in Assert.java. The next line of this stack trace indicates that
the call to Assert.pre was made on line 24 of examples.java at the start of
the sqrt function. This is the first line of the sqrt method. The problem is
(probably) on line 15 of the main procedure of examples.java. Debugging our
code should probably start in the main routine.
Beginning with Java 1.4, assertion testing is part of the formal Java language
specification. The assert keyword can be used to perform many of the types of
checks we have described. If, however, you are using an earlier version of Java,
or you expect your users may wish to use a version of Java before version 1.4,
you may find the Assert class to be a more portable approach to the testing of
the conditions of one’s code. A feature of language-based assertion testing is
that the tests can be automatically removed at compile time when one feels se-
cure about the way the code works. This may significantly improve performance
of classes that heavily test conditions.
2.3 Craftsmanship
If you really desire to program well, a first step is to take pride in your work—
pride enough to sign your name on everything you do. Through the centuries,
fine furniture makers signed their work, painters finished their efforts by dab-
bing on their names, and authors inscribed their books. Programmers should
stand behind their creations.
Computer software has the luxury of immediate copyright protection—it is
a protection against piracy, and a modern statement that you stand behind the
belief that what you do is worth fighting for. If you have crafted something as
best you can, add a comment at the top of your code:
If, of course, you have stolen work from another, avoid the comment and
consider, heavily, the appropriate attribution.
2.4 Conclusions 37
2.4 Conclusions
Effective programmers consider their work a craft. Their constructions are well
considered and documented. Comments are not necessary, but documentation
makes working with a program much easier. One of the most important com-
ments you can provide is your name—it suggests you are taking credit and re-
sponsibility for things you create. It makes our programming world less anony-
mous and more humane.
Special comments, including conditions and assertions, help the user and
implementor of a method determine whether the method is used correctly.
While it is difficult for compilers to determine the “spirit of the routine,” the
implementor is usually able to provide succinct checks of the sanity of the func-
tion. Five minutes of appropriate condition description and checking provided I’ve done my
by the implementor can prevent hours of debugging by the user. time!
Problems
Solutions to the odd-numbered problems begin on page 457.
2.1 What are the pre- and postconditions for the length method of the
java.lang.String class?
2.2 What are the pre- and postconditions for String’s charAt method?
2.3 What are the pre- and postconditions for String’s concat method?
2.4 What are the pre- and postconditions for the floor function in the
java.lang.Math class?
2.5 Improve the comments on an old program.
2.6 Each of the methods of Assert (pre, post, and condition) takes the
same parameters. In what way do the methods function differently? (Write a
test program to find out!)
2.7 What are the pre- and postconditions for java.lang.Math.asin class?
2.5 Laboratory: Using Javadoc Commenting
Within the class definition, there should be a Javadoc comment for each in-
stance variable and method. Typically, Javadoc comments for instance variables
are short comments that describe the role of the variable in supporting the class
state:
/**
* Size of the structure.
*/
int size;
/**
*
* This method computes the square root of a double value.
* @param x The value whose root is to be computed.
* @return The square root of x.
* @pre x >= 0
* @post computes the square root of x
*/
1. Download a copy of the Ratio.java source from the Java Structures web-
site. This version of the Ratio class does not include full comments.
2. Review the code and make sure that you understand the purpose of each
of the methods.
3. At the top of the Ratio.java file, place a Javadoc comment that describes
the class. The comment should describe the features of the class and an
example of how the class might be used. Make sure that you include an
@author comment (use your name).
4. Run the documentation generation facility for your particular environ-
ment. For Sun’s Java environment, the Javadoc command takes a parame-
ter that describes the location of the source code that is to be documented:
javadoc prog.java
2 In this book, where there are constraints on space, the pre- and postconditions are provided in
non-Javadoc comments. Code available on the web, however, is uniformly commented using the
Javadoc comments. Javadoc can be upgraded to recognize pre- and postconditions; details are
available from the Java Structures website.
2.5 Laboratory: Using Javadoc Commenting 41
The result is an index.html file in the current directory that contains links
to all of the necessary documentation. View the documentation to make
sure your description is formatted correctly.
5. Before each instance variable write a short Javadoc comment. The com-
ment should begin with /** and end with */. Generate and view the
documentation and note the change in the documentation.
6. Directly before each method write a Javadoc comment that includes, at
a minimum, one or two sentences that describe the method, a @param
comment for each parameter in the method, a @return comment describ-
ing the value returned, and a @pre and @post comment describing the
conditions.
Generate and view the documentation and note the change in the doc-
umentation. If the documentation facility does not appear to recognize
the @pre and @post keywords, the appropriate Javadoc doclet software
has not been installed correctly. More information on installation of the
Javadoc software can be found at the Java Structures website.
Notes:
Chapter 3
Vectors
Concepts:
Climb high, climb far,
. Vectors
your goal the sky, your aim the star.
. Extending arrays
—Inscription on a college staircase
. Matrices
{
data[i] = s.next();
}
}
Unfortunately, if you are running your program on a small machine and have
small amounts of data, you are in trouble (see Problem 3.9). Because the array
is so large, it will not fit on your machine—even if you want to read small
amounts of data. You have to recompile the program with a smaller upper
bound and try again. All this seems rather silly, considering how simple the
problem appears to be.
We might, of course, require the user to specify the maximum size of the
array before the data are read, at run time. Once the size is specified, an appro-
priately sized array can be allocated. While this may appear easier to program,
the burden has shifted to the user of the program: the user has to commit to a
specific upper bound—beforehand:
The Vector starts empty and expands (using the add method) with every String
read from the input. Notice that the program doesn’t explicitly keep track of the
number of values stored in data, but that the number may be determined by a
call to the size method.
an existing element, one calls get. If remove is called with an Object, it re-
moves at most one element, selected by value. Another remove method shrinks
the logical size of the Vector by removing an element from an indicated loca-
tion. The set method is used to change a value in the Vector. Finally, two
methods provide feedback about the current logical size of the Vector: size
and isEmpty. The size method returns the number of values stored within
the Vector. As elements are added to the Vector, the size increases from zero
up to the capacity of the Vector. When the size is zero, then isEmpty returns
true. The result is a data structure that provides constant-time access to data
within the structure, without concern for determining explicit bounds on the
structure’s size.
There are several ways that a Vector is different than its array counterpart.
First, while both the array and Vector maintain a number of references to ob-
jects, the Vector typically grows with use and stores a non-null reference in
each entry. An array is a static structure whose entries may be initialized and
used in any order and are often null. Second, the Vector has an end where ele-
ments can be appended, while the array does not directly support the concept of
appending values. There are times, of course, when the append operation might
not be a feature desired in the structure; either the Vector or array would be a
suitable choice.
The interface for Vectors in the structure package was driven, almost ex-
clusively, by the interface for Java’s proprietary java.util.Vector class. Thus,
while we do not have access to the code for that class, any program written to
use Java’s Vector class can be made to use the Vector class described here;
their interfaces are consistent.
Vector list;
String targetWord;
java.util.Random generator = new java.util.Random();
list = new Vector(10); WordList
list.add("clarify");
list.add("entered");
list.add("clerk");
while (list.size() != 0)
{
{ // select a word from the list
int index = Math.abs(generator.nextInt())%list.size();
targetWord = (String)list.get(index);
}
// ... play the game using targetWord ...
list.remove(targetWord);
}
48 Vectors
Here, the operations of the Vector are seen to be very similar to the opera-
tions of the WordList program fragment shown on page 19. The Vector class,
however, does not have a selectAny method. Instead, the bracketed code ac-
complishes that task. Since only Strings are placed within the Vector, the
assignment of targetWord involves a cast from Object (the type of value re-
turned from the get method of Vector) to String. This cast is necessary for
Java to be reassured that you’re expecting an element of type String to be
returned. If the cast were not provided, Java would complain that the types
involved in the assignment were incompatible.
Now that we have an implementation of the Hangman code in terms of both
the WordList and Vector structures, we can deduce an implementation of the
WordList structure in terms of the Vector class. In this implementation, the
WordList contains a Vector that is used to hold the various words, as well
as the random number generator (the variable generator in the code shown
above). To demonstrate the implementation, we look at the implementation of
the WordList’s constructor and selectAny method:
protected Vector theList;
protected java.util.Random generator;
public WordList(int n)
{
theList = new Vector(n);
generator = new java.util.Random();
}
Clearly, the use of a Vector within the WordList is an improvement over the
direct use of an array, just as the use of WordList is an improvement over the
complications of directly using a Vector in the Hangman program.
2 Recently, using informal “literary forensics,” Don Foster has identified the author of the anony-
WordFreq mously penned book Primary Colors and is responsible for new attributions of poetry to Shake-
speare. Foster also identified Major Henry Livingston Jr. as the true author of “The Night Before
Christmas.”
3.3 Example: Word Frequency 49
{
Vector vocab = new Vector(1000);
Scanner s = new Scanner(System.in);
int i;
First, for each word found on the input, we maintain an Association between
the word (a String) and its frequency (an Integer). Each element of the
Vector is such an Association. Now, the outer loop at the top reads in each
word. The inner loop scans through the Vector searching for matching words
that might have been read in. Matching words have their values updated. New
words cause the construction of a new Association. The second loop scans
through the Vector, printing out each of the Associations.
50 Vectors
Unlike other languages, all arrays within Java must be explicitly allocated. At
the time the array is allocated, the number of elements is specified. Thus, in the
constructor, the new operator allocates the number of elements desired by the
user. Since the size of an array can be gleaned from the array itself (by asking
for elementData.length), the value does not need to be explicitly stored within
the Vector object.3
To access and modify elements within a Vector, we use the following oper-
ations:
public Object get(int index)
3 It could, of course, but explicitly storing it within the structure would mean that the implementor
would have to ensure that the stored value was always consistent with the value accessible through
the array’s length variable.
3.4 The Implementation 51
The arguments to both methods identify the location of the desired element. Be-
cause the index should be within the range of available values, the precondition
states this fact.
For the accessor (get), the desired element is returned as the result. The set
method allows the Object reference to be changed to a new value and returns
the old value. These operations, effectively, translate operations on Vectors
into operations on arrays.
Now consider the addition of an element to the Vector. One way this can
be accomplished is through the use of the one-parameter add method. The task
requires extending the size of the Vector and then storing the element at the
location indexed by the current number of elements (this is the first free location
within the Vector). Here is the Java method:
public void add(Object obj)
// post: adds new element to end of possibly extended vector
{
ensureCapacity(elementCount+1);
elementData[elementCount] = obj;
elementCount++;
}
(We will discuss the method ensureCapacity later. Its purpose is simply to en-
sure that the data array actually has enough room to hold the indicated number
of values.) Notice that, as with many modern languages, arrays are indexed
starting at zero. There are many good reasons for doing this. There are prob-
ably just as many good reasons for not doing this, but the best defense is that
this is what programmers are currently used to. N
NW
NE
W
SE
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 0 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 8
0 0 0 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 7 8
0 0 0 0 0 0 0 0 0 9 0 1 1 2 3 4 5 6 7 8
(a) (b)
Figure 3.1 The incorrect (a) and correct (b) way of moving values in an array to make
room for an inserted value.
Note that the loop that moves the elements higher in the array runs backward.
To see why, it is only necessary to see what happens if the loop runs forward (see
Figure 3.1a): the lowest element gets copied into higher and higher elements,
ultimately copying over the entire Vector to the right of the insertion point.
Figure 3.1b demonstrates the correct technique.
Removing an element from a specific location in the Vector is very similar,
reversing the effect of add. Here, using an argument similar to the previous one,
the loop moves in the forward direction:
We also allow the removal of a specific value from the Vector, by passing an
example Object to remove (not shown). Within this code, the equals method
of the value passed to the routine is used to compare it to values within the
Vector. When (and if) a match is found, it is removed using the technique just
described.
The methods having to do with size are relatively straightforward:
public boolean isEmpty()
// post: returns true iff there are no elements in the vector
{
return size() == 0;
}
The logical size of the Vector is the number of elements stored within the
Vector, and it is empty when this size is zero.
hold two. The original element must be copied to the new space to complete
the operation. When a third is added, the first two must be copied. The result
is that
n(n − 1)
1 + 2 + 3 + · · · + (n − 1) =
2
elements are copied as the array grows to size n. (Proving this last formula is
the core of Problem 3.8.) This is expensive since, if in the beginning we had
just allocated the Vector with a capacity of n elements, none of the data items
would have to be copied during extension!
It turns out there is a happy medium: every time you extend the array, just
double its capacity. Now, if we reconsider the number of times that an item
gets copied during the extension process, the result is dramatically different.
Suppose, for neatness only, that n is a power of 2, and that the Vector started
with a capacity of 1. What do we know? When the Vector was extended from
capacity 1 to capacity 2, one element was copied. When the array was extended
from capacity 2 to capacity 4, two elements were copied. When the array was
extended from capacity 4 to capacity 8, four elements were copied. This contin-
ues until the last extension, when the Vector had its capacity extended from n2
to n: then n2 elements had to be preserved. The total number of times elements
were copied is
n
1 + 2 + 4 + ··· + = n − 1
2
Thus, extension by doubling allows unlimited growth of the Vector with an
overhead that is proportional to the ultimate length of the array. Another way
to think about it is that there is a constant overhead in supporting each element
of a Vector extended in this way.
The Java language specifies a Vector interface that allows the user to specify
how the Vector is to be extended if its capacity is not sufficient for the current
operation. When the Vector is constructed, a capacityIncrement is specified.
This is simply the number of elements to be added to the underlying array
when extension is required. A nonzero value for this increment leads to the n2
behavior we saw before, but it may be useful if, for example, one does not have
the luxury of being able to double the size of a large array. If the increment is
zero, the doubling strategy is used.
Our design, then, demands another protected value to hold the increment;
we call this capacityIncrement. This value is specified in a special constructor
and is not changed during the life of the Vector:
This code deserves careful investigation. If the current length of the underlying
array is already sufficient to provide minCapacity elements, then the method
does nothing. On the other hand, if the Vector is too short, it must be ex-
tended. We use a loop here that determines the new capacity by doubling (if
capacityIncrement is zero) or by directly incrementing if capacityIncrement
is nonzero. In either case, by the time the loop is finished, the desired capacity
is determined. At that point, an array of the appropriate size is allocated, the
old values are copied over, and the old array is dereferenced in favor of the new.
56 Vectors
we have seen in Section 3.2: each element of the Set would be stored in a
location in the Vector. Whenever a new value is to be added to the Set, it
is only added if the Set does not already contain the value. When values are
removed from the Set, the structure contracts. At all times, we are free to keep
the order of the data in the Vector hidden from the user since the ordering of
the values is not part of the abstraction.
We construct a SetVector using the following constructors, which initialize
a protected Vector:
public SetVector()
// post: constructs a new, empty set
{
data = new Vector();
}
The second constructor is a copy constructor that makes use of the union op-
erator, addAll. Since the initial set is empty (the call to this() calls the first
constructor), the SetVector essentially picks up all the values found in the other
structure.
Most methods of the Set are adopted from the underlying Vector class. For
example, the remove method simply calls the remove method of the Vector:
The add method, though, is responsible for ensuring that duplicate values are
not added to the Set. It must first check to see if the value is already a member:
Rows 0 1 2 3
Figure 3.2 The Matrix class is represented as a Vector of rows, each of which is a
Vector of references to Objects. Elements are labeled with their indices.
The two-parameter constructor specifies the width and height of the Matrix. El-
ements of the Matrix are initially null, but may be reset with the set method.
This method, along with the get method, accepts two parameters that identify
the row and the column of the value. To expand and shrink the Matrix, it is
possible to insert and remove both rows and columns at any location. When a
row or column is removed, a Vector of removed values is returned. The meth-
ods height and width return the number of rows and columns found within
the Matrix, respectively.
To support this interface, we imagine that a Matrix is a Vector of rows,
which are, themselves, Vectors of values (see Figure 3.2). While it is not strictly
necessary, we explicitly keep track of the height and width of the Matrix (if we
determine at some later date that keeping this information is unnecessary, the
interface would hide the removal of these fields). Here, then, is the constructor
for the Matrix class:
We allocate a Vector for holding the desired number of rows, and then, for each
row, we construct a new Vector of the appropriate width. All the elements are
initialized to null. It’s not strictly necessary to do this initialization, but it’s a
good habit to get into.
The process of manipulating individual elements of the matrix is demon-
strated by the get and set methods:
public Object get(int row, int col)
// pre: 0 <= row < height(), 0 <= col < width()
// post: returns object at (row, col)
{
Assert.pre(0 <= row && row < height, "Row in bounds.");
Assert.pre(0 <= col && col < width, "Col in bounds.");
Vector theRow = (Vector)rows.get(row);
return theRow.get(col);
}
Rows 0 1 2 3
Figure 3.3 The insertion of a new row (gray) into an existing matrix. Indices are those
associated with matrix before addRow. Compare with Figure 3.2.
that in the set method, the row is found using the get method, while the
element within the row is changed using the set method. Although the element
within the row changes, the row itself is represented by the same vector.
Many of the same memory management issues discussed in reference to
Vectors hold as well for the Matrix class. When a row or column needs to be
expanded to make room for new elements (see Figure 3.3), it is vital that the
management of the arrays within the Vector class be hidden. Still, with the
addition of a row into the Matrix, it is necessary to allocate the new row object
and to initialize each of the elements of the row to null:
3.9 Conclusions
Most applications that accept data are made more versatile by not imposing
constraints on the number of values processed by the application. Because the
size of an array is fixed at the time it is allocated, programmers find it difficult
to create size-independent code without the use of extensible data structures.
The Vector and Matrix classes are examples of extensible structures.
Initially Vectors are empty, but can be easily expanded when necessary.
When a programmer knows the upper bound on the Vector size, this infor-
mation can be used to minimize the amount of copying necessary during the
entire expansion process. When a bound is not known, we saw that doubling
the allocated storage at expansion time can reduce the overall copying cost.
The implementation of Vector and Matrix classes is not trivial. Data ab-
straction hides many important housekeeping details. Fortunately, while these
details are complex for the implementor, they can considerably reduce the com-
plexity of applications that make use of the Vector and Matrix structures.
What can be said about the values found in elementData after this code is
executed?
3.10 When there is more than one constructor for a class, when and how do
we indicate the appropriate method to use? Compare, for example,
3.9 Conclusions 65
3.11 Is the row index of the Matrix bounded by the matrix height or width?
When indexing a Matrix which is provided first, the row or the column?
Problems
Solutions to the odd-numbered problems begin on page 457.
3.1 Explain the difference between the size and capacity of a vector. Which
is more important to the user?
3.2 The default capacity of a Vector in a structure package implementa-
tion is 10. It could have been one million. How would you determine a suitable
value?
3.3 The implementation of java.util.Vector provides a method trimTo-
Size. This method ensures that the capacity of the Vector is the same as its
size. Why is this useful? Is it possible to trim the capacity of a Vector without
using this method?
3.4 The implementation of java.util.Vector provides a method setSize.
This method explicitly sets the size of the Vector. Why is this useful? Is it
possible to set the size of the Vector without using this method?
3.5 Write a Vector method, indexOf, that returns the index of an object in
the Vector. What should the method return if no object that is equals to this
object can be found? What does java.lang.Vector do in this case? How long
does this operation take to perform, on average?
3.6 Write a class called BitVector that has an interface similar to Vector,
but the values stored within the BitVector are all known to be boolean (the
primitive type). What is the primary advantage of having a special-purpose
vector, like BitVector?
3.7 Suppose we desire to implement a method reverse for the Vector class.
One approach would be to remove location 0 and to use add near the end or tail
of the Vector. Defend or reject this suggested implementation. In either case,
write the best method you can.
3.8 Suppose that a precisely sized array is used to hold data, and that each
time the array size is to be increased, it is increased by exactly one and the data
are copied over. Prove that, in the process of growing an array incrementally
from size 0 to size n, approximately n2 values must be copied.
3.9 What is the maximum length array of Strings you can allocate on your
machine? (You needn’t initialize the array.) What is the maximum length array
of boolean you can allocate on your machine? What is to be learned from the
ratio of these two values?
3.10 Implement the Object-based remove method for the Vector class.
66 Vectors
3.11 In our discussion of L-systems, the resulting strings are always linear.
Plants, however, often branch. Modify the LSystem program so that it includes
the following five productions:
Before After Before After Before After
S T U V W [S]U
T U V W
where [S] is represented by a new Vector that contains a single S. (To test to
see if an Object, x, is a Vector, use the test x instanceof Vector.)
3.12 Finish the two-dimensional Vector-like structure Matrix. Each element
of the Matrix is indexed by two integers that identify the row and column
containing the value. Your class should support a constructor, methods addRow
and addCol that append a row or column, the get and set methods, and width
and height methods. In addition, you should be able to use the removeRow and
removeCol methods.
3.13 Write Matrix methods for add and multiply. These methods should
implement the standard matrix operations from linear algebra. What are the
preconditions that are necessary for these methods?
3.14 A Matrix is useful for nonmathematical applications. Suppose, for ex-
ample, that the owners of cars parked in a rectangular parking lot are stored
in a Matrix. How would you design a new Matrix method to return the lo-
cation of a particular value in the Matrix? (Such an extension implements an
associative memory. We will discuss associative structures when we consider
Dictionarys.)
3.15 An m × n Matrix could be implemented using a single Vector with
mn locations. Assuming that this choice was made, implement the get method.
What are the advantages and disadvantages of this implementation over the
Vector of Vectors approach?
3.16 A triangular matrix is a two-dimensional structure with n rows. Row i
has i + 1 columns (numbered 0 through i) in row i. Design a class that supports
all the Matrix operations, except addRow, removeRow, addCol, and removeCol.
You should also note that when a row and column must be specified, the row
must be greater than or equal to the column.
3.17 A symmetric matrix is a two-dimensional Matrix-like structure such that
the element at [i][j] is the same element found at [j][i]. How would you imple-
ment each of the Matrix operations? The triangular matrix of Problem 3.16
may be useful here. Symmetric matrices are useful in implementing undirected
graph structures.
3.18 Sometimes it is useful to keep an unordered list of characters (with
ASCII codes 0 through 127), with no duplicates. Java, for example, has a
CharSet class in the java.util package. Implement a class, CharSet, using
a Vector. Your class should support (1) the creation of an empty set, (2) the
addition of a single character to the set, (3) the check for a character in the set,
(4) the union of two sets, and (5) a test for set equality.
3.10 Laboratory: The Silver Dollar Game
The game begins by placing silver dollars in a few of the squares. Each square
holds at most one coin. Interesting games begin with some pairs of coins sepa-
rated by one or more empty squares.
The goal is to move all the n coins to the leftmost n squares of the paper.
This is accomplished by players alternately moving a single coin, constrained by
the following rules:
1. Coins move only to the left.
2. No coin may pass another.
3. No square may hold more than one coin.
The last person to move is the winner.
Procedure. Write a program to facilitate playing the Silver Dollar Game. When
the game starts, the computer has set up a random strip with 3 or more coins.
Two players are then alternately presented with the current game state and are
allowed to enter moves. If the coins are labeled 0 through n−1 from left to right,
a move could be specified by a coin number and the number of squares to move
the coin to the left. If the move is illegal, the player is repeatedly prompted to
enter a revised move. Between turns the computer checks the board state to
determine if the game has been won.
Here is one way to approach the problem:
1. Decide on an internal representation of the strip of coins. Does your rep-
resentation store all the information necessary to play the game? Does
your representation store more information than is necessary? Is it easy to
test for a legal move? Is it easy to test for a win?
2. Develop a new class, CoinStrip, that keeps track of the state of the play-
ing strip. There should be a constructor, which generates a random board.
Another method, toString, returns a string representation of the coin
strip. What other operations seem to be necessary? How are moves per-
formed? How are rules enforced? How is a win detected?
68 Vectors
Thought Questions. Consider the following questions as you complete the lab:
Hint: When 1. How might one pick game sizes so that, say, one has a 50 percent chance
flipped, the of a game with three coins, a 25 percent chance of a game with four coins,
Belgian Euro is a 12 12 percent chance of a game with five coins, and so on? Would your
heads technique bias your choice of underlying data structure?
149 times
out of 250. 2. How might one generate games that are not immediate wins? Suppose
you wanted to be guaranteed a game with the possibility of n moves?
3. Suppose the computer could occasionally provide good hints. What op-
portunities appear easy to recognize?
4. How might you write a method, computerPlay, where the computer plays
to win?
5. A similar game, called Welter’s Game (after C. P. Welter, who analyzed the
game), allows the coins to pass each other. Would this modification of the
rules change your implementation significantly?
Notes:
Chapter 4
Generics
1 Even after considering compile-time and runtime errors, there are many errors that even a run-
ning system cannot detect. For example, undesirable infinite loops (some are desirable) are often
the result of errors in logic that the computer cannot detect. The word “cannot” is quite strong here:
it is impossible to build an environment that correctly identifies any program that loops infinitely
(or even more broadly–fails to halt). This result is due to Alan Turing.
70 Generics
Instead of using Vector we use StringVector. The compiler knows that the
add method must take a String, so passing an array of Strings to the add
method generates the error:
LongWords2.java:12: cannot find symbol
symbol : method add(java.lang.String[])
location: class StringVector
longWords.add(args);
^
NE
E
SW
SE
Here, (1) the actual source of the logical error was identified, and (2) it was
identified at compile-time.
To accomplish this, however, we had to write a new class and modify it
appropriately. This is, itself, an error-prone task. Also, we must rewrite the
class for every every new contained type. Soon we would be overwhelmed by
special-purpose classes. These classes are not related in any way and, it should
be noted, our original class, Vector, would never be used. Imagine the difficulty
of adding a new method to the Vector class that you wished to make available
to each of your specialized versions! A better solution is to create a generic class
or a class parameterized by the type of data it holds.
/*
for example:
Association<String,Integer> personAttribute =
new Assocation<String,Integer>("Age",34);
*/
public Association(K key, V value)
// pre: key is non-null
// post: constructs a key-value pair
public V getValue()
// post: returns value from association
public K getKey()
// post: returns key from association
At the time of their declaration, parameterized class name are followed by a list
of comma-separated type parameters in angle brackets. This book follows the
common convention that type parameters are indicated by single capital Latin
letters.3 In this example, K is a place holder for the type of the association’s
key, while V will be used to represent the actual type of the association’s value.
Within the class definition, these type variables may be used wherever class
names are used: declaring data variables and declaring method parameters and
return values. The one constraint is that
3 There is some dispute about this convention. See your instructor. Professional driver, closed
course. Your mileage may vary. Danger, Will Robinson. Some identifiers too small for three year
olds.
74 Generics
Notice that there are no casts in this code: since the value is declared to be of
type V, and since the return value for setValue is the same, no cast is necessary.
The removal of casts is a sign that type checking will happen in the compiler
and not while the program is running.
To make use of the generic version of a class, we must specify the actual
parameter types associated with the formal types demanded by Association.
For example, a new Association between a String and an Integer would be
declared:
Association<String,Integer> personAttribute =
new Assocation<String,Integer>("Age",34);
public Vector()
// post: constructs a vector with capacity for 10 elements
4 Two syntactic features of Java 5 include autoboxing and its inverse, -unboxing. With autobox-
ing, primitive types are automatically “boxed” into their object equivalents if doing so would fix
a type incompatibility. In addition, the corresponding object types will be converted to primitive
equivalents, if necessary.
4.2 Implementing Generic Container Classes 75
5 This reads like a law journal. A technical point important to note here is that a Vector<E>
does not have any relation to Vector<S> if S is a subclass of E. For example, you cannot assign a
76 Generics
The Vector constructor does not mention the <E> type parameter in its name.
Why? The type parameter is obvious because the constructor declaration ap-
pears within the class Vector<E>. When the value is constructed, of course,
check of the data type. This check is necessitated by the fact that, over time, alternative arrays—
arrays of different base types—can be assigned to a single array reference. Unfortunately Java 5
does not transmit parameterized type information to the running program. This means that param-
eterized types cannot be exactly checked at runtime, but they should be. The easiest way to enforce
correct checking is to make it impossible to construct arrays of parameterized types. We expect
future implementations of Java will address this issue, and that David Ortiz will be the American
League Most Valuable Player, but good things take time.
7 See more about privacy rights in Appendix B.8.
4.2 Implementing Generic Container Classes 77
the actual parameter appears within the new statement (see the example on
page 78). Within the constructor, the supporting array is allocated as a logically
empty array of Object, and the initial value (type E) is cached away within the
type. Is there any way that a non-E value can be stored in elementData, using
this method? No. The method ensures the safety of the types of Vector’s values.
If we ask this question for each mutator method, and the answer is uniformly
No, we can be sure the Vector contains only the correct types.
Now, consider a method that adds a value to the Vector:
public void add(E obj)
// post: adds new element to end of possibly extended vector
{
ensureCapacity(elementCount+1);
elementData[elementCount] = obj;
elementCount++;
}
The Vector is expanded and the new value is appended to the end of the array.
Is there a possibility of a type error, here? In a more extensive review, we might
check to make sure ensureCapacity allows only type E values in elementData.
(It does.) The second and third statements append an object of type E to the ar-
ray, so there is no opportunity for a non-E value to be assigned. Incidentally, one
might wonder what happens if the add method were called with a non-E type. It
is precisely what happens in the StringVector example at the beginning of the
chapter: an exception is raised at the site of the call, during compilation. We’ll
review this in a moment.
Next, we consider the get method. This accessor method retrieves a value
from within the array.
public E get(int index)
{
return (E)elementData[index];
}
By assumption (and eventually through proof) we believe the safety of the array
is intact to this point of access. Every element is of type E, even though it appears
in a more general array of Objects. The cast of the value, while required, will
always hold; runtime type errors will never occur at this point. The method,
then, returns a value of type E.
The set method is a combination of the prior two methods. It is useful to
convince yourself that (1) the method is type-safe, and (2) the cast is necessary
but always successful.
public E set(int index, E obj)
{
Assert.pre(0 <= index && index < elementCount,"index is within bounds");
E previous = (E)elementData[index];
elementData[index] = obj;
return previous;
}
78 Generics
It is, of course, possible to make type mistakes when using the Vector class.
They fall, however, into two distinct categories. Vector implementation mis-
takes may allow elements of types other than E into the array. These mistakes
are always possible, but they are the responsiblity of a single programmer. Good
design and testing will detect and elminate these compile-time and runtime er-
rors quickly. The second class of errors are abuses of the Vector<E> class by
the client application. These errors are unfortunate, but they will be reported
at compile-time at the appropriate location, one that focuses the programmer’s
attention on the mistake.
We can now test our new implementation on working code and then attempt
to break it. In LongWords3, we consider, yet again, the implementation of our
program that checks for long argument words. The implementation makes use
of a Vector<String> as follows:
public static void main(String[] args)
{
Vector<String> longWords = new Vector<String>();
LongWords3 int i;
for (i = 0; i < args.length; i++) {
if (args[i].length() > 4) {
longWords.add(args[i]); // line 12
}
}
...
for (i = 0; i < longWords.size(); i++) {
String word = longWords.get(i); // line 31
System.out.println(word+", length "+word.length());
}
}
4.3 Conclusions
When we write data structures, we often write them for others. When we write
for others, we rarely know the precise details of the application. It is important
that we write our code as carefully as possible so that semantic errors associated
with our data structures occur as early as possible in development and as close
as possible to the mistake.
We have seen, here, several examples of generic data types. The Association
class has two type parameters, and is typical in terms of the simplicity of writ-
ing generalized code that can be tailored for use in specific applications. Formal
type parameters hold the place for actual type parameters to be specified later.
Code is written just as before, but with the knowledge that our structures will
not sacrifice the type-safety of their client applications.
There is one “fly in the ointment”: we cannot construct arrays of any type
that involves a formal type parameter. These situations are relatively rare and,
for the most part, can be limited to the some carefully crafted code in the Vector
class. When array-like storage is required in the future, use of the extensible
Vector class has one more advantage over arrays: it hides the difficulties of
manipulating generic arrays.
Type bounds provide a mechanism to constrain the type parameters that ap-
pear in generic class specifications. These bounds can be disturbingly complex.
The remainder of this text demonstrates the power of the generic approach
to writing data structures. While the structure of these data types becomes
increasingly technical, the nature of specifying these structures in a generic and
flexible manner remains quite simple, if not natural.
Chapter 5
Design Fundamentals
Concepts:
. Asymptotic analysis and big-O notation We shape clay into a pot,
but it is the emptiness inside
. Time-space trade-off
that holds whatever we want.
. Back-of-the-envelope estimations —Lao Tzu
. Recursion and Induction
referenced. Yet, modern architectures may have execution speeds that vary as
much as a factor of 10 or more. The accurate counting of any specific kind of
operation alone does not give us much information about the actual running
time of a specific implementation. Thus, while detailed accounting can be use-
ful for understanding the fine distinctions between similar implementations, it
is not generally necessary to make such detailed analyses of behavior. Distinc-
tions between structures and algorithms, however, can often be identified by
observing patterns of performance over a wide variety of problems.
Definition 5.1 A function f (n) is O(g(n)) (read “order g” or “big-O of g”), if and
only if there exist two positive constants, c and n0 , such that
|f (n)| ≤ c · g(n)
for all n ≥ n0 .
In this text, f will usually be a function of problem size that describes the utiliza-
tion of some precious resource (e.g., time or space). This is a subtle definition
(and one that is often stated incorrectly), so we carefully consider why each of
the parts of the definition is necessary.
Most importantly, we would like to think of g(n) as being proportional to an
upper bound for f (n) (see Figure 5.1). After some point, f (n) does not exceed
an “appropriately scaled” g(n). The selection of an appropriate c allows us to
enlarge g(n) to the extent necessary to develop an upper bound. So, while g(n)
may not directly exceed f (n), it might if it is multiplied by a constant larger
than 1. If so, we would be happy to say that f (n) has a trend that is no worse
than that of g(n). You will note that if f (n) is O(g(n)), it is also O(10 · g(n)) and
O(5 + g(n)). Note, also, that c is positive. Generally we will attempt to bound
f (n) by positive functions.
Second, we are looking for long-term behavior. Since the most dramatic
growth in functions is most evident for large values, we are happy to ignore
“glitches” and anomalous behavior up to a certain point. That point is n0 . We
Nails = proofs. do not care how big n0 must be, as long as it can be nailed down to some fixed
value when relating specific functions f and g.
5.1 Asymptotic Analysis Tools 83
g(n)
g(n)
f(n)
f(n) g(n)
f(n)
n n n
Third, we are not usually interested in whether the function f (n) is negative
or positive; we are just interested in the magnitude of its growth. In reality, most
of the resources we consider (e.g., time and space) are measured as positive
values and larger quantities of the resource are consumed as the problem grows
in size; growth is usually positive.
Most functions we encounter fall into one of a few categories. A function
that is bounded above by a constant is classified as O(1).1 The constant factor
can be completely accounted for in the value of c in Definition 5.1. These func-
tions measure size-independent characteristics of data structures. For example,
the time it takes to assign a value to an arbitrary element of an array of size n
is constant. What’s your
When a function grows proportionately to problem size, or linearly, we ob- best guess for
serve it is O(n). Depending on what’s being measured, this can be classified as the time to
“nice behavior.” Summing the values in an n-element array, for example, can be assign a value?
1
second?
accomplished in linear time. If we double the size of the array, we expect the 1000
1
sec.?
time of the summation process to grow proportionately. Similarly, the Vector 1000000
1
s.?
takes linear space. Most methods associated with the Vector class, if not con- 1000000000
stant, are linear in time and space. If we develop methods that manipulate
the n elements of a Vector of numbers in superlinear time—faster than linear
growth—we’re not pleased, as we know it can be accomplished more efficiently.
Other functions grow polynomially and are O(nc ), where c is some constant
greater than 1. The function n2 + n is O(n2 ) (let c = 2 and n0 = 1) and
therefore grows as a quadratic. Many simple methods for sorting n elements of
an array are quadratic. The space required to store a square matrix of size n
takes quadratic space. Usually, we consider functions with polynomial growth
to be fairly efficient, though we would like to see c remain small in practice. Grass could be
Because a function nc−1 is O(n · nc−1 ) (i.e., O(nc )), we only need consider the greener.
growth of the most significant term of a polynomial function. (It is, after all,
most significant!) The less significant terms are ultimately outstripped by the
leading term.
5
n! n log( n)
n
4
3
2
2n n
sqrt( n)
2
1
log(n)
0
0 1 2 3 4 5
Figure 5.2 Near-origin details of common curves. Compare with Figure 5.3.
100
2n
n! n
80
n log( n)
n2
60
40
20
sqrt( n)
log( n)
0
0 20 40 60 80 100
Figure 5.3 Long-range trends of common curves. Compare with Figure 5.2.
5.1 Asymptotic Analysis Tools 85
Some functions experience exponential growth (see Figures 5.2 and 5.3).
The functions are O(cn ), where c is a constant greater than 1. Enumerating
all strings of length n or checking topological equivalence of circuits with n
devices are classic examples of exponential algorithms. Constructing a list of
the n-digit palindromes requires exponential time and space. The demands of “2002” is a
an exponential process grow too quickly to make effective use of resources. palindrome.
As a result, we often think of functions with exponential behavior as being
intractable. In the next section we will see that some recursive solutions to
problems are exponential. While these solutions are not directly useful, simple
insights can sometimes make these algorithms efficient.
5.1.2 Examples
A “Difference Table”
Suppose we’re interested in printing a 10 by 10 table of differences between
two integers (row-col) values. Each value in the table corresponds to the result
of subtracting the row number from the column number:
0 -1 -2 -3 -4 -5 -6 -7 -8 -9
1 0 -1 -2 -3 -4 -5 -6 -7 -8
2 1 0 -1 -2 -3 -4 -5 -6 -7 Analysis
3 2 1 0 -1 -2 -3 -4 -5 -6
4 3 2 1 0 -1 -2 -3 -4 -5
5 4 3 2 1 0 -1 -2 -3 -4
6 5 4 3 2 1 0 -1 -2 -3
7 6 5 4 3 2 1 0 -1 -2
8 7 6 5 4 3 2 1 0 -1
9 8 7 6 5 4 3 2 1 0
Each of the loops executes n times. Since printing a value (line 3) takes constant
time c1 , the inner loop at line 2 takes c1 n time. If line 4 takes constant time c2 ,
86 Design Fundamentals
then the outer loop at line 1 takes n(c1 n+c2 ) = c1 n2 +c2 n time. This polynomial
is clearly O(n2 ) (take c = c1 + c2 and n0 = 1). Doubling the problem size
approximately quadruples the running time.
As a rule of thumb, each loop that performs n iterations multiplies the com-
plexity of each iteration by a factor of n. Nested loops multiply the complexity
of the most deeply nested code by another power of n. As we have seen, loops
doubly nested around a simple statement often consume quadratic time.
Since there are only three variables in our difference method, it takes con-
stant space—an amount of space that is independent of problem size.
A Multiplication Table
Unlike the difference operator, the multiplication operator is commutative, and
the multiplication table is symmetric. Therefore, when printing a multiplication
table of size n, only the “lower triangular” region is necessary:
1
2 4
3 6 9
4 8 12 16
5 10 15 20 25
6 12 18 24 30 36
7 14 21 28 35 42 49
8 16 24 32 40 48 56 64
9 18 27 36 45 54 63 72 81
10 20 30 40 50 60 70 80 90 100
Clearly, this table can be printed at least as fast as our difference table—it has
about half the entries—so it is, similarly, O(n2 ). Can this limit be improved? If
lines 3 and 4 take constant times c1 and c2 , respectively, then the overall time is
approximately
c1 n(n + 1) c1 c1
(1c1 + c2 ) + (2c1 + c2 ) + · · · + (nc1 + c2 ) = + nc2 = n2 + (c2 + )n
2 2 2
5.1 Asymptotic Analysis Tools 87
Clearly, no linear function will bound this function above, so the bound of O(n2 )
is a good estimate. Notice that we have, essentially, used the fastest growing
term of the polynomial—n2 .
Notice that both of these programs print an “area” of values, each of which
can be computed in constant time. Thus, the growth rate of the function is the
growth rate of the area of the output—which is O(n2 ).
Often, it is useful to build a Vector containing specific values. For the purposes
of this problem, we will assume the values are integers between 0 and n −
1, inclusive. Our first (and best) attempt expands the Vector in the natural
manner:
We will assume (correctly) that lines 1 and 4 take constant time. The loop at
line 2, however, takes n times the length of time it takes to add a single element.
Review of that code will demonstrate that the addition of a new element to a
Vector takes constant time, provided expansion is not necessary. Thus, the total
running time is linear, O(n). Notice that the process of building this Vector
requires space that is linear as well. Clearly, if the method’s purpose is to spend
time initializing the elements of a Vector, it would be difficult for it to consume
space at a faster rate than time.
A slightly different approach is demonstrated by the following code:
All the assumptions of buildVector1 hold here, except that the cost of inserting
a value at the beginning of a Vector is proportional to the Vector’s current
length. On the first insertion, it takes about 1 unit of time, on the second, 2
units, and so on. The analysis of this method, then, is similar to that of the
triangular multiplication table. Its running time is O(n2 ). Its space utilization,
however, remains linear.
How much space must be reserved for storing this table? This problem looks a
little daunting because the number of factors associated with each line varies,
but without any obvious pattern. Here’s a program that generates the desired
table:
public static Vector<Vector<Integer>> factTable(int n)
// pre: n > 0
// post: returns a table of factors of values 1 through n
{
Vector<Vector<Integer>> table = new Vector<Vector<Integer>>();
for (int i = 1; i <= n; i++)
{
Vector<Integer> factors = new Vector<Integer>();
for (int f = 1; f <= i; f++)
{
if ((i % f) == 0) {
factors.add(f);
}
}
table.add(factors);
}
return table;
}
To measure the table size we consider those lines that mention f as a factor.
Clearly, f appears on every f th line. Thus, over n lines of the table there are
5.1 Asymptotic Analysis Tools 89
1
1
1 1
2
1
1 1
3 1
4 1 1
5 6 7 8
0
0 1 2 3 4 5 6 7 8 9 10
P8 1
Figure 5.4 Estimating the sum of reciprocal values. Here, x=1 x
≈ 2.72 is no more
R8
than 1 + 1 x1 dx = 1 + ln 8 ≈ 3.08.
n
no more than f lines that include f . Thus, we have as an upper bound on the
table size:
n n n n n
+ + + ··· + +
1 2 3 n−1 n
Factoring out n we have:
1 1 1 1 1
n + + + ··· + +
1 2 3 n−1 n
We note that these fractions fall on the curve x1 (see Figure 5.4). We may
compute the area of the curve—an upper bound on the sum—as:
n Z n
X 1 1
n ≤ n 1+ dx
x=1
x 1 x
≤ n(1 + ln n − ln 1)
≤ O(n ln n)
The size of the table grows only a little faster than linearly. The time necessary
to create the table, of course, is O(n2 ) since we check n factors for number n.
√
Exercise 5.1 Slightly modify the method to construct the same table, but in O(n n)
time.
Exercise 5.2 Rewrite the method to construct the same table, but in O(n ln n)
time.
90 Design Fundamentals
This simple method checks each of the characters within a string. When one
is found to be a space, the loop is terminated and the index is returned. If, of
course, there is no space within the string, this must be verified by checking
each character. Clearly, the time associated with this method is determined by
the number of loops executed by the method. As a result, the time taken is
linear in the length of the string.
We can, however, be more precise about its behavior using best-, worst-, and
average-case analyses:
Best case. The best-case behavior is an upper bound on the shortest time that
any problem of size n might take. Usually, best cases are associated with
particularly nice arrangements of values—here, perhaps, a string with a
space in the first position. In this case, our method takes at most constant
time! It is important to note that the best case must be a problem of size n.
Worst case. The worst-case behavior is the longest time that any problem of
size n might take. In our string-based procedure, our method will take
the longest when there is no space in the string. In that case, the method
consumes at most linear time. Unless we specify otherwise, we will use
the worst-case consumption of resources to determine the complexity.
Average case. The average-case behavior is the complexity of solving an “av-
erage” problem of size n. Analysis involves computing a weighted sum of
the cost (in time or space) of problems of size n. The weight of each prob-
lem is the probability that the problem would occur. If, in our example,
we knew (somehow) that there was exactly one space in the string, and
that it appears in any of the n positions with equal probability, we would
deduce that, on average,
n
X 1 1 1 1 1 n(n + 1) n+1
i = · 1 + · 2 + ··· + · n = · =
i=1
n n n n n 2 2
5.1 Asymptotic Analysis Tools 91
iterations would be necessary to locate the space. Our method has linear
average-time complexity. If, however, we knew that the string was English
prose of length n, the average complexity would be related to the average
length of the first word, a value easily bounded above by a constant (say,
10). The weights of the first few terms would be large, while the weights
associated with a large number of iterations or more would be zero. The German prose
average complexity would be constant. (In this case, the worst case would may require
be constant as well.) Obviously determining the average-case complexity larger
requires some understanding of the desired distributions of data. constants.
if (false)
{
System.out.println("Man in the moon.");
} else {
System.out.println("Pie in the sky.");
}
After compiler optimizations have been employed, though, there is a limit that
can be placed on how fast the code can be made to run. We will assume—
whenever we consider a time–space trade-off—that all reasonable efforts have
been made to optimize the time and space utilization of a particular approach.
Notice, however, that most optimizations performed by a compiler do not sig-
nificantly affect the asymptotic running time of an algorithm. At most, they tend
to speed up an algorithm by a constant factor, an amount that is easily absorbed
in any theoretical analysis using big-O methods.
Appropriately implemented data structures can, however, yield significant
performance improvements. Decisions about data structure design involve weigh-
ing—often using results of big-O analysis—the time and space requirements of
a structure used to solve a problem. For example, in the Vector class, we opted
to maintain a field, elementCount, that kept track of how many elements within
the underlying array are actually being used. This variable became necessary
when we realized that as the Vector expanded, the constant reallocation of the
underlying memory could lead to quadratic time complexity over the life of the
Vector. By storing a little more information (here, elementCount) we reduce
the total complexity of expanding the Vector—our implementation, recall, re-
quires O(1) data-copying operations as the Vector expands. Since Vectors are
very likely to expand in this way, we find it worthwhile to use this extra space.
In other situations we will see that the trade-offs are less obvious and sometimes
lead to the development of several implementations of a single data structure
designed for various uses by the application designer.
The choice between implementations is sometimes difficult and may require
analysis of the application: if Vector’s add method is to be called relatively in-
frequently, the time spent resizing the structure is relatively insignificant. On the
other hand, if elements are to be added frequently, maintaining elementCount
saves time. In any case, the careful analysis of trade-off between time and space
is an important part of good data structure design.
for estimating things. It is useful, then, to keep a store of some simple figures
that may help you to determine the performance—either in time or space—of a
project. Here are some useful rules of thumb:
• An Ethernet network can transmit at 100 million bits per second (expected
throughput is nearer 10 million bits).
Exercise 5.3 How many dots can be printed on a single sheet of paper? Assume,
for example, your printer prints at 500 dots per inch. If a dot were used to represent
a bit of information, how much text could be encoded on one page?
As you gain experience designing data structures you will also develop a
sense of the commitments necessary to support a structure that takes O(n2 )
space, or an algorithm that uses O(n log n) time.
5.2 Self-Reference
One of the most elegant techniques for constructing algorithms, data structures,
and proofs is to utilize self-reference in the design. In this section we discuss ap-
plications of self-reference in programming—called recursion—and in proofs—
called proof by induction. In both cases the difficulties of solving the problem
outright are circumvented by developing a language that is rich enough to sup-
port the self-reference. The result is a compact technique for solving complex
problems.
5.2.1 Recursion
When faced with a difficult problem of computation or structure, often the best
solution can be specified in a self-referential or recursive manner. Usually, the dif-
ficulty of the problem is one of management of the resources that are to be used
by the program. Recursion helps us tackle the problem by focusing on reducing
the problem to one that is more manageable in size and then building up the
answer. Through multiple, nested, progressive applications of the algorithm, a
solution is constructed from the solutions of smaller problems.
Summing Integers
We first consider a simple, but classic, problem: suppose we are interested in
computing the sum of the numbers from 0 through n.
n
X
i = 0 + 1 + 2 + 3 + ··· + n
i=0
One approach to the problem is to write a simple loop that over n iterations
accumulates the result.
result = result + i;
}
return result;
}
The method starts by setting a partial sum to 0. If n is a value that is less than
1, then the loop will never execute. The result (0) is what we expect if n = 0. If
n is greater than 0, then the loop executes and the initial portion of the partial
sum is computed. After n − 1 loops, the sum of the first n − 1 terms is computed.
The nth iteration simply adds in n. When the loop is finished, result holds the
sum of values 1 through n. We see, then, that this method works as advertised
in the postcondition.
Suppose, now, that a second programmer is to solve the same problem. If
the programmer is particularly lazy and has access to the sum1 solution the
following code also solves the problem:
For the most trivial problem (any number less than 1), we return 0. For all other
values of n, the programmer turns to sum1 to solve the next simplest problem
(the sum of integers 0 through n − 1) and then adds n. Of course, this algorithm
works as advertised in the postcondition, because it depends on sum1 for all but
the last step, and it then adds in the correct final addend, n.
Actually, if sum2 calls any method that is able to compute the sum of numbers
0 through n−1, sum2 works correctly. But, wait! The sum of integers is precisely
what sum2 is supposed to be computing! We use this observation to derive, then,
the following self-referential method:
This code requires careful inspection (Figure 5.5). First, in the simplest or base
cases (for n < 1), sum3 returns 0. The second line is only executed when n ≥ 1.
It reduces the problem to a simpler problem—the sum of integers between 0 and
n − 1. As with all recursive programs, this requires a little work (a subtraction)
to reduce the problem to one that is closer to the base case. Considering the
problem n + 1 would have been fatal because it doesn’t make suitable progress
96 Design Fundamentals
Compute sum3(100):
1. Compute sum3(99)
2. Add in 100 Progress
Work 3. Return 1+..+98
+99+100
Compute sum3(99):
1. Compute sum3(98)
2. Add in 99
3. Return 1+...+98+99 Base case
Compute sum3(98):
1. Compute sum3(97)
2. Add in 98
3. Return 1+...+98
Compute sum3(0):
Trivially return 0
toward the base case. The subproblem is passed off to another invocation of
sum3. Once that procedure computes its result (either immediately or, if nec-
essary, through further recursion), a little more work is necessary to convert
the solution of the problem of size n − 1 into a solution for a problem of size
n. Here, we have simply added in n. Notice the operation involved in build-
ing the answer (addition) opposes the operation used to reduce the problem
N
(subtraction). This is common in recursive procedures.
NW
NE
W
SE
Note that the base case is identified through the need to apply a trivial operation
rather than, say, the size of the index. Indeed, progress is determined by how
close the index gets to the size of the Vector. Again, this is a linear or O(n)
process.
In the previous example, the recursive routine was suitable for direct use by
the user. Often, though, recursion demands additional parameters that encode,
in some way, progress made toward the solution. These parameters can be
confusing to users who, after all, are probably unaware of the details of the
recursion. To avoid this confusion, we “wrap” the call to a protected recursive
method in a public method. This hides the details of the initial recursive method
call. Here, we investigate a printing extension to the Vector class:
The print method wraps or hides the call to the recursive printFrom method.
The recursive method accepts a single parameter that indicates the index of
the first element that should be printed out. As progress is made, the initial
98 Design Fundamentals
index increases, leading to linear performance. To print the entire Vector, the
recursive method is called with a value of zero.
It would appear that the base case is missing. In fact, it is indicated by the
failure of the if statement. Even though the base case is to “do nothing,” the if
statement is absolutely necessary. Every terminating recursive method should
have some conditional statement.
PrintFrom is an example of a tail recursive method. Any recursion happens
just before exiting from the method. Tail recursive methods are particularly nice
because good compilers can translate them into loops. Each iteration of the loop
simulates the computation and return of another of the nested recursive proce-
dure calls. Since there is one call for each of the n values, and the procedure
performs a constant amount of work, the entire process takes O(n) time.
Exercise 5.4 Write a recursive method to print out the characters of a string with
spaces between characters. Make sure your method does not print a leading or
tailing space, unless it is a leading or trailing character of the original string.
For the nontrivial cases, the variable minStamps keeps track of the minimum
number of stamps returned by any of these three subproblems. Since each
method call potentially results in several recursive calls, the method is not tail
recursive. While it is possible to solve this problem using iteration, recursion
presents a very natural solution.
When we call the method for the first time, we allocate an array of sufficient
size (amount+1 because arrays are indexed beginning at zero) and pass it as
answer in the protected two-parameter version of the method. If the answer
is not found in the array, it is computed using up to three recursive calls that
pass the array of previously computed answers. Just before returning, the newly
computed answer is placed in the appropriate slot. In this way, when solutions
are sought for this problem again, they can be retrieved without the overhead
of redundant computation.
When we seek the solution to the 70 cent problem, 146 calls are made to the
procedure. Only a few of these get past the first few statements to potentially
make recursive calls. The combination of the power recursion and the efficiency
of dynamic programming yields elegant solutions to many seemingly difficult
5.2 Self-Reference 101
problems.
Exercise 5.5 Explain why the dynamic programming approach to the problem
runs in linear time.
Proof: We prove this by induction. First, consider the simplest case, or base case.
If n = 0, then the sum is 0. The formula gives us 0(0+1)
2 = 0. The observation
appears to hold for the base case.
Now, suppose we know—for some reason—that our closed-form formula
holds for all values between 0 (our base case) and n − 1. This knowledge may
102 Design Fundamentals
help us solve a more complex problem, namely, the sum of integers between 0
and n. The sum
0 + 1 + 2 + · · · + (n − 1) + n
conveniently contains the sum of the first n − 1 integers, so we rewrite it as
[0 + 1 + 2 + · · · + (n − 1)] + n
Because we have assumed that the sum of the natural numbers to n − 1 can be
computed by the formula, we may rewrite the sum as
(n − 1)n
+n
2
(n − 1)n + 2n n(n + 1)
=
2 2
Thus given only the knowledge that the formula worked for n − 1, we have
been able to extend it to n. It is not hard to convince yourself, then, that the
observation holds for any nonnegative value of n. Our base case was for n = 0,
so it must hold as well for n = 1. Since it holds for n = 1, it must hold for
n = 2. In fact, it holds for any value of n ≥ 0 by simply proving it holds for
values 0, 1, 2, . . . , n − 1 and then observing it can be extended to n.
The induction can be viewed as a recursively constructed proof (consider
Figure 5.6). Suppose we wish to see if our observation holds for n = 100. Our
99 cases left to method requires us to show it holds for n = 99. Given that, it is a simple matter
prove! Take one to extend the result to 100. Proving the result for n = 99, however, is almost2
down, pass it as difficult as it is for n = 100. We need to prove it for n = 98, and extend
around, 98 that result. This process of developing the proof for 100 eventually unravels
cases left to into a recursive construction of a (very long) proof that demonstrates that the
prove! . . .
observation holds for values 0 through 99, and then 100.
The whole process, like recursion, depends critically on the proof of appro-
priate base cases. In our proof of Observation 5.1, for example, we proved that
the observation held for n = 0. If we do not prove this simple case, then our
recursive construction of the proof for any value of n ≥ 0 does not terminate:
when we try to prove it holds for n = 0, we have no base case, and therefore
must prove it holds for n = −1, and in proving that, we prove that it holds for
−2, −3, . . . , ad infinitum. The proof construction never terminates!
Our next example of proof by induction is a correctness proof . Our intent is
to show that a piece of code runs as advertised. In this case, we reinvestigate
sum3 from page 95:
2 It is important, of course, to base your inductive step on simpler problems—problems that take
Recursion you closer to your base case. If you avoid basing it on simpler cases, then the recursive proof will
never be completely constructed, and the induction will fail.
5.2 Self-Reference 103
Figure 5.6 The process of proof by induction simulates the recursive construction of a
proof. Compare with Figure 5.5.
(The code has been reformatted to allow discussion of portions of the computa-
tion.) As with our mathematical proofs, we state our result formally:
Observation 5.2 Given that n ≥ 0, the method sum3 computes the sum of the
integers 0 through n, inclusive.
Proof: Our proof is by induction, based on the parameter n. First, consider the
action of sum3 when it is passed the parameter 0. The if statement of line 1 is
true, and the program returns 0, the desired result.
We now consider n>0 and assume that the method computes the correct
result for all values less that n. We extend our proof of correctness to the pa-
rameter value of n. Since n is greater than 0, the if of line 1 fails, and the else
beginning on line 2 is considered. On line 4, the parameter is decremented,
and on line 3, the recursion takes place. By our assumption, this recursive
104 Design Fundamentals
1111111111
0000000000
0000000000
1111111111
0000000000
1111111111
n-1 others
0000000000
1111111111
0000000000
1111111111
Alice
0000000000
1111111111
0000000000
1111111111
Figure 5.7 A group of n computer scientists composed of Alice and n − 1 others.
call returns the correct result—the sum of values between 0 and n-1, inclusive.
Line 5 adds in the final value, and the entire result is returned. The program
works correctly for a parameter n greater than 0. By induction on n, the method
computes the correct result for all n>=0.
Proofs of correctness are important steps in the process of verifying that code
works as desired. Clearly, since induction and recursion have similar forms, the
application of inductive proof techniques to recursive methods often leads to
straightforward proofs. Even when iteration is used, however, induction can be
used to demonstrate assumptions made about loops, no matter the number of
iterations.
We state here an important result that gives us a closed-form expression for
computing the sum of powers of 2.
Pn
Observation 5.3 i=0 2i = 2n+1 − 1.
There are, of course, ways that the inductive proof can go awry. Not proving
the appropriate base cases is the most common mistake and can lead to some
interesting results. Here we prove what few have suspected all along:
Warning: bad Proof: We prove the observation is true, using mathematical induction. First,
proof! we use traditional techniques (examinations, etc.) to demonstrate that Alice is
a good programmer.
Now, assume that our observation is true of any group of fewer than n com-
puter scientists. Let’s extend our result: select n computer scientists, including
Alice (see Figure 5.7). Clearly, the subgroup consisting of all computer scien-
tists that are “not Alice” is a group of n − 1 computer scientists. Our assumption
states that this group of n − 1 computer scientists is made up of good program-
mers. So Alice and all the other computer scientists are good programmers.
By induction on n, we have demonstrated that all computer scientists are good
programmers.
5.2 Self-Reference 105
1111111111111
0000000000000
0000
1111
0000000000000
1111111111111
Alice
0000
1111 0000
1111
0000000000000
1111111111111
0000
1111 0000
1111
0000000000000
1111111111111
00000
11111 0000
1111
0000000000000
1111111111111
00000
11111
Carol
00000 1111
0000
0000000000000
1111111111111
11111
0000000000000
1111111111111
0000000000000
1111111111111
Bob
Figure 5.8 A group of n computer scientists, including Alice, Bob, and Carol.
This is a very interesting result, especially since it is not true. (Among other
things, some computer scientists do not program computers!) How, then, were
we successful in proving it? If you look carefully, our base case is Alice. The
assumption, on the other hand, is based on any group of n − 1 programmers.
Unfortunately, since our only solid proof of quality programming is Alice, and
non-Alice programmers cannot be reduced to cases involving Alice, our proof is
fatally flawed.
Still, a slight reworking of the logic might make the proof of this observa-
tion possible. Since Alice is a computer scientist, we can attempt to prove the
observation by induction on groups of computer scientists that include Alice:
Proof: We prove the observation by induction. First, as our base case, consider Warning: bad
Alice. Alice is well known for being a good programmer. Now, assume that for proof, take 2!
any group of fewer than n computer scientists that includes Alice, the members
are excellent programmers. Take n computer scientists, including Alice (see
Figure 5.8). Select a non-Alice programmer. Call him Bob. If we consider all
non-Bob computer scientists, we have a group of n − 1 computer scientists—
including Alice. By our assumption, they must all be good. What about Bob?
Select another non-Alice, non-Bob computer scientist from the group of n. Call
her Carol. Carol must be a good programmer, because she was a member of the
n − 1 non-Bob programmers. If we consider the n − 1 non-Carol programmers,
the group includes both Alice and Bob. Because it includes Alice, the non-
Carol programmers must all be good. Since Carol is a good programmer, then
all n must program well. By induction on n, all groups of computer scientists
that include Alice must be good programmers. Since the group of all computer
scientists is finite, and it includes Alice, the entire population must program
well. The observation holds!
This proof looks pretty solid—until you consider that in order for it to work,
you must be able to distinguish between Alice, Bob, and Carol. There are three
people. The proof of the three-person case depends directly on the observation
holding for just two people. But we have not considered the two-person case!
In fact, that is the hole in the argument. If we know of a bad programmer, Ted,
we can say nothing about the group consisting of Alice and Ted (see Figure 5.9).
106 Design Fundamentals
Ted
Alice
Figure 5.9 The proof does not hold for the simplest nontrivial case: Alice and any bad
programmer.
0, 1, 1, 2, 3, 5, 8, 13, 21, . . .
These values are the first of the sequence of Fibonacci numbers. Each value is
the sum of the two values that fall before it. We should be careful—especially
given our last discussion—that we have the base cases carefully considered. In
this particular case, we must specify two initial values: 0 and 1.
This sequence may be familiar to you. If it is, you may have seen the defini-
tion of Fn , the nth value of the sequence as
n n = 0 or n = 1
Fn =
Fn−2 + Fn−1 n > 1
{
Assert.pre(n >= 0, "Index is nonnegative.");
// when n < 2, return n
if (n == 0) return 0; // line 1
else if (n == 1) return 1; // line 2
// complex, self-referential case:
else return fibo(n-2)+fibo(n-1); // line 3
}
We now seek to prove that the recursive method computes and returns the nth
member of the sequence.
Proof: First, suppose n = 0: the method returns 0, on line 1. Next, suppose
that n = 1: the method returns 1, on line 2. So, for the two very simplest
cases, the method computes the correct values. Now, suppose that n > 1, and
furthermore, assume that fibo returns the correct value for all terms with index
less than n. Since n > 1, lines 1 and 2 have no effect. Instead, the method
resorts to using line 3 to compute the value. Since the method works for all
values less than n, it specifically computes the two previous terms—Fn−2 and
Fn−1 —correctly. The sum of these two values (Fn ) is therefore computed and
immediately returned on line 3. We have, then, by mathematical induction on
n proved that f ibo(n) computes Fn for all n ≥ 0.
Another approach to computing Fibonacci numbers, of course, would be to
use an iterative method:
static public int fibo2(int n)
// pre: n is a nonnegative integer
// post: result is the ith term from the sequence
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
{
Assert.pre(n >= 0, "Index is nonnegative.");
int a = 0;
int b = 1;
if (n == 0) return a; // line 1
if (n == 1) return b; // line 2
// for large values of n, iteratively compute sequence
int i=2,F;
do
{
// Assertion: b is the i-1st member of the sequence
// a is the i-2nd member
F = a + b; // line 3
// Assertion: F is the ith member
// update previous two values:
a = b; // line 4
b = F; // line 5
i++; // line 6
} while (i <= n); // line 7
return F; // line 8
}
108 Design Fundamentals
5.3.1 Symmetry
For the most part, our instruction of computers occurs through programs. As
a result, programs can be nonintuitive and hard to understand if they are not
designed with human-readability in mind. On the other hand, a well-designed
program can be used by a novice without a significant learning curve. Systems
that are easy to use tend to survive longer.
The programmer, as a designer of a data structure, is responsible for deliv-
ering a usable implementation of an abstract data structure. For an implemen-
tation to be usable, it should provide access to the structure with methods that
are predictable and easy to use. The notion of predictability is particularly dif-
ficult for designers of data structures to understand, and it is something often
overlooked by novice programmers.
When designing a system (here, a program or data structure) a useful princi-
ple is to make its interface symmetric. What is symmetry? Symmetry allows one
5.3 Properties of Design 109
to view a system from different points of view and see similarities. Mathemati-
cians would say that a system exhibits a symmetry if “it looks like itself under
a nontrivial transformation.” Given this, programmers consider asymmetries in
transformed programs to be early warning signs of errors in logic.
Consider the following method (you will see this as part of the swap proce-
dure of page 120). It exchanges two object references—data[i] and data[j].
int temp;
temp = data[i];
data[i] = data[j];
data[j] = temp;
Close inspection of this code demonstrates that it does what it claims to do.
Even if we stand back, not thinking so much about the actual workings of the
code, we can see that the code is pretty symmetric. For example, if we squint
our eyes and look at the code from the standpoint of variable data[i], we see
it as:
... = data[i];
data[i] = ...;
While this is not direct proof that the code works, it is an indication that the
code is, in some way, “symmetric,” and that helps make the argument that it is
well designed.
Not everything we do is symmetric. If we consider the Association class,
for example, the key and value components of the Association are different.
The value, of course, has two associated methods, getValue and setValue.
The first of the methods reads and returns a value, while the second method
consumes and sets a value. Everything is in balance, and so we are hopeful that
the design of the structure is correct. On the other hand, the key can only be
read: while there is a getKey method, there is no setKey. We have suggested
good reasons for doing this. As long as you can make a good argument for
asymmetry in design, the breaking of symmetry can be useful. Unreasoned
asymmetry, however, is a sign of poor and unpredictable design.
Here are various ways that one can look at a system to evaluate it for sym-
metry:
1. Compare methods that extend the structure with methods that trim the
structure. Do they have similar approaches? Are they similar in number?
2. Consider methods that read and write values. Can the input methods read
what is written by the output methods? Can the writing methods write all
values that can be read?
110 Design Fundamentals
When asymmetries are found, it is important to consider why they occur. Argu-
ments such as “I can’t imagine that anyone would need an opposite method!”
are usually unconvincing. Many methods are added to the structures, not be-
cause they are obviously necessary, but because there is no good argument
against them. Sometimes, of course, the language or underlying system forces
an asymmetry. In Java, for example, every Object has a toString method that
converts an internal representation of an object to a human-readable form, but
there’s no fromString required method that reads the value of an Object from
Should 6= will. a String. There should be, but there isn’t.
5.3.2 Friction
One of the obvious benefits of a data structure is that it provides a means of
storing information. The ease with which the structure accepts and provides in-
formation about its contents can often be determined by its interface. Likewise,
the difficulty of moving a data structure from one state to another determines,
in some way, its “stiffness” or the amount of friction the structure provides when
the state of the structure is to be modified.
One way that we might measure friction is to determine a sequence of logical
states for the structure, and then determine the number of operations that are
necessary to move the structure from each state to the next. If the number
of operations is high, we imagine a certain degree of friction; if the operation
count is low, the structure moves forward with relative ease.
Often we see that the less space provided to the structure, the more friction
appears to be inherent in its structure. This friction can be good—it may make
it less possible to get our structure into states that are inconsistent with the
definition of the structure, or it may be bad—it may make it difficult to get
something done.
5.4 Conclusions
Several formal concepts play an important role in modern data structure des-
ign—the use of big-O analysis to support claims of efficiency, the use of recur-
sion to develop concise but powerful structures, and the use of induction to
prove statements made about both data structures and algorithms. Mastery of
these concepts improves one’s approach to solving problems of data structure
design.
5.4 Conclusions 111
Problems
Solutions to the odd-numbered problems begin on page 462.
5.1 What is the time complexity associated with accessing a single value in
an array? The Vector class is clearly more complex than the array. What is the
time complexity of accessing an element with the get method?
5.2 What is the worst-case time complexity of the index-based remove code
in the Vector class? What is the best-case time complexity? (You may assume
the Vector does not get resized during this operation.)
5.3 What is the running time of the following method?
public static int reduce(int n)
{
int result = 0;
while (n > 1)
{
n = n/2;
result = result+1;
}
return result;
}
What is a lower bound on the time it takes to remove a value from a Vector by
index?
5.7 What is a lower bound on adding a value to the end of a Vector? Does
it matter that sometimes we may have to spend time doubling the size of the
underlying array?
5.8 When discussing symmetry, we investigated a procedure that swapped
two values within an array. Is it possible to write a routine that swaps two
integer values? If so, provide the code; if not, indicate why.
5.9 For subtle reasons String objects cannot be modified. Instead, Strings
are used as parameters to functions that build new Strings. Suppose that a is
an n-character String. What is the time complexity of performing a=a+"!"?
5.10 Read Problem 5.9. Suppose that a and b are n-character Strings. What
is the complexity of performing a=a+b?
5.11 What is the rate of growth (using big-O analysis) of the function f (n) =
n + log n? Justify your answer.
5.12 In this text, logarithms are assumed to be in base 2. Does it make a
difference, from a complexity viewpoint?
1
5.13 What is the rate of growth of the function n + 12? Justify your answer.
sin n
5.14 What is the rate of growth of the function n ? Justify your answer.
5.15 Trick question: What is the rate of growth of tan n?
5.16 Suppose n integers between 1 and 366 are presented as input, and you
want to know if there are any duplicates. How would you solve this problem?
What is the rate of growth of the function T (n), describing the time it takes for
you to determine if there are duplicates? (Hint: Pick an appropriate n0 .)
5.17 The first element of a Syracuse sequence is a positive integer s0 . The
value si (for i > 0) is defined to be si−1 /2 if si−1 is even, or 3si−1 + 1 if si−1
is odd. The sequence is finished when a 1 is encountered. Write a procedure to
print the Syracuse sequence for any integer s0 . (It is not immediately obvious
that this method should always terminate.)
5.18 Rewrite the sqrt function of Section 2.1 as a recursive procedure.
5.19 Write a recursive procedure to draw a line segment between (x0 , y0 )
and (x1 , y1 ) on a screen of pixels with integer coordinates. (Hint: The pixel
closest to the midpoint is not far off the line segment.)
5.20 Rewrite the reduce method of Problem 5.3 as a recursive method.
5.21 One day you notice that integer multiplication no longer works. Write
a recursive procedure to multiply two values a and b using only addition. What
is the complexity of this function?
5.22 Modify the “stamp change” problem of Section 5.2.1 to report the num-
ber of each type of stamp to be found in the minimum stamp change.
5.23 Prove that 5n − 4n − 1 is divisible by 16 for all n ≥ 0.
Pn
5.24 Prove Observation 5.3, that i=0 2i = 2n+1 − 1 for n ≥ 0.
114 Design Fundamentals
• Different runs of the experiment can generate different times. This vari-
ation is unlikely to be due to significant differences in the speed of the
operation, but instead to various interruptions that regularly occur when
a program is running. Instead of computing the average of the running
times, it is best to compute the minimum of the experiment’s elapsed
times. It’s unlikely that this is much of an underestimate!
• Never perform input or output while you are timing an experiment. These
operations are very expensive and variable. When reading or writing,
make sure these operations appear before or after the experiment being
timed.
• The process of repeating an operation takes time. One of our tasks will be
to measure the time it takes to execute an empty for loop. The loop, of
course, is not really empty: it performs a test at the top of the loop and an
increment at the bottom. Failing to account for the overhead of a for loop
makes it impossible to measure any operation that is significantly faster.
can assign a value of 0 much faster than the assignment of a value of 42.
If an experiment yields an unexpectedly short operation time, change the
Java to obscure any easy optimizations that may be performed. Don’t
forget to subtract the overhead of these obscuring operations!
Keeping a mindful eye on your experimental data will allow you to effectively
measure very, very short events accurate to nanoseconds. In one nanosecond,
light travels 11.80 inches!
Procedure. The ultimate goal of this experiment is a formally written lab report
presenting your results. Carefully design your experiment, and be prepared to
defend your approach. The data you collect here is experimental, and necessar-
ily involves error. To reduce the errors described above, perform multiple runs
of each experiment, and carefully document your findings. Your report should
include results from the following experiments:
1. A description of the machine you are using. Make sure you use this ma-
chine for all of your experiments.
2. Write a short program to measure the time that elapses, say, when an
empty for loop counts to one million. Print out the elapsed time, as well
as the per-iteration elapsed time. Adjust the number of loops so that the
total elapsed time falls between, say, one-hundredth and one-tenth of a
second.
Recall that we can measure times in nanoseconds (as accurately as possi-
ble, given your machine) using System.nanoTime():
int i, loops;
double speed;
loops = 10000000;
long start,stop,duration;
start = System.nanoTime();
for (i = 0; i < loops; i++)
{
// code to be timed goes here
}
stop = System.nanoTime();
duration = stop-start;
System.out.println("# Elapsed time: "+duration+"ns");
System.out.println("# Mean time: "+
(((double)duration)/loops)+
"nanoseconds");
Notes:
Chapter 6
Sorting
1 We focus on arrays of integers to maintain a simple approach. These techniques, of course, can
be applied to vectors of objects, provided that some relative comparison can be made between two
elements. This is discussed in Section 6.7.
120 Sorting
40 2 1 43 3 65 0 −1 58 3 42 4
0 1 2 3 4 5 6 7 8 9 10 11
(a) Unordered
−1 0 1 2 3 3 4 40 42 43 58 65
0 1 2 3 4 5 6 7 8 9 10 11
(b) Sorted
Figure 6.1 The relations between entries in unordered and sorted arrays of integers.
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
After a single pass the largest value will end up “bubbling” up to the high-
indexed side of the array. The next pass will, at least, bubble up the next largest
value, and so forth. The sort—called bubble sort—must be finished after n − 1
passes. Here is how we might write bubble sort in Java:
Observe that the only potentially time-consuming operations that occur in this
sort are comparisons and exchanges. While the cost of comparing integers is rel-
6.1 Approaching the Problem 121
Bubble
40 2 1 43 3 65 0 −1 58 3 42 4
2 1 40 3 43 0 −1 58 3 42 4 65
1 2 3 40 0 −1 43 3 42 4 58 65
1 2 3 0 −1 40 3 42 4 43 58 65
1 2 0 −1 3 3 40 4 42 43 58 65
1 0 −1 2 3 3 4 40 42 43 58 65
0 −1 1 2 3 3 4 40 42 43 58 65
−1 0 1 2 3 3 4 40 42 43 58 65
Detectable finish
−1 0 1 2 3 3 4 40 42 43 58 65
−1 0 1 2 3 3 4 40 42 43 58 65
−1 0 1 2 3 3 4 40 42 43 58 65
−1 0 1 2 3 3 4 40 42 43 58 65
Figure 6.2 The passes of bubble sort: hops indicate “bubbling up” of large values.
Shaded values are in sorted order. A pass with no exchanges indicates sorted data.
122 Sorting
atively small, if each element of the array were to contain a long string (for ex-
ample, a DNA sequence) or a complex object (for example, a Library of Congress
entry), then the comparison of two values might be a computationally intensive
operation. Similarly, the cost of performing an exchange is to be avoided.2 We
can, therefore, restrict our attention to the number of comparison and exchange
operations that occur in sorts in order to adequately evaluate their performance.
In bubble sort each pass of the bubbling phase performs n − 1 comparisons
and as many as n − 1 exchanges. Thus the worst-case cost of performing bubble
sort is O((n−1)2 ) or O(n2 ) operations. In the best case, none of the comparisons
leads to an exchange. Even then, though, the algorithm has quadratic behavior.3
Most of us are inefficient sorters. Anyone having to sort a deck of cards or a
stack of checks is familiar with the feeling that there must be a better way to do
this. As we shall see, there probably is: most common sorting techniques used in
day-to-day life run in O(n2 ) time, whereas the best single processor comparison-
based sorting techniques are expected to run in only O(n log n) time. (If multi-
ple processors are used, we can reduce this to O(log n) time, but that algorithm
is beyond the scope of this text.) We shall investigate two sorting techniques
that run in O(n2 ) time, on average, and two that run in O(n log n) time. In the
end we will attempt to understand what makes the successful sorts successful.
Our first two sorting techniques are based on natural analogies.
time on data that were already sorted. Still, the average case would be quadratic.
6.2 Selection Sort 123
max = 0;
for (index = 1; index < numUnsorted; index++)
{
if (data[max] < data[index]) max = index;
}
(Notice that the maximum is not updated unless a larger value is found.) Now,
consider where this maximum value would be found if the data were sorted:
it should be clear to the right, in the highest indexed location. This is easily
accomplished: we simply swap the last element of the unordered array with the
maximum. Once this swap is completed, we know that at least that one value is
in the correct location, and we logically reduce the size of the problem by one.
If we remove the n − 1 largest values in successive passes (see Figure 6.3), we
have selection sort. Here is how the entire method appears in Java:
Selection sort potentially performs far fewer exchanges than bubble sort: se-
lection sort performs exactly one per pass, while bubble sort performs as many
as n − 1. Like bubble sort, however, selection sort demands O(n2 ) time for
comparisons.
Interestingly, the performance of selection sort is independent of the order
of the data: if the data are already sorted, it takes selection sort just as long to
sort as if the data were unsorted. We can improve on this behavior through a
slightly different analogy.
124 Sorting
40 2 1 43 3 4 0 −1 58 3 42 65
40 2 1 43 3 4 0 −1 42 3 58 65
40 2 1 3 3 4 0 −1 42 43 58 65
40 2 1 3 3 4 0 −1 42 43 58 65
−1 2 1 3 3 4 0 40 42 43 58 65
−1 2 1 3 3 0 4 40 42 43 58 65
−1 2 1 0 3 3 4 40 42 43 58 65
−1 2 1 0 3 3 4 40 42 43 58 65
−1 0 1 2 3 3 4 40 42 43 58 65
−1 0 1 2 3 3 4 40 42 43 58 65
−1 0 1 2 3 3 4 40 42 43 58 65
Figure 6.3 Profile of the passes of selection sort: shaded values are sorted. Circled
values are maximum among unsorted values and are moved to the low end of sorted
values on each pass.
6.3 Insertion Sort 125
Insert
40 2 1 43 3 65 0 −1 58 3 42 4
2 40 1 43 3 65 0 −1 58 3 42 4
1 2 40 43 3 65 0 −1 58 3 42 4
1 2 40 43 3 65 0 −1 58 3 42 4
1 2 3 40 43 65 0 −1 58 3 42 4
1 2 3 40 43 65 0 −1 58 3 42 4
0 1 2 3 40 43 65 −1 58 3 42 4
−1 0 1 2 3 40 43 65 58 3 42 4
−1 0 1 2 3 40 43 58 65 3 42 4
−1 0 1 2 3 3 40 43 58 65 42 4
−1 0 1 2 3 3 40 42 43 58 65 4
−1 0 1 2 3 3 4 40 42 43 58 65
Figure 6.4 Profile of the passes of insertion sort: shaded values form a “hand” of sorted
values. Circled values are successively inserted into the hand.
6.4 Mergesort 127
is executed exactly once for each of n − 1 passes. The best-case running time
performance of the sort is therefore dominated by O(n) comparisons (there are
no movements of data within the array). Because of this characteristic, insertion
sort is often used when data are very nearly ordered (imagine sorting a phone
book after a month of new customers has been appended).
In contrast, if the array was previously in reverse order, the value must be
compared with every sorted value to find the correct location. As the compar-
isons are made, the larger values are moved to the right to make room for the
new value. The result is that each of O(n2 ) compares leads to a data movement,
and the worst-case running time of the algorithm is O(n2 ).
Note that each of these sorts uses a linear number of data cells. Not every
sorting technique is able to live within this constraint.
6.4 Mergesort
Suppose that two friends are to sort an array of values. One approach might be
to divide the deck in half. Each person then sorts one of two half-decks. The
sorted deck is then easily constructed by combining the two sorted half-decks.
This careful interleaving of sorted values is called a merge.
It is straightforward to see that a merge takes at least O(n) time, because
every value has to be moved into the destination deck. Still, within n − 1 com-
parisons, the merge must be finished. Since each of the n − 1 comparisons
(and potential movements of data) takes at most constant time, the merge is no
worse than linear.
There are, of course, some tricky aspects to the merge operation—for exam-
ple, it is possible that all the cards in one half-deck are smaller than all the cards
in the other. Still, the performance of the following merge code is O(n):
This code is fairly general, but a little tricky to understand (see Figure 6.5). We
assume that the data from the two lists are located in the two arrays—in the
lower half of the range in temp and in the upper half of the range in data (see
Figure 6.5a). The first loop compares the first remaining element of each list to
determine which should be copied over to the result list first (Figure 6.5b). That
loop continues until one list is emptied (Figure 6.5c). If data is the emptied list,
the remainder of the temp list is transferred (Figure 6.5d). If the temp list was
emptied, the remainder of the data list is already located in the correct place!
Returning to our two friends, we note that before the two lists are merged
each of the two friends is faced with sorting half the cards. How should this be
done? If a deck contains fewer than two cards, it’s already sorted. Otherwise,
each person could recursively hand off half of his or her respective deck (now
one-fourth of the entire deck) to a new individual. Once these small sorts are
finished, the quarter decks are merged, finishing the sort of the half decks, and
the two half decks are merged to construct a completely sorted deck. Thus,
we might consider a new sort, called mergesort, that recursively splits, sorts,
and reconstructs, through merging, a deck of cards. The logical “phases” of
mergesort are depicted in Figure 6.6.
private static void mergeSortRecursive(int data[],
int temp[],
int low, int high)
// pre: 0 <= low <= high < data.length
// post: values in data[low..high] are in ascending order
{
int n = high-low+1;
int middle = low + n/2;
int i;
if (n < 2) return;
// move lower half of data into temporary storage
for (i = low; i < middle; i++)
{
temp[i] = data[i];
}
// sort lower half of array
mergeSortRecursive(temp,data,low,middle-1);
// sort upper half of array
mergeSortRecursive(data,temp,middle,high);
// merge halves together
merge(data,temp,low,middle,high);
}
6.4 Mergesort 129
data −1 0 3 4 42 58
(a) 0 1 2 3 4 5 6 7 8 9 10 11 12 13
temp 1 2 3 40 43 65
di 6 ti 0 ri 0
data −1 0 1 2 3 3 4 42 58
(b) 0 1 2 3 4 5 6 7 8 9 10 11 12 13
temp 40 43 65
di 8 ti 3 ri 5
data −1 0 1 2 3 3 4 40 42 43 58
(c) 0 1 2 3 4 5 6 7 8 9 10 11 12 13
temp 65
di 12 ti 5 ri 11
data −1 0 1 2 3 3 4 40 42 43 58 65
(d) 0 1 2 3 4 5 6 7 8 9 10 11 12 13
temp
di 12 ti 6 ri 12
Figure 6.5 Four stages of a merge of two six element lists (shaded entries are partic-
ipating values): (a) the initial location of data; (b) the merge of several values; (c) the
point at which a list is emptied; and (d) the final result.
130 Sorting
40 2 1 43 3 65 0 −1 58 3 42 4 Split
40 2 1 43 3 65 0 −1 58 3 42 4
40 2 1 43 3 65 0 −1 58 3 42 4
40 2 1 43 3 65 0 −1 58 3 42 4
2 1 3 65 −1 58 42 4
Merge
40 1 2 43 3 65 0 −1 58 3 4 42
1 2 40 3 43 65 −1 0 58 3 4 42
1 2 3 40 43 65 −1 0 3 4 42 58
−1 0 1 2 3 3 4 40 42 43 58 65
Figure 6.6 Profile of mergesort: values are recursively split into unsorted lists that are
then recursively merged into ascending order.
Note that this sort requires a temporary array to perform the merging. This
temporary array is only used by a single merge at a time, so it is allocated once
and garbage collected after the sort. We hide this detail with a public wrapper
procedure that allocates the array and calls the recursive sort:
Clearly, the depth of the splitting is determined by the number of times that n
can be divided in two and still have a value of 1 or greater: log2 n. At each
level of splitting, every value must be merged into its respective subarray. It
follows that at each logical level, there are O(n) compares over all the merges.
Since there are log2 n levels, we have O(n · log n) units of work in performing a
mergesort.
Mergesort is a common technique for sorting large sets of data that do not
fit completely in fast memory. Instead, the data are saved in temporary files that
are merged together. When the recursion splits the collection into subsets of a
manageable size, they can be sorted using other techniques, if desired.
6.5 Quicksort 131
6.5 Quicksort
Since the process of sorting numbers consists of moving each value to its ul-
timate location in the sorted array, we might make some progress toward a
solution if we could move a single value to its ultimate location. This idea forms
the basis of a fast sorting technique called quicksort.
One way to find the correct location of, say, the leftmost value—called a
pivot—in an unsorted array is to rearrange the values so that all the smaller
values appear to the left of the pivot, and all the larger values appear to the
right. One method of partitioning the data is shown here. It returns the final
location for what was originally the leftmost value:
The indices left and right start at the two ends of the array (see Figure 6.7)
and move toward each other until they coincide. The pivot value, being leftmost
in the array, is indexed by left. Everything to the left of left is smaller than the
pivot, while everything to the right of right is larger. Each step of the main loop
compares the left and right values and, if they’re out of order, exchanges them.
Every time an exchange occurs the index (left or right) that references the
pivot value is alternated. In any case, the nonpivot variable is moved toward
the other. Since, at each step, left and right move one step closer to each
other, within n steps, left and right are equal, and they point to the current
location of the pivot value. Since only smaller values are to the left of the pivot,
and larger values are to the right, the pivot must be located in its final location.
Values correctly located are shaded in Figure 6.8.
132 Sorting
40 2 1 43 3 65 0 −1 58 3 42 4
left right
4 2 1 43 3 65 0 −1 58 3 42 40
4 2 1 40 3 65 0 −1 58 3 42 43
4 2 1 3 3 65 0 −1 58 40 42 43
4 2 1 3 3 40 0 −1 58 65 42 43
4 2 1 3 3 −1 0 40 58 65 42 43
4 2 1 3 3 −1 0 40 58 65 42 43
left right
Figure 6.7 The partitioning of an array’s values based on the (shaded) pivot value 40.
Snapshots depict the state of the data after the if statements of the partition method.
6.5 Quicksort 133
40 2 1 43 3 65 0 −1 58 3 42 4
partition
4 2 1 3 3 −1 0 40 58 65 42 43
0 2 1 3 3 −1 4 43 42 58 65
−1 0 1 3 3 2 42 43 65
−1 1 3 3 2 42
2 3 3
2 3
−1 0 1 2 3 3 4 40 42 43 58 65
Figure 6.8 Profile of quicksort: leftmost value (the circled pivot) is used to position
value in final location (indicated by shaded) and partition array into relatively smaller
and larger values. Recursive application of partitioning leads to quicksort.
Because the pivot segregates the larger and smaller values, we know that
none of these values will appear on the opposite side of the pivot in the final
arrangement. This suggests that we can reduce the sorting of a problem of size
n to two problems of size approximately n2 . To finish the sort, we need only
recursively sort the values to the left and right of the pivot:
In practice, of course, the splitting of the values is not always optimal (see the
placement of the value 4 in Figure 6.8), but a careful analysis suggests that even
with these “tough breaks” quicksort takes only O(n log n) time.
When either sorted or reverse-sorted data are to be sorted by quicksort, the
results are disappointing. This is because the pivot value selected (here, the
leftmost value) finds its ultimate location at one end of the array or the other.
This reduces the sort of n values to n − 1 values (and not n/2), and the sort
requires O(n) passes of an O(n) step partition. The result is an O(n2 ) sort.
Since nearly sorted data are fairly common, this result is to be avoided.
Notice that picking the leftmost value is not special. If, instead, we attempt
to find the correct location for the middle value, then other arrangements of
data will cause the degenerate behavior. In short, for any specific or determin-
istic partitioning technique, a degenerate arrangement exists. The key to more
consistent performance, then, is a nondeterministic partitioning that correctly
places a value selected at random (see Problem 6.15). There is, of course, a
very unlikely chance that the data are in order and the positions selected in-
duce a degenerate behavior, but that chance is small and successive runs of
the sorting algorithm on the same data are exceedingly unlikely to exhibit the
same behavior. So, although the worst-case behavior is still O(n2 ), its expected
behavior is O(n log n).
Quicksort is an excellent sort when data are to be sorted with little extra
space. Because the speed of partitioning depends on the random access nature
of arrays or Vectors, quicksort is not suitable when not used with random access
structures. In these cases, however, other fast sorts are often possible.
into different buckets (perhaps based on the first letter). In a subsequent pass
we can sort the values in each bucket with, perhaps a different sort. The buck-
ets of sorted values are then accumulated, carefully maintaining the order of
the buckets, and the result is completely sorted. Unfortunately, the worst-case
behavior of this sorting technique is determined by the performance of the al-
gorithm we use to sort each bucket of values.
Exercise 6.2 Suppose we have n values and m buckets and we use insertion sort
to perform the sort of each bucket. What is the worst-case time complexity of this
sort?
Such a technique can be used to sort integers, especially if we can partially sort
the values based on a single digit. For example, we might develop a support
function, digit, that, given a number n and a decimal place d, returns the
value of the digit in the particular decimal place. If d was 0, it would return the
units digit of n. Here is a recursive implementation:
Here is the code for placing an array of integer values among 10 buckets, based
on the value of digit d. For example, if we have numbers between 1 and 52 and
we set d to 2, this code almost sorts the values based on their 10’s digit.
j = digit(value,d);
// add data value to end of vector; keeps values in order
bucket.get(j).add(value);
}
// collect data from buckets back into array
// collect in reverse order to unload Vectors
// in linear time
i = n;
for (j = 9; j >= 0; j--)
{
// unload all values in bucket j
while (!bucket.get(j).isEmpty())
{
i--;
value = bucket.get(j).remove();
data[i] = value;
}
}
}
We now have the tools to support a new sort, radix sort. The approach is to
use the bucketPass code to sort all the values based on the units place. Next,
all the values are sorted based on their 10’s digit. The process continues until
enough passes have been made to consider all the digits. If it is known that
values are bounded above, then we can also bound the number of passes as
well. Here is the code to perform a radix sort of values under 1 million (six
passes):
After the first bucketPass, the values are ordered, based on their units digit. All
values that end in 0 are placed near the front of data (see Figure 6.9), all the
values that end in 9 appear near the end. Among those values that end in 0, the
values appear in the order they originally appeared in the array. In this regard,
we can say that bucketPass is a stable sorting technique. All other things being
equal, the values appear in their original order.
During the second pass, the values are sorted, based on their 10’s digit.
Again, if two values have the same 10’s digit, the relative order of the values is
maintained. That means, for example, that 140 will appear before 42, because
after the first pass, the 140 appeared before the 42. The process continues, until
6.6 Radix Sort 137
Start
140 2 1 43 3 65 0 11 58 3 42 4
Digit 0
140 0 1 11 2 42 43 3 3 4 65 58
Digit 1
0 1 2 3 3 4 11 140 42 43 58 65
Digit 2
0 1 2 3 3 4 11 42 43 58 65 140
Digit 3
0 1 2 3 3 4 11 42 43 58 65 140
Digit 4
0 1 2 3 3 4 11 42 43 58 65 140
Digit 6
0 1 2 3 3 4 11 42 43 58 65 140
Finish
Figure 6.9 The state of the data array between the six passes of radixSort. The
boundaries of the buckets are identified by vertical lines; bold lines indicate empty buck-
ets. Since, on every pass, paths of incoming values to a bucket do not cross, the sort
is stable. Notice that after three passes, the radixSort is finished. The same would be
true, no matter the number of values, as long as they were all under 1000.
138 Sorting
all digits are considered. Here, six passes are performed, but only three are
necessary (see Problem 6.9).
There are several important things to remember about the construction of
this sort. First, bucketPass is stable. That condition is necessary if the work
of previous passes is not to be undone. Secondly, the sort is unlikely to work if
the passes are performed from the most significant digit toward the units digit.
Finally, since the number of passes is independent of the size of the data array,
the speed of the entire sort is proportional to the speed of a single pass. Careful
design allows the bucketPass to be accomplished in O(n) time. We see, then,
that radixSort is a O(n) sorting method.
While, theoretically, radixSort can be accomplished in linear time, practi-
cally, the constant of proportionality associated with the bound is large com-
pared to the other sorts we have seen in this chapter. In practice, radixSort is
inefficient compared to most other sorts.
class PhoneEntry
{
String name; // person's name
PhoneBook String title; // person's title
int extension; // telephone number
int room; // number of room
String building; // office building
Figure 6.10 An array of phone entries for the 107th Congressional Delegation from
Oregon State, before and after sorting by telephone (shaded).
We have added the compareTo method to describe the relation between two
entries in the phone book (the shaded fields of Figure 6.10). The compareTo
method returns an integer that is less than, equal to, or greater than 0 when
this is logically less than, equal to, or greater than other. We can now modify
any of the sort techniques provided in the previous section to sort an array of
phone entries:
Careful review of this insertion sort routine shows that all the < operators have
been replaced by checks for negative compareTo values. The result is that the
phone entries in the array are ordered by increasing phone number.
If two or more people use the same extension, then the order of the resulting
entries depends on the stability of the sort. If the sort is stable, then the relative
order of the phone entries with identical extensions in the sorted array is the
same as their relative order in the unordered array. If the sort is not stable, no
guarantee can be made. To ensure that entries are, say, sorted in increasing
order by extension and, in case of shared phones, sorted by increasing name,
the following compareTo method might be used:
Correctly specifying the relation between two objects with the compareTo meth-
od can be difficult when the objects cannot be totally ordered. Is it always possi-
ble that one athletic team is strictly less than another? Is it always the case that
one set contains another? No. These are examples of domains that are partially
ordered. Usually, however, most types may be totally ordered, and imagining
how one might sort a collection of objects forces a suitable relation between
any pair.
book, the entries would ideally be ordered based on the name associated with
the entry. Sometimes, however, the compareTo method does not provide the
ordering desired, or worse, the compareTo method has not been defined for an
object. In these cases, the programmer turns to a simple method for specifing an
external comparison method called a comparator. A comparator is an object that
contains a method that is capable of comparing two objects. Sorting methods,
then, can be developed to apply a comparator to two objects when a comparison
is to be performed. The beauty of this mechanism is that different comparators
can be applied to the same data to sort in different orders or on different keys.
In Java a comparator is any class that implements the java.util.Comparator
interface. This interface provides the following method:
package java.util;
public interface Comparator
{
public abstract int compare(Object a, Object b); Comparator
// pre: a and b are valid objects, likely of similar type
// post: returns a value less than, equal to, or greater than 0
// if a is less than, equal to, or greater than b
}
Like the compareTo method we have seen earlier, the compare method re-
turns an integer that identifies the relationship between two values. Unlike
the compareTo method, however, the compare method is not associated with
the compared objects. As a result, the comparator is not privy to the implemen-
tation of the objects; it must perform the comparison based on information that
is gained from accessor methods.
As an example of the implementation of a Comparator, we consider the
implementation of a case-insensitive comparison of Strings, called Caseless-
Comparator. This comparison method converts both String objects to upper-
case and then performs the standard String comparison:
public class CaselessComparator implements java.util.Comparator<String>
{
public int compare(String a, String b)
// pre: a and b are valid Strings Caseless-
// post: returns a value less than, equal to, or greater than 0 Comparator
// if a is less than, equal to, or greater than b, without
// consideration of case
{
String upperA = ((String)a).toUpperCase();
String upperB = ((String)b).toUpperCase();
return upperA.compareTo(upperB);
}
}
The result of the comparison is that strings that are spelled similarly in differ-
ent cases appear together. For example, if an array contains the words of the
children’s tongue twister:
142 Sorting
This should be compared with the standard ordering of String values, which
would generate the following output:
Note that in this description we don’t see the particulars of the types involved.
Instead, all data are manipulated as Objects, which are specifically manipulated
by the compare method of the provided Comparator.
6.9 Vector-Based Sorting 143
6.10 Conclusions
Sorting is an important and common process on computers. In this chapter we
considered several sorting techniques with quadratic running times. Bubble sort
approaches the problem by checking and rechecking the relationships between
elements. Selection and insertion sorts are based on techniques that people
commonly use. Of these, insertion sort is most frequently used; it is easily
coded and provides excellent performance when data are nearly sorted.
Two recursive sorting techniques, mergesort and quicksort, use recursion
to achieve O(n log n) running times, which are optimal for comparison-based
techniques on single processors. Mergesort works well in a variety of situations,
but often requires significant extra memory. Quicksort requires a random access
structure, but runs with little space overhead. Quicksort is not a stable sort
because it has the potential to swap two values with equivalent keys.
We have seen with radix sort, it is possible to have a linear sorting algorithm,
but it cannot be based on compares. Instead, the technique involves carefully
ordering values based on looking at portions of the key. The technique is, practi-
cally, not useful for general-purpose sorting, although for many years, punched
cards were efficiently sorted using precisely the method described here.
Sorting is, arguably, the most frequently executed algorithm on computers
today. When we consider the notion of an ordered structure, we will find that
algorithms and structures work hand in hand to help keep data in the correct
order.
6.4 During spring cleaning, you decide to sort four months of checks re-
turned with your bank statements. You decide to sort each month separately
and go from there. Is this valid? If not, why. If it is, what happens next?
6.5 A postal employee approximately sorts mail into, say, 10 piles based
on the magnitude of the street number of each address, pile 1 has 1-10, pile
2 has 11-20, etc. The letters are then collected together by increasing pile
number. She then sorts them into a delivery crate with dividers labeled with
street names. The order of streets corresponds to the order they appear on her
mail route. What type of sort is she performing?
6.6 What is the purpose of the compareTo method?
Problems
Solutions to the odd-numbered problems begin on page 464.
6.1 Show that to exchange two integer values it is not strictly necessary to
use a third, temporary integer variable. (Hint: Use addition and/or subtrac-
tion.)
6.2 We demonstrated that, in the worst case, bubble sort performs O(n2 )
operations. We assumed, however, that each pass performed approximately
O(n) operations. In fact, pass i performs as many as O(n − i) operations, for
1 ≤ i ≤ n − 1. Show that bubble sort still takes O(n2 ) time.
6.3 How does bubbleSort (as presented) perform in the best and average
cases?
6.4 On any pass of bubble sort, if no exchanges are made, then the rela-
tions between all the values are those desired, and the sort is done. Using this
information, how fast will bubble sort run in worst, best, and average cases?
6.5 How fast does selection sort run in the best, worst, and average cases?
6.6 How fast does insertion sort run in the best, worst, and average cases?
Give examples of best- and worst-case input for insertion sort.
6.7 Running an actual program, count the number of compares needed to
sort n values using insertion sort, where n varies (e.g., powers of 2). Plot your
data. Do the same thing for quicksort. Do the curves appear as theoretically
expected? Does insertion sort ever run faster than quicksort? If so, at what
point does it run slower?
6.8 Comparing insertion sort to quicksort, it appears that quicksort sorts
more quickly without any increase in space. Is that true?
6.9 At the end of the discussion on radix sort, we pointed out that the digit
sorting passes must occur from right to left. Give an example of an array of 5
two-digit values that do not sort properly if you perform the passes left to right.
6.10 In radix sort, it might be useful to terminate the sorting process when
numbers do not change position during a call to bucketPass. Should this mod-
ification be adopted or not?
146 Sorting
6.11 Using the millisecond timer, determine the length of time it takes to
perform an assignment of a nonzero value to an int. (Hint: It will take less
than a millisecond, so you will have to design several experiments that measure
thousands or millions of assignments; see the previous lab, on page 115, for
details.)
6.12 Running an actual program, and using the millisecond timer, System.-
currentTimeMillis, measure the length of time needed to sort arrays of data
of various sizes using a sort of your choice. Repeat the experiment but use
Vectors. Is there a difference? In either case, explain why. (Hint: You may
have to develop code along the lines of Problem 6.11.)
6.13 A sort is said to be stable if the order of equal values is maintained
throughout the sort. Bubble sort is stable, because whenever two equal val-
ues are compared, no exchange occurs. Which other sorts are stable (consider
insertion sort, selection sort, mergesort, and quicksort)?
6.14 The partition function of quicksort could be changed as follows: To
place the leftmost value in the correct location, count the number of values that
are strictly less than the leftmost value. The resulting number is the correct
index for the desired value. Exchange the leftmost value for the value at the
indexed location. With all other code left as it is, does this support a correctly
functioning quicksort? If not, explain why.
6.15 Modify the partition method used by quicksort so that the pivot is
randomly selected. (Hint: Before partitioning, consider placing the randomly
selected value at the left side of the array.)
6.16 Write a recursive selectionSort algorithm. (Hint: Each level of recur-
sion positions a value in the correct location.)
6.17 Write a recursive insertionSort algorithm.
6.18 Some of the best-performing sorts depend on the best-performing shuf-
fles. A good shuffling technique rearranges data into any arrangement with
equal probability. Design the most efficient shuffling mechanism you can, and
argue its quality. What is its performance?
6.19 Write a program called shuffleSort. It first checks to see if the data are
in order. If they are, the sort is finished. If they aren’t, the data are shuffled and
the process repeats. What is the best-case running time? Is there a worst-case
running time? Why or why not? If each time the data were shuffled they were
arranged in a never-seen-before configuration, would this change your answer?
6.20 Write a program to sort a list of unique integers between 0 and 1 million,
but only using 1000 32-bit integers of space. The integers are read from a file.
6.11 Laboratory: Sorting with Comparators
Thought Questions. Consider the following questions as you complete the lab:
1. Suppose we write the following Comparator:
import structure5.*;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Scanner;
public class RevComparator<T> implements Comparator<T>
{
protected Comparator<T> base;
while (s.hasNextInt())
{
v.add(s.nextInt());
}
Notes:
Chapter 7
A Design Method
Concepts:
. Signatures But, luckily, he kept his wits and his purple crayon.
. Interface design —Crockett Johnson
. Abstract base classes
1. Design of the interface. The interface describes the common external fea-
tures of all implementations.
Once the interface has been defined, it can be put to immediate use. Potential
users of the class can be asked to review it. In fact, application code can be
written to make use of the new interface. Later, if particular implementations
are developed, the application code can be put to use. It is important to remem-
ber, however, that the development of the application and the implementation
of the data structure may both proceed at the same time.
7.1 The Interface-Based Approach 151
Once the interface has been outlined, it is useful for the designer to consider
those functions of the structure that are implementation independent. These
pieces are gathered together in a partial or abstract implementation of the in-
terface called an abstract base class. Since some parts of the interface may not
be implemented in the abstract base class—perhaps they require a commitment
to a particular implementation approach—it is necessary for the class to be de-
clared abstract. Once the abstract class is implemented, it may be used as a
basis for developing extensions that describe particular implementations.
Some structures may have some built-in redundancy in their public methods.
An interface supporting trigonometric calculations might, for example, have a
method tan which computes its result from sin and cos. No matter how sin
and cos are actually implemented, the tan method can be implemented in this
manner. On the other hand, if a tan function can be computed in a more di-
rect manner—one not dependent on sin and cos—a particular implementation
might override the method outlined in the abstract base class.
A similar approach is taken in Vector-like classes that implement a backward-
compatible setElementAt method based on the more recently added set method.
Such a method might appear in an abstract base class as
Because such code cannot be included in any interface that might describe a
Vector, we place the code in the abstract class.
Implementors of other abstract objects may find it useful to develop a com-
mon library of methods that support all implementations. These methods—
often declared privately—are only made available to the implementor of the
class. If they are utility methods (like sin and sqrt) that are not associated
with a particular object, we also declare them static.
Thus the abstract base class provides the basis for all implementations of
an interface. This includes implementation-independent code that need not be
rewritten for each implementation. Even if an abstract base class is empty, it is
useful to declare the class to facilitate the implementation of implementation-
independent development later in the life of the data structure. It is frequently
the case, for example, that code that appears in several implementations is re-
moved from the specific implementations and shared from the abstract base
class. When implementations are actually developed, they extend the associ-
ated abstract base class.
152 A Design Method
7.1.3 Implementation
When the abstract base class is finished, it is then possible for one or more im-
plementations to be developed. Usually each of these implementations extends
the work that was started in the abstract base class. For example, a Fraction
interface might be implemented as the ratio of two values (as in the Ratio
class we saw in Chapter 1), or it might be implemented as a double. In the
latter case, the double is converted to an approximate ratio of two integers,
the numerator and denominator. In both cases, it might be useful to declare an
AbstractFraction class that includes a greatest common divisor (gcd) method.
Such a method would be declared protected and static.
The Generator is constructed and the get method can be used to get its initial
value. When necessary, the next routine generates, one at a time, a sequence of
integer values. Each call to next returns the next value in the sequence, a value
that can be recalled using the get method. If necessary, the reset method can
be used to restart the sequence of generated values.
The next step is to generate an abstract base class that implements the inter-
face. For the AbstractGenerator we implement any of the methods that can
be implemented in a general manner. We choose, here, for example, to provide
a mechanism for the next method to save the current value:
public AbstractGenerator()
// post: initialize the current value to zero
{
this(0);
}
The current variable keeps track of a single integer—ideally the last value gen-
erated. This value is the value returned by the get method. A hidden method—
set—allows any implementation to set the value of current. It is expected
that this is called by the next method of the particular implementation. By pro-
viding this code in the abstract base class, individual implementations needn’t
repeatedly reimplement this common code. By default, the reset method does
nothing. If a particular generator does not require a reset method, the default
method does nothing.
Here is a simple implementation of a Generator that generates a constant
value. The value is provided in the constructor:
{
set(c);
}
The set method of the AbstractGenerator is called from the constructor, record-
ing the constant value to be returned. This effectively implements the get
method—that code was provided in the AbstractGenerator class. The next
method simply returns the value available from the get method.
Another implementation of a Generator returns a sequence of prime num-
bers. In this case, the constructor sets the current value of the generator to
2—the first prime. The next method searches for the next prime and returns
that value after it has been saved. Here, the private set and the public get
methods from the AbstractGenerator class help to develop the state of the
Generator:
}
} while (f*f <= n);
set(n);
return n;
}
}
Clearly, the reset method is responsible for restarting the sequence at 2. While
it would be possible for each Generator to keep track of its current value in its
own manner, placing that general code in the AbstractGenerator reduces the
overall cost of keeping track of this information for each of the many implemen-
tations.
The card interface provides all the public methods that we need to have in our
card games, but it does not provide any hints at how the cards are implemented.
The interface also provides standard names for faces and suits that are passed
to and returned from the various card methods.
In the expectation that most card implementations are similar to a stan-
dard deck of cards, we provide an AbstractCard class that keeps track of an
integer—a card index—that may be changed with set or retrieved with get
(both are protected methods):
import java.util.Random;
public abstract class AbstractCard implements Card
{
AbstractCard protected int cardIndex;
protected static Random gen = new Random();
public AbstractCard()
// post: constructs a random card in a standard deck
{
set(randomIndex(52));
}
cardIndex = index;
}
Our abstract base class also provides a protected random number generator that
returns values from 0 to max-1. We make use of this in the default constructor
for a standard deck; it picks a random card from the usual 52. The cards are
indexed from the ace of clubs through the king of spades. Thus, the face and
suit methods must use division and modulo operators to split the card index
into the two constituent parts. By default, the value method returns the face of
the card as its value. This is likely to be different for different implementations
of cards, as the face values of cards in different games vary considerably.
We also provide a standard toString method that allows us to easily print
out a card. We do not provide a compareTo method because there are complex-
ities with comparing cards that cannot be predicted at this stage. For example,
in bridge, suits play a predominant role in comparing cards. In baccarat they do
not.
Since a poker deck is very similar to our standard implementation, we find
the PokerCard implementation is very short. All that is important is that we
allow aces to have high values:
public class PokerCard extends AbstractCard
{
public PokerCard(int face, int suit)
PokerCard // pre: face and suit have valid values
// post: constructs a card with the particular face value
{
set(suit*13+face-1);
}
public PokerCard()
// post: construct a random poker card.
{
// by default, calls the AbstractCard constructor
}
{
PokerCard that = (PokerCard)other;
return value()-that.value();
}
}
Exercise 7.2 Write the value and compareTo methods for a pair of cards where
suits play an important role. Aces are high, and assume that suits are ranked clubs
(low), diamonds, hearts, and spades (high). Assume that face values are only
considered if the suits are the same; otherwise ranking of cards depends on their
suits alone.
The implementation of a pinochle card is particularly difficult. We are inter-
ested in providing the standard interface for a pinochle card, but we are faced
with the fact that there are two copies each of the six cards 9, jack, queen, king,
10, and ace, in each of the four suits. Furthermore we assume that 10 has the
unusual ranking between king and ace. Here’s one approach:
public class PinochleCard extends AbstractCard
{
// cardIndex face suit
// 0 9 clubs PinochleCard
// 1 9 clubs (duplicate)
// ...
// 10 ACE clubs
// 11 ACE clubs (duplicate)
// 12 9 diamonds
// 13 9 diamonds (duplicate)
// ...
// 47 ACE spades (duplicate)
public PinochleCard()
// post: construct a random Pinochle card.
{
set(randomIndex(48));
}
return result;
}
The difficulty is that there is more than one copy of a card. We choose to keep
track of the extra copy, in case we need to distinguish between them at some
point, but we treat duplicates the same in determining face value, suit, and
relative rankings.
7.4 Conclusions
Throughout the remainder of this book we will find it useful to approach each
type of data structure first in an abstract manner, and then provide the details of
various implementations. While each implementation tends to have a distinct
approach to supporting the abstract structure, many features are common to all
implementations. The basic interface, for example, is a shared concept of the
methods that are used to access the data structure. Other features—including
common private methods and shared utility methods—are provided in a basic
implementation called the abstract base class. This incomplete class serves as
a single point of extension for many implementations; the public and private
features of the abstract base class are shared (and possibly overridden) by the
varied approaches to solving the problem.
Chapter 8
Iterators
Concepts:
. Iterators One potato, two potato, three potato, four,
. The AbstractIterator class five potato, six potato, seven potato, more.
. Vector iterators —A child’s iterator
. Numeric iteration
P ROGRAMS MOVE FROM ONE STATE TO ANOTHER . As we have seen, this “state” Ah! Interstate
is composed of the current value of user variables as well as some notion of programs!
“where” the computer is executing the program. This chapter discusses enumer-
ations and iterators—objects that hide the complexities of maintaining the state
of a traversal of a data structure.
Consider a program that prints each of the values in a list. It is important
to maintain enough information to know exactly “where we are” at all times.
This might correspond to a reference to the current value. In other structures
it may be less clear how the state of a traversal is maintained. Iterators help us
hide these complexities. The careful design of these control structures involves,
as always, the development of a useful interface that avoids compromising the
iterator’s implementation or harming the object it traverses.
Hello world!
There are some important caveats that come with the use of Java’s Enumera-
tion construct. First, it is important to avoid modifying the associated structure
while the Enumeration is active or live. Uncommenting the line marked SILLY
causes the following infinite output to begin:
A silly virus Inserting the string "silly" as the new second element of the Vector causes it
vector! to expand each iteration of the loop, making it difficult for the Enumeration to
detect the end of the Vector.
NE
live.
W
E
SW
SE
the Enumeration and its associated structure are hidden. Making assumptions
about their interaction can be dangerous.
Another subtle aspect of Enumerations is that they do not guarantee a par-
ticular traversal order. All that is known is that each element will be visited
exactly once before hasMoreElements becomes false. While we assume that
our first example above will print out Hello world!, the opposite order may
also be possible.
Presently, we develop the concept of an iterator.
While the Iterator is a feature built into the Java language, we will choose to
implement our own AbstractIterator class.
This abstract base class not only meets the Iterator interface, but also im-
plements the Enumeration interface by recasting the Enumeration methods in
terms of Iterator methods. We also provide some important methods that are
not part of general Iterators: reset and get. The reset method reinitializes
the AbstractIterator for another traversal. The ability to traverse a structure
multiple times can be useful when an algorithm makes multiple passes through
a structure to perform a single logical operation. The same functionality can be
achieved by constructing a new AbstractIterator between passes. The get
method of the AbstractIterator retrieves a reference to the current element of
the traversal. The same reference will be returned by the call to next. Unlike
next, however, get does not push the traversal forward. This is useful when
the current value of an AbstractIterator is needed at a point logically distant
from the call to next.
The use of an AbstractIterator leads to the following idiomatic loop for
traversing a structure:
We will see this form of for loop used on many structure classes.
Vector-
Iterator
166 Iterators
public E get()
// pre: traversal has more elements
// post: returns the current value referenced by the iterator
public E next()
// pre: traversal has more elements
// post: increments the iterated traversal
}
As is usually the case, the nonconstructor methods of VectorIterator exactly
match those required by the Iterator interface. Here is how the VectorIter-
ator is constructed and initialized:
protected Vector<E> theVector;
protected int current;
public VectorIterator(Vector<E> v)
// post: constructs an initialized iterator associated with v
{
theVector = v;
reset();
}
This routine simply checks to see if the current index is valid. If the index is less
than the size of the Vector, then it can be used to retrieve a current element
from the Vector. The two value-returning methods are get and next:
public E get()
// pre: traversal has more elements
// post: returns the current value referenced by the iterator
{
return theVector.get(current);
}
public E next()
// pre: traversal has more elements
// post: increments the iterated traversal
{
return theVector.get(current++);
}
The get method simply returns the current element. It may be called arbitrarily
many times without pushing the traversal along. The next method, on the other
hand, returns the same reference, but only after having incremented current.
The next value in the Vector (again, if there is one) becomes the current value.
Since all the Iterator methods have been implemented, Java will allow a
VectorIterator to be used anywhere an Iterator is required. In particular, it
can now be returned from the iterator method of the Vector class.
Observe that while the user cannot directly construct a VectorIterator (it
is a nonpublic class), the Vector can construct one on the user’s behalf. This
allows measured control over the agents that access data within the Vector.
Also, an Iterator is a Java interface. It is not possible to directly construct an
Iterator. We can, however, construct any class that implements the Iterator
interface and use that as we would any instance of an Iterator.
Since an AbstractIterator implements the Enumeration interface, we may
use the value returned by Vector’s iterator method as an Enumeration to
access the data contained within the Vector. Of course, treating the Vector-
Iterator as an Enumeration makes it difficult to call the AbstractIterator
methods reset and get.
the Iterator interface is more general. Any Object, including Integer values,
may be returned from an Iterator.
In this section we experiment with the construction of a numeric iterator—a
Generator-like class that meets the Iterator interface. In particular, we are
interested in constructing an Iterator that generates prime factors of a specific
integer. The PFIterator accepts the integer to be factored as the sole parameter
on the constructor:
import structure5.AbstractIterator;
public class PFGenerator extends AbstractIterator<Integer>
{
PFGenerator // the original number to be factored
protected int base;
The process of determining the prime factor involves reducing the number by a
factor. Initially, the factor f starts at 2. It remains 2 as long as the reduced value
is even. At that point, all the prime factors of 2 have been determined, and we
next try 3. This process continues until the reduced value becomes 1.
Because we reduce the number at each step, we must keep a copy of the
original value to support the reset method. When the iterator is reset, the
original number is restored, and the current prime factor is set to 2.
If, at any point, the number n has not been reduced to 1, prime factors
remain undiscovered. When we need to find the current prime factor, we first
check to see if f divides n—if it does, then f is a factor. If it does not, we simply
increase f until it divides n. The next method is responsible for reducing n by a
factor of f.
8.4 Example: Rethinking Generators 169
We can now write a program that uses the iterator to print out the prime
factors of the values presented on the command line of the Java program as it
is run:
public static void main(String[]args)
{
// for each of the command line arguments
for (int i = 0; i < args.length; i++)
{
// determine the value
int n = Integer.parseInt(args[i]);
PFGenerator g = new PFGenerator(n);
System.out.print(n+": ");
// and print the prime factors of n
while (g.hasNext()) System.out.print(g.next()+" ");
System.out.println();
}
}
For those programmers that prefer to use the hasMoreElements and next-
Element methods of the Enumeration interface, those methods are automat-
ically provided by the AbstractIterator base class, which PFGenerator ex-
tends.
seeds ever tested. Write an Iterator that, given a seed, generates the sequence of
values that ends with 1.
The result of the program, when run on the Gettysburg Address, is the follow-
ing output, which helps increase the vocabulary of this textbook by nearly 139
words:
When the filter is reset using the reset method, the base iterator is reset as
well. We then construct an empty List of words previously observed. As the
filter progresses, words encountered are incorporated into the observed list.
The current value is fetched by the get method. It just passes the request
along to the base iterator. A similar technique is used with the hasNext method:
public T get()
// pre: traversal has more elements
// post: returns the current value referenced by the iterator
{
172 Iterators
return base.get();
}
Finally, the substance of the iterator is found in the remaining method, next:
public T next()
// pre: traversal has more elements
// post: returns current value and increments the iterator
{
T current = base.next();
// record observation of current value
observed.add(current);
// now seek next new value
while (base.hasNext())
{
T possible = base.get();
if (!observed.contains(possible))
{ // new value found! leave
break;
} else {
// old value, continue
base.next();
}
}
return current;
}
Because this routine can only be called if there is a current value, we record the
current value in the observed list. The method then increments the base iterator
until a new, previously unobserved value is produced, or the base iterator runs
dry.
Some subtle details are worth noting here. First, while we have used a
VectorIterator on a Vector of Strings, the UniqueFilter can be applied, as
is, to any type of iterator and can deliver any type of value. All that is required
is that the base type support the equals method. Secondly, as the filter iterator
progresses, it forces the base iterator to progress, too. Because of this, two filters
are usually not applied to the same base iterator, and the base iterator should
never be modified while the filter is running.
8.6 Conclusions
We have seen that data structures can sometimes be used to control the way
programs focus on and access data. This is made very explicit with Java’s
Enumeration construct that facilitates visiting all the elements of a structure.
When we wish to traverse the elements of a data structure in a predeter-
mined order, we use an Iterator. The Iterator provides access to the ele-
ments of a structure using an interface that is similar to that of an Enumeration.
8.6 Conclusions 173
The abstract base class AbstractIterator implements both the Iterator and
Enumeration interfaces, and provides two new methods—get and reset—as
well. We have also seen that there are weaknesses in the concept of both of
these constructs, because they surrender some of the data hiding and access
controls that are provided by the associated structure. Careful use of these con-
trolling structures, however, can yield useful tools to make traversal of struc-
tures simpler.
Problems
Solutions to the odd-numbered problems begin on page 467.
8.1 Since the get method is available to the AbstractIterator, the next
method does not appear to need to return a value. Why does our implementa-
tion return the value?
8.2 Write an Iterator that works on Strings. Each value returned should
be an object of type Character.
8.3 Write an Iterator that returns a stream of Integers that are prime.
How close is it to the Generator implementation of Section 7.2?
8.4 Write a filtering iterator, ReverseIterator, that reverses the stream of
values produced by another Iterator. You may assume that the base Iterator
will eventually have no more elements, but you may not bound the number.
8.5 Write a filtering iterator, OrderedIterator, that sorts the stream of
values produced by another Iterator. You may assume that the base Iterator
will eventually have no more elements, but you may not bound the number.
8.6 Write a filtering iterator, ShuffleIterator, that shuffles the stream of
values produced by another Iterator. You may assume that the base Iterator
will eventually have no more elements, but you may not bound the number.
174 Iterators
8.7 Write a filtering iterator that takes a base iterator and an Object (called
predicate) with a static select method defined. This iterator passes along
only those values that generate true when passed to the select method of the
predicate Object.
8.7 Laboratory: The Two-Towers Problem
Still, this stacking is only the second-best solution! To find the best stacking, we
could consider all the possible configurations.
We do know one thing: the total height of the two towers is computed by
summing the heights of all the blocks:
n
X √
h= i
i=1
If we consider all the subsets of the n blocks, we can think of the subset as the
set of blocks that make up, say, the left tower. We need only keep track of that
subset that comes closest to h/2 without exceeding it.
In this lab, we will represent a set of n distinct objects by a Vector, and we
will construct an Iterator that returns each of the 2n subsets.
Procedure. The trick to understanding how to generate a subset of n values
from a Vector is to first consider how to generate a subset of indices of elements
from 0 to n − 1. Once this simpler problem is solved, we can use the indices to
help us build a Vector (or subset) of values identified by the indices.
There are exactly 2n subsets of values 0 to n−1. We can see this by imagining
that a coin is tossed n times—once for each value—and the value is added to
the subset if the coin flip shows a head. Since there are 2 × 2 × · · · × 2 = 2n
different sequences of coin tosses, there are 2n different sets.
We can also think of the coin tosses as determining the place values for n
different digits in a binary number. The 2n different sequences generate binary
numbers in the range 0 through 2n − 1. Given this, we can see a line of attack:
176 Iterators
count from 0 to 2n −1 and use the binary digits (bits) of the number to determine
which of the original values of the Vector are to be included in a subset.
Computer scientists work with binary numbers frequently, so there are a
number of useful things to remember:
• The arithmetic shift operator (<<) can be used to quickly compute powers
of 2. The value 2i can be computed by shifting a unit bit (1) i places to the
left. In Java we write this 1<<i. This works only for nonnegative, integral
powers. (For long integers, use 1L<<i.)
• The bitwise and of two integers can be used to determine the value of
a single bit in a number’s binary representation. To retrieve bit i of an
integer m we need only compute m & (1<<i).
Armed with this information, the process of generating subsets is fairly straight-
forward. One line of attack is the following:
3. Write a hasNext method that returns true if the current value is a reason-
able representation of a subset.
4. Write a get method that returns a new Vector of values that are part of
the current subset. If bit i of the current counter is 1, element i of the
Vector is included in the resulting subset Vector.
5. Write a next method. Remember it returns the current subset before in-
crementing the counter.
You can now test your new SubsetIterator by having it print all the subsets
of a Vector of values. Remember to keep the Vector small. If the original values
are all distinct, the subsets should all have different values.
8.7 Laboratory: The Two-Towers Problem 177
√ To√solve the√ two-towers problem, write a main method that inserts the values
1, 2,. . . , n as Double objects into a Vector. A SubsetIterator is then
used to construct 2n subsets of these values. The values of each subset are
summed, and the sum that comes closest to, but does not exceed, the value
h/2 is remembered. After all the subsets have been considered, print the best
solution.
Thought Questions. Consider the following questions as you complete the lab:
Notes:
Chapter 9
Lists
Concepts:
. The list abstraction
He’s makin’ a list
. Singly linked lists
and checkin’ it twice!
. Doubly linked lists
—Haven Gillespie
. Circular lists
. Vectors as lists
If you have
never seen
these, visit your
niece.
180 Lists
Now, let’s see what the Java description of a list looks like:
public E getFirst();
// pre: list is not empty
// post: returns first value in list
public E getLast();
// pre: list is not empty
// post: returns last value in list
public E removeFirst();
// pre: list is not empty
// post: removes first value from list
public E removeLast();
// pre: list is not empty
// post: removes last value from list
public E remove();
// pre: list has at least one element
// post: removes last value found in list
public E get();
// pre: list has at least one element
// post: returns last value found in list
181
madam
I'm
Adam!
...
Adam!
9.2 Example: Free Lists 183
I'm
Ada!
...
mad
am I...
madam
madam
I'm
Adam!
...
Ada!
mad
am I...
Because there is no practical limit (other than the amount of memory available)
on the length of a list, there is no practical limit on the size of the input that
can be fed to the program. The list interface does not provide any hint of how
the list is actually implemented, so it is difficult to estimate the performance of
the program. It is likely, however, that the contains method—which is likely
to have to consider every existing element of the list—and the add method—
which might have to pass over every element to find its correct position—will
govern the complexity of the management of this List. As we consider imple-
mentations of Lists, we should keep the performance of programs like Unique
in mind.
class Space
{ // structure describing parking space
public final static int COMPACT = 0; // small space ParkingLot
public final static int MINIVAN = 1; // medium space
public final static int TRUCK = 2; // large space
protected int number; // address in parking lot
protected int size; // size of space
public Space(int n, int s)
// post: construct parking space #n, size s
{
184 Lists
number = n;
size = s;
}
public boolean equals(Object other)
// pre: other is not null
// post: true iff spaces are equivalent size
{
Space that = (Space)other;
return this.size == that.size;
}
}
The lot consists of 10 spaces of various sizes: one large, six medium, and three
small. Renters may rent a space if one of appropriate size can be found on
the free list. The equals method of the Space class determines an appropriate
match. The rented list maintains Associations between names and space de-
scriptions. The following code initializes the free list so that it contains all the
parking spaces, while the rented list is initially empty:
The main loop of our program reads in commands from the keyboard—either
rent or return:
Scanner s = new Scanner(System.in);
while (s.hasNext())
{
String command = s.next(); // rent/return
...
}
System.out.println(free.size()+" slots remain available.");
Within the loop, when the rent command is entered, it is followed by the size
of the space needed and the name of the renter. This information is used to
construct a contract:
Space location;
if (command.equals("rent"))
{ // attempt to rent a parking space
9.2 Example: Free Lists 185
Notice that when the contains method is called on a List, a dummy element is
constructed to specify the type of object sought. When the dummy item is used
in the remove command, the actual item removed is returned. This allows us to
maintain a single copy of the object that describes a single parking space.
When the spaces are returned, they are returned by name. The contract is
looked up and the associated space is returned to the free list:
Space location;
if (command.equals("return")){
String renter = s.next(); // from whom?
// template for finding "rental contract"
Association<String,Space> query = new Association<String,Space>(renter);
if (rented.contains(query))
{ // contract found
Association<String,Space> contract =
rented.remove(query);
location = contract.getValue(); // where?
free.add(location); // put in free list
System.out.println("Space "+location.number+" is now free.");
} else {
System.out.println("No space rented to "+renter);
}
}
Notice that when Alice’s space is returned, it is not immediately reused because
the free list contains other small, free spaces. The use of addLast instead of
addFirst (or the equivalent method, add) would change the reallocation policy
of the parking lot.
We now consider an abstract base class implementation of the List inter-
face.
{
add(0,value);
}
public E getFirst()
// pre: list is not empty
// post: returns first value in list
{
return get(0);
}
public E getLast()
// pre: list is not empty
// post: returns last value in list
{
return get(size()-1);
}
public E removeFirst()
// pre: list is not empty
// post: removes first value from list
{
return remove(0);
}
public E removeLast()
// pre: list is not empty
// post: removes last value from list
{
return remove(size()-1);
}
public E remove()
// pre: list has at least one element
// post: removes last value found in list
{
return removeLast();
}
188 Lists
public E get()
// pre: list has at least one element
// post: returns last value found in list
{
return getLast();
}
A B
Figure 9.1 Pictures of a null reference (left) and a non-null reference to an instance
of a class (right).
NW
NE
Principle 10 When manipulating references, draw pictures.
E
SW
SE
S
In this text, we will draw references as arrows pointing to their respective ob-
jects (Figure 9.1). When a reference is not referencing anything, we draw it as
a dot. Since references can only be in one of two states—pointing to nothing or
pointing to an object—these are the only pictures we will ever draw.
One approach to keeping track of arbitrarily large collections of objects is to
use a singly linked list to dynamically allocate each chunk of memory “on the
fly.” As the chunks of memory are allocated, they are linked together to form First garbage,
the entire structure. This is accomplished by packaging with each user object a now flies!
reference to the next object in the chain. Thus, a list of 10 items contains 10
elements, each of which contains a value as well as another element reference.
Each element references the next, and the final element does not reference
anything: it is assigned null (see Figure 9.2). Here, an implementation of a
Node contains an additional reference, nextElement:
public Node(E v)
// post: constructs a new tail of a list with value v
{
this(v,null);
}
public E value()
// post: returns value associated with this element
{
return data;
}
When a list element is constructed, the value provided is stored away in the ob-
ject. Here, nextElement is a reference to the next element in the list. We access
the nextElement and data fields through public methods to avoid accessing
protected fields. Notice that, for the first time, we see a self-referential data
structure: the Node object has a reference to a Node. This is a feature common
to structures whose size can increase dynamically. This class is declared public
so that anyone can construct Nodes.
We now construct a new class that implements the List interface by extend-
ing the AbstractList base class. For that relation to be complete, it is necessary
to provide a complete implementation of each of the methods promised by the
9.4 Implementation: Singly Linked Lists 191
count head
3 Life
on
Mars
count head
This code sets the head reference to null and the count field to 0. Notice that,
by the end of the constructor, the list is in a consistent state. N
NW
NE
W
Principle 11 Every public method of an object should leave the object in a consis-
E
SW
SE
tent state. S
192 Lists
Recall that the isEmpty method described in the AbstractList class simply
returns whether or not the size method would return 0. There’s a great advan-
tage to calling the size method to implement isEmpty: if we ever change the
implementation, we need only change the implementation of size.
Both of these methods could avoid referencing the count field, by travers-
ing each of the next references. In this alternative code we use the analogy
of a finger referencing each of the elements in the list. Every time the finger
references a new element, we increment a counter. The result is the number of
elements. This time-consuming process is equivalent to constructing the infor-
mation stored explicitly in the count field.
public int size()
// post: returns number of elements in list
{
// number of elements we've seen in list
int elementCount = 0;
// reference to potential first element
Node<E> finger = head;
Note that isEmpty does not need to change.1 It is early verification that the
interface for size helps to hide the implementation.
The decision between the two implementations has little impact on the user
of the class, as long as both implementations meet the postconditions. Since
the user is insulated from the details of the implementation, the decision can
be made even after applications have been written. If, for example, an environ-
ment is memory-poor, it might be wise to avoid the use of the count field and
1 In either case, the method isEmpty could be written more efficiently, checking a null head
reference.
9.4 Implementation: Singly Linked Lists 193
4 Yes!
3 Life
Life
on
on
Mars
Mars
Figure 9.4 A singly linked list before and after the call to addFirst. Shaded value is
added to the list. The removeFirst method reverses this process and returns value.
instead traverse the list to determine the number of elements by counting them.
If, however, a machine is slow but memory-rich, then the first implementation
would be preferred. Bot