2 CHAPTER 1INTRODUCTION
would reasonably be taken on such a structure would be to sort it into alphabetical
order, to add new records and delete old ones, and to retrieve entries based on
one or more search keys like last name or city of residence. In Chapter 3, we will
present the basics of a naive ﬂat ﬁle implementation, and then in later chapters we
will introduce the structures and algorithms that allow for more sophisticated and
more eﬃcient management of the data.
1.1.1 Layers of Software
A central theme in the development of software in a modern setting is that
software exists in layers. This is critical to understanding concepts of how and
why software is developed the way it is and why there are right ways and wrong
ways to develop code.
If you, for example, are the programmer developing an address book imple-
mentation, your job is to develop code that handles “address-book-ness.” This
will include adding, deleting, and editing records; sorting, displaying, and print-
ing copies; perhaps adding and deleting ﬁelds in the record; and (in many current
applications) linking to web pages or sending text or making phone calls. What
you as the address book programmer ought not to be concerned about is how the
data is stored in detail. That takes place one level down in the software hierarchy.
Although you need to be aware of the existence of the data storage methods that
have been chosen for use, your code need not be concerned with the implementa-
tion of those storage methods. Implementation of the storage methods should take
place one level down, and that code should be written so as to be independent of
the application that is using it.
This layering of code allows programmers to concentrate on the tasks at hand
without being distracted by other issues, and it allows code to be used by diﬀerent
programs. You have by now used library code for things like input and output.
Your program need not be concerned with how the println statement gets your
data to the console; it need only be conﬁdent that the code will accomplish that
task correctly and consistently. In this course, we will extend that concept to higher
structures that you write as well as to further structures built into Java in the large.
1.1.2 Algorithms and Efﬁciency
Computers demonstrate their real value not when doing small amounts of work on
small amounts of data, but when doing large amounts of work on large amounts of
data or when doing the same small task over and over again. Modern computers are
very fast, much faster than their predecessors of even 10 or 20 years ago. But as fast
as computers are, it is still usually the case that we do need to make programs run at
least reasonably eﬃciently. For this reason, we will cover some of the background of
how we measure the eﬃciency of an algorithm or program and why some algorithms