Java Reference
In-Depth Information
tion may be allowed to take longer, perhaps on the order of a minute. To
meet this requirement, it will be necessary to support operations that pro-
cess range queries efficiently by processing all cities in the range as a batch,
rather than as a series of operations on individual cities.
The hash table suggested in the previous example is inappropriate for
implementing our city database, because it cannot perform efficient range
queries. The B
+
-tree of Section 10.5.1 supports large databases, insertion
and deletion of data records, and range queries. However, a simple linear in-
dex as described in Section 10.1 would be more appropriate if the database
is created once, and then never changed, such as an atlas distributed on a
CD or accessed from a website.
1.2
Abstract Data Types and Data Structures
The previous section used the terms “data item” and “data structure” without prop-
erly defining them. This section presents terminology and motivates the design
process embodied in the three-step approach to selecting a data structure. This mo-
tivation stems from the need to manage the tremendous complexity of computer
programs.
A type is a collection of values. For example, the Boolean type consists of the
values
true
and
false
. The integers also form a type. An integer is a simple
type because its values contain no subparts. A bank account record will typically
contain several pieces of information such as name, address, account number, and
account balance. Such a record is an example of an aggregate type or composite
type. A data item is a piece of information or a record whose value is drawn from
a type. A data item is said to be a member of a type.
A data type is a type together with a collection of operations to manipulate
the type. For example, an integer variable is a member of the integer data type.
Addition is an example of an operation on the integer data type.
A distinction should be made between the logical concept of a data type and its
physical implementation in a computer program. For example, there are two tra-
ditional implementations for the list data type: the linked list and the array-based
list. The list data type can therefore be implemented using a linked list or an ar-
ray. Even the term “array” is ambiguous in that it can refer either to a data type
or an implementation. “Array” is commonly used in computer programming to
mean a contiguous block of memory locations, where each memory location stores
one fixed-length data item. By this meaning, an array is a physical data structure.
However, array can also mean a logical data type composed of a (typically ho-
mogeneous) collection of data items, with each data item identified by an index
number.
It is possible to implement arrays in many different ways.
For exam-
