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
them in a PDF document located at www.deitel.com/books/jhtp10/ .]
 
Search WWH ::




Custom Search