21 Custom Generic Data
Structures
Objectives
In this chapter you’ll:
■Form linked data structures
using references, self-
referential classes, recursion
and generics.
■Create and manipulate
dynamic data structures, such
as linked lists, queues, stacks
Self-Review Exercises 2
Self-Review Exercises
21.1 Fill in the blanks in each of the following statements:
a) A self- class is used to form dynamic data structures that can grow and shrink
at execution time.
b) A(n) is a constrained version of a linked list in which nodes can be inserted
and deleted only from the start of the list.
c) A method that does not alter a linked list, but simply looks at it to determine whether
it’s empty, is referred to as a(n) method.
d) A queue is referred to as a(n) data structure because the first nodes inserted
are the first ones removed.
e) The reference to the next node in a linked list is referred to as a(n) .
f) Automatically reclaiming dynamically allocated memory in Java is called .
g) A(n) is a constrained version of a linked list in which nodes can be inserted
only at the end of the list and deleted only from the start of the list.
h) A(n) is a nonlinear, two-dimensional data structure that contains nodes with
two or more links.
i) A stack is referred to as a(n) data structure because the last node inserted is
the first node removed.
j) The nodes of a(n) tree contain two link members.
k) The first node of a tree is the node.
l) Each link in a tree node refers to a(n) or of that node.
m) A tree node that has no children is called a(n) node.
n) The three traversal algorithms we mentioned in the text for binary search trees are
o) When compiling types in a package, the javac command-line option speci-
fies where to store the package and causes the compiler to create the package’s directo-
ries if they do not exist.
p) The compiler uses a(n) to locate the classes it needs in the classpath.
q) The classpath for the compiler and JVM can be specified with the option to
the javac or java command, or by setting the environment variable.
r) There can be only one in a Java source-code file, and it must precede all other
declarations and statements in the file.
21.2 What are the differences between a linked list and a stack?
21.3 What are the differences between a stack and a queue?
21.4 Comment on how each of the following entities or concepts contributes to the reusability
of data structures:
a) Classes
b) Composition
21.5 Provide the inorder, preorder and postorder traversals of the binary search tree of Fig. 21.1.
ANS: The inorder traversal is
Exercises
NOTE: Solutions to the programming exercises are located in the ch21solutions folder.
Each exercise has its own folder named ex21_## where ## is a two-digit number represent-
ing the exercise number. For example, exercise 21.6’s solution is located in the folder ex-
21_06.
21.18 (Duplicate Elimination) In this chapter, we saw that duplicate elimination is straightfor-
ward when creating a binary search tree. Describe how you’d perform duplicate elimination when
using only a one-dimensional array. Compare the performance of array-based duplicate elimination
with the performance of binary-search-tree-based duplicate elimination.
Fig. 21.1 |Binary search tree with 15 nodes.
49
28
18 40 71 97
83
11 19 32 44 69 72 92 99
© 2018 Pearson Education, Inc., 330 Hudson Street, NY NY 10013. All rights reserved.
Exercises 4
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.11)?
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?