Ch.7

Question 1

…the very different nature of these two fundamental data structures.
Locations within an array are easily described with an integer [i..x]. Recall
that an index of an element e in a sequence is equal to the number of elements
before e in that sequence. By this definition, the first element of a sequence has
index 0, and the last has index n−1, assuming that n denotes the total number of
elements. The notion…

Answer 1

[index] 258

Question 2

With that said, Java defines a general interface, java.util.List, that includes the
following index-based methods (and more):
size( ): Returns the number of [e..s] in the list.
isEmpty( ): Returns a boolean [i..g] whether the list is empty.
get(i): Returns the element of the list [h..g] index i; an error condition
occurs if i is not in range [0, size( )−1].
set(i, e): Replaces the element at index i with e, and [r..s] the old element
that was replaced; an error condition occurs if i is not in range
[0, size( )−1].
add(i, e): Inserts a new element e into the list so that it has index i, moving
all [s..t] elements one index later in the list; an error
condition occurs if i is not in range [0, size( )].
remove(i): Removes and returns the element at index i, moving all subsequent
elements one index earlier in the [l..t]; an error condition
occurs if i is not in range [0, size( )−1].
We note that the index of an existing element may change over time, as other
elements are added or removed in front of it.

Answer 2

[elements][indicating][having][removes][subsequent][list] 258

Question 3

…effectively allows an array-based list to have unbounded capacity. Such an unbounded list is known as an [a..y l..t] in Java (or a vector in C++ and in the
earliest versions of Java).
With a representation based on an array A, the get(i) and set(i, e) methods are easy to implement by accessing A[i] (assuming i is a legitimate index). Methods add(i, e) and remove(i) are more time…

Answer 3

[array list] 260

Question 4

…no apparent limit on the overall capacity. To provide
this abstraction, Java relies on an algorithmic sleight of hand that is known as a [d..c a..y].
In reality, elements of an ArrayList are stored in a traditional array, and the precise size of that traditional array must be internally declared in order for the
system to properly allocate a consecutive piece of memory for its storage. For example, Figure 7.2 displays an array with 12 cells…

Answer 4

[dynamic array] 263

Question 5

… As a shorthand notation, let us refer to the insertion of an element to be the last element in an array list as a [p..h] operation.
The strategy of replacing an array with a new, larger..

Answer 5

[push] 265

Question 6

Using an algorithmic process called [a..n], we show that performing a sequence of push operations on a dynamic array is actually quite efficient. To
perform an [a..d a..s], we use an accounting technique where we view
the computer as a coin-operated … one [c..r]
for a constant amount of computing time.

Answer 6

[amortization][amortized analysis][cyberdollar] 266

Question 7

Java provides many data structure interfaces and classes, which together form the
[J..a C..s F..k]. This framework, which is part of the java.util package, includes versions of several of the data structures discussed in this book, some
of which we have already discussed and others of which we will discuss later in
this book. The root interface in the Java collections framework is named Collection.
This is a general interface for any data structure, such as a list, that represents a…

Answer 7

[Java Collections Framework] 288

Question 8

… Some classes enforce, or allow, a fixed
capacity limit. Robust classes provide support for [c..y], allowing multiple
processes to share use of a data structure in a thread-safe manner. If the structure
is designated as [b..g], a call to retrieve an element from an empty collection waits until some other process inserts an element… It views its current
position as being before the first element, between two elements, or after the last element. That is, it uses a list [c..r], much like a screen cursor is viewed as being located between two characters on a screen. Specifically, the java.util.ListIterator interface includes…

Answer 8

[concurrency][blocking][cursor] 288&289