Java Reference
In-Depth Information
(
removeFromFront
) and 21.9 (
removeFromBack
) that show how to insert a new node in the middle
of a linked list and how to remove an existing node from the middle of a linked list.
21.27
(Lists and Queues without Tail References)
Our linked-list implementation (Fig. 21.3) used
both a
firstNode
and a
lastNode
. The
lastNode
was useful for the
insertAtBack
and
removeFrom-
Back
methods of the
List
class. The
insertAtBack
method corresponds to the
enqueue
method of
the
Queue
class. Rewrite the
List
class so that it does not use a
lastNode
. Thus, any operations on
the tail of a list must begin searching the list from the front. Does this affect our implementation of
the
Queue
class (Fig. 21.13)?
21.28
(Performance of Binary Tree Sorting and Searching)
One problem with the binary tree sort
is that the order in which the data is inserted affects the shape of the tree—for the same collection
of data, different orderings can yield binary trees of dramatically different shapes. The performance
of the binary tree sorting and searching algorithms is sensitive to the shape of the binary tree. What
shape would a binary tree have if its data were inserted in increasing order? in decreasing order?
What shape should the tree have to achieve maximal searching performance?
21.29
(Indexed Lists)
As presented in the text, linked lists must be searched sequentially. For large
lists, this can result in poor performance. A common technique for improving list-searching perfor-
mance is to create and maintain an index to the list. An index is a set of references to key places in
the list. For example, an application that searches a large list of names could improve performance
by creating an index with 26 entries—one for each letter of the alphabet. A search operation for a
last name beginning with 'Y' would then first search the index to determine where the 'Y' entries
began, then “jump into” the list at that point and search linearly until the desired name was found.
This would be much faster than searching the linked list from the beginning. Use the
List
class of
Fig. 21.3 as the basis of an
IndexedList
class. Write a program that demonstrates the operation of
indexed lists. Be sure to include methods
insertInIndexedList
,
searchIndexedList
and
delete-
FromIndexedList
.
21.30
(Queue Class that Inherits from a List Class)
In Section 21.5, we created a stack class from
class
List
with inheritance (Fig. 21.10) and with composition (Fig. 21.12). In Section 21.6 we cre-
ated a queue class from class
List
with composition (Fig. 21.13). Create a queue class by inheriting
from class
List
. What are the differences between this class and the one we created with composi-
tion?
Special Section: Building Your Own Compiler
In Exercises 7.36-7.38, we introduced Simpletron Machine Language (SML), and you imple-
mented a Simpletron computer simulator to execute SML programs. In Exercises 21.31-21.35, we
build a compiler that converts programs written in a high-level programming language to SML.
This section “ties” together the entire programming process. You'll write programs in this new
high-level language, compile them on the compiler you build and run them on the simulator you
built in Exercise 7.37. You should make every effort to implement your compiler in an object-ori-
ented manner. [
Note:
Due to the size of the descriptions for Exercises 21.31-21.35, we've posted