Java Reference
In-Depth Information
One application that makes use of some ADT might use particular member
functions of that ADT more than a second application, or the two applications might
have different time requirements for the various operations. These differences in the
requirements of applications are the reason why a given ADT might be supported
by more than one implementation.
Example1.5
Two popular implementations for large disk-based database
applications are hashing (Section 9.4) and the B
+
-tree (Section 10.5). Both
support efficient insertion and deletion of records, and both support exact-
match queries. However, hashing is more efficient than the B
+
-tree for
exact-match queries. On the other hand, the B
+
-tree can perform range
queries efficiently, while hashing is hopelessly inefficient for range queries.
Thus, if the database application limits searches to exact-match queries,
hashing is preferred. On the other hand, if the application requires support
for range queries, the B
+
-tree is preferred. Despite these performance is-
sues, both implementations solve versions of the same problem: updating
and searching a large collection of records.
The concept of an ADT can help us to focus on key issues even in non-comp-
uting applications.
Example1.6
When operating a car, the primary activities are steering,
accelerating, and braking. On nearly all passenger cars, you steer by turn-
ing the steering wheel, accelerate by pushing the gas pedal, and brake by
pushing the brake pedal. This design for cars can be viewed as an ADT
with operations “steer,” “accelerate,” and “brake.” Two cars might imple-
ment these operations in radically different ways, say with different types
of engine, or front- versus rear-wheel drive. Yet, most drivers can oper-
ate many different cars because the ADT presents a uniform method of
operation that does not require the driver to understand the specifics of any
particular engine or drive design. These differences are deliberately hidden.
The concept of an ADT is one instance of an important principle that must be
understood by any successful computer scientist: managing complexity through
abstraction. A central theme of computer science is complexity and techniques
for handling it. Humans deal with complexity by assigning a label to an assembly
of objects or concepts and then manipulating the label in place of the assembly.
Cognitive psychologists call such a label a metaphor. A particular label might be
related to other pieces of information or other labels. This collection can in turn be
given a label, forming a hierarchy of concepts and labels. This hierarchy of labels
allows us to focus on important issues while ignoring unnecessary details.
