Java Reference
In-Depth Information
(a) Modify the code of Figure 4.8 to implement circular singly linked lists.
(b) Modify the code of Figure 4.15 to implement circular doubly linked
lists.
4.9 Section 4.1.3 states “the space required by the array-based list implementa-
tion is (n), but can be greater.” Explain why this is so.
4.10 Section 4.1.3 presents an equation for determining the break-even point for
the space requirements of two implementations of lists. The variables are D,
E, P, and n. What are the dimensional units for each variable? Show that
both sides of the equation balance in terms of their dimensional units.
4.11 Use the space equation of Section 4.1.3 to determine the break-even point for
an array-based list and linked list implementation for lists when the sizes for
the data field, a pointer, and the array-based list's array are as specified.
(a) The data field is eight bytes, a pointer is four bytes, and the array holds
twenty elements.
(b) The data field is two bytes, a pointer is four bytes, and the array holds
thirty elements.
(c) The data field is one byte, a pointer is four bytes, and the array holds
thirty elements.
(d) The data field is 32 bytes, a pointer is four bytes, and the array holds
forty elements.
4.12 Determine the size of an
int
variable, a
double
variable, and a pointer on
your computer.
(a) Calculate the break-even point, as a function of n, beyond which the
array-based list is more space efficient than the linked list for lists
whose elements are of type
int
.
(b) Calculate the break-even point, as a function of n, beyond which the
array-based list is more space efficient than the linked list for lists
whose elements are of type
double
.
4.13 Modify the code of Figure 4.19 to implement two stacks sharing the same
array, as shown in Figure 4.21.
4.14 Modify the array-based queue definition of Figure 4.27 to use a separate
Boolean member to keep track of whether the queue is empty, rather than
require that one array position remain empty.
4.15 A palindrome is a string that reads the same forwards as backwards. Using
only a fixed number of stacks and queues, the stack and queue ADT func-
tions, and a fixed number of
int
and
char
variables, write an algorithm to
determine if a string is a palindrome. Assume that the string is read from
standard input one character at a time. The algorithm should output
true
or
false
as appropriate.
4.16 Re-implement function
fibr
from Exercise 2.11, using a stack to replace
the recursive call as described in Section 4.2.4.
