Java Reference
In-Depth Information
9.
You can add a dummy head node, as Project 5 describes, to the beginning of a doubly linked chain. Modify the
implementation of the ADT list described in the previous project by adding a dummy head node to the chain.
10.
Define a class that is a linked implementation of the interface
FixedSizeListInterface
, as described in Project 8
of the previous chapter.
11.
Repeat any of the projects 1 through 5 and 8 through 15 in the previous chapter by either using a linked chain or
involving the class
LList
instead of the class
AList
.
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
To locate the
n
th
node in a chain,
getNodeAt
starts at the first node and counts nodes as it traverses the chain from
node to node, until it reaches the
n
th
one. The following pseudocode describes the steps in more detail:
currentNode = firstNode
for (counter = 1
to
n)
currentNode = currentNode.getNextNode()
1.
The desired node is at
currentNode
2.
Yes. With
newPosition
equal to
numberOfNodes + 1
,
nodeBefore
will reference the last node in the chain. More-
over,
nodeAfter
will be
null
, n
ewNode
's link field will be set to
null
, and the last node's link will reference the
new node.
3.
No. The statements given in Segment 14.4 do not assign a new value to
firstNode
. Also, when the chain is
empty,
numberOfNodes
is zero. The precondition of
getNodeAt
given in Segment 14.3 requires a positive argu-
ment. Even if you redesign
getNodeAt
, the empty chain will remain a special case.
4.
a.
This approach is inefficient of time, since each addition causes
getNodeAt
to traverse the chain from its begin-
ning until it locates the chain's last node. Thus, each addition depends on the length of the chain.
b.
Maintaining a tail reference would allow additions to the end of the chain to occur in O(1) time, that is, inde-
pendently of the length of the chain.
5.
Since the chain is not empty,
firstNode
is not
null
. Thus,
currentNode
's initial value is not
null
. The loop in
getNodeAt
can iterate no more than
numberOfNodes
-
1 times. After the first iteration,
currentNode
references the
second node. After the second iteration, it references the third node. If the loop were to iterate
numberOfNodes
-
1
times,
currentNode
would reference the last node. It would not be
null
.
6.
a.
assert
!isEmpty() && (newPosition > 1);
b.
getNodeAt(newPosition)
c.
No. Calling
getNodeAt
to get a reference to the node after the one that
nodeBefore
references results in another
traversal of the chain from its beginning. The expression
nodeBefore.getNextNode()
provides a much faster
way to get the required reference.
7.
It could be, but testing for an empty list is unnecessary. The first
if
statement ensures that the value of
newPosition
ranges from 1 to
numberOfEntries
+ 1. If the list is empty,
numberOfEntries
is 0, therefore
newPosition
must be 1. Since adding to an empty list is the same as adding to the beginning of any list, we
need not be concerned with empty lists.
8.
The first method
add
invokes
getNodeAt
only if the list is not empty. Thus, the argument
numberOfEntries
passed to
getNodeAt
is
itself. The second method
add
checks the validity of
newPosition
and then calls
getNodeAt
only if the list is not empty and
newPosition
> 1. It is possible for
newPosition
to equal
numberOfEntries
+ 1, but
since
getNodeAt
's argument is
newPosition
-
1, the argument's value is
≥
1 and
≤
≤
numberOfEntries
as required.
