O'Reilly logo

Data Structures Using Java by Duncan A. Buell

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8 CHAPTER 1INTRODUCTION
not usually write code that assumes that the one-in-a-billion worst case is going to
happen. For example, the first time we create a sorted telephone book, we might
want to assume that the records are in a reasonably random order, but if we are
adding new records to a telephone-book-sized address list, we can safely assume
that we are starting with a large list that is already sorted and then adding a small
number of records to that list. These assumptions might well lead to the use of a
different sorting algorithm for the incremental updates than was used for creating
the list in the first place.
A different version of the heuristics issue is that programming for performance
requires identifying the most serious bottlenecks and then applying some better
brainpower to those bottlenecks first. There is probably no point in using a com-
plicated algorithm for a task that is done infrequently and is not time-critical. In
software, as in life, there is always a list of the most important things to be accom-
plished, and we should be attacking those before we go about making cosmetic
changes or changes that will have no real effect.
1.1.9 Templates, Generics, and Abstract Classes
We have described a flat file that comprises records (lines in a spreadsheet), each
record of which has fields (the columns). In any real programming situation, field
items will exist as strings, integers, floating-point numbers, and other less primitive
types. To avoid writing almost the same code over and over again, Java can provide
generic constructs and abstract classes that will simplify the coding process (that
is, the process will be simpler once one learns how to use generics and abstract
classes). In sorting, for example, the structure of a sort is independent of whether
one is sorting integers as integers or sorting strings (like last names) lexicographi-
cally; the base step in sorting an array into “increasing” order is to compare two
data items and exchange the order of the two items if necessary so that the “smaller”
item comes first. Good programming practice will therefore put off until the very
last moment any code that specifically deals with one data type or another, and
only at the very last moment use an appropriate compare-and-exchange method
for two data items.
One issue of data structures that does not necessarily present itself in a flat file
but is so important that it warrants mention here is the nature of tree structures and
then eventually of recursion. One canonical use of a tree structure is the directory
structure on a modern computer. In Unix, the “root” data structure is the “/”
directory, and all the directories and files live underneath that. Users will have a
“home” directory and create under that various files and subdirectories, with the
subdirectories then having files and subdirectories, and so forth. In Windows, most
user data starts at the My Documents folder (Windows uses the term “folder”
instead of “directory”) and descends from there.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required