Java Reference
In-Depth Information
comparison of the two methods
16.3
Both the array and linked list versions run in constant time per operation.
Thus they are so fast that they are unlikely to be the bottleneck of any algo-
rithm and, in that regard, which version is used rarely matters.
The array versions of these data structures are likely to be faster than their
linked list counterparts, especially if an accurate estimation of capacity is
available. If an additional constructor is provided to specify the initial capac-
ity (see Exercise 16.2) and the estimate is correct, no doubling is performed.
Also, the sequential access provided by an array is typically faster than the
potential nonsequential access offered by dynamic memory allocation.
The array implementation does have two drawbacks, however. First, for
queues, the array implementation is arguably more complex than the linked
list implementation, owing to the combined code for wraparound and array
doubling. Our implementation of array doubling was not as efficient as possi-
ble (see Exercise 16.8), thus a faster implementation of the queue would
require a few additional lines of code. Even the array implementation of the
stack uses a few more lines of code than its linked list counterpart.
The second drawback affects other languages, but not Java. When doubling,
we temporarily require three times as much space as the number of data items
suggests. The reason is that, when the array is doubled, we need to have memory
to store both the old and the new (double-sized) array. Further, at the queue's peak
size, the array is between 50 percent and 100 percent full; on average it is 75 per-
cent full, so for every three items in the array, one spot is empty. The wasted space
is thus 33 percent on average and 100 percent when the table is only half full. As
discussed earlier, in Java, each element in the array is simply a reference. In other
languages, such as C++, objects are stored directly, rather than referenced. In
these languages, the wasted space could be significant when compared to the
linked list-based version that uses only an extra reference per item.
The array versus
linked list imple-
mentations
represent a classic
time-space
trade-off.
the java.util.Stack class
16.4
The Collections API provides a Stack class. The Stack class in java.util is
considered a legacy class and is not widely used. Figure 16.28 provides an
implementation.
 
 
 
Search WWH ::




Custom Search