Java Reference
In-Depth Information
Answers to Self-Review Exercises
21.1
a) referential. b) stack. c) predicate. d) first-in, first-out (FIFO). e) link. f) garbage col-
lection. g) queue. h) tree i) last-in, first-out (LIFO). j) binary. k) root. l) child or subtree.
m) leaf. n) inorder, preorder, postorder. o)
-d
. p) class loader. q)
-classpath
,
CLASSPATH
. r)
package
declaration.
21.2
It's possible to insert a node anywhere in a linked list and remove a node from anywhere in
a linked list. Nodes in a stack may be inserted only at the top of the stack and removed only from
the top.
21.3
A queue is a FIFO data structure that has references to both its head and its tail, so that
nodes may be inserted at the tail and deleted from the head. A stack is a LIFO data structure that
has a single reference to the stack's top, where both insertion and deletion of nodes are performed.
21.4
a) Classes allow us to create as many data structure objects as we wish.
b) Inheritance enables a subclass to reuse the functionality from a superclass. Public and
protected superclass methods can be accessed through a subclass to eliminate duplicate
logic.
c) Composition enables a class to reuse code by storing a reference to an instance of an-
other class in a field. Public methods of the instance can be called by methods in the
class that contains the reference.
21.5
The inorder traversal is
11 18 19 28 32 40 44 49 69 71 72 83 92 97 99
The preorder traversal is
49 28 18 11 19 40 32 44 83 71 69 72 97 92 99
The postorder traversal is
11 19 18 32 44 40 28 69 72 71 92 99 97 83 49
Exercises
21.6
(Concatenating Lists)
Write a program that concatenates two linked list objects of charac-
ters. Class
ListConcatenate
should include a
static
method
concatenate
that takes references to
both list objects as arguments and concatenates the second list to the first list.
21.7
(Inserting into an Ordered List)
Write a program that inserts 25 random integers from 0 to
100 in order into a linked-list object. For this exercise, you'll need to modify the
List<T>
class
(Fig. 21.3) to maintain an ordered list. Name the new version of the class
SortedList
.
21.8
(Merging Ordered Lists)
Modify the
SortedList
class from Exercise 21.7 to include a
merge
method that can merge the
SortedList
it receives as an argument with the
SortedList
that calls the
method. Write an application to test method
merge
.
21.9
(Copying a List Backward)
Write a
static
method
reverseCopy
that receives a
List<T>
as
an argument and returns a copy of that
List<T>
with its elements reversed. Test this method in an
application.
21.10
(Printing a Sentence in Reverse Using a Stack)
Write a program that inputs a line of text
and uses a stack to display the words of the line in reverse order.
21.11
(Palindrome Tester)
Write a program that uses a stack to determine whether a string is a
palindrome (i.e., the string is spelled identically backward and forward). The program should ignore
spaces and punctuation.
