Java Reference
In-Depth Information
To locate a particular node within a chain, we begin at the chain's first node and traverse the
chain from one node to another. We know that firstNode contains a reference to the first node in
the chain. That first node contains a reference to the second node in the chain, the second node con-
tains a reference to the third node, and so on.
We can use a temporary variable, currentNode , to reference the nodes one at a time as we tra-
verse the chain from the first node to the desired node. Initially, we set currentNode to firstNode
so that it references the first node in the chain. If we are seeking the first node, we are done. Other-
wise, we move to the next node by executing
currentNode = currentNode.getNextNode();
If we are seeking the second node, we are done. Otherwise, we move to the next node by
executing
currentNode = currentNode.getNextNode();
once again. We continue in this manner until we locate the node at the desired position within
the list.
The implementation for getNodeAt follows:
private Node getNodeAt( int givenPosition)
{
assert (firstNode != null ) &&
(1 <= givenPosition) && (givenPosition <= numberOfNodes);
Node currentNode = firstNode;
// traverse the chain to locate the desired node
for ( int counter = 1; counter < givenPosition; counter++)
currentNode = currentNode.getNextNode();
assert currentNode != null ;
return currentNode;
} // end getNodeAt
Within the for loop, currentNode should never become null if the method's precondition is
met. Thus, currentNode.getNextNode() never executes if currentNode is null . You can enable
the assert statements during the testing of getNodeAt to verify these claims.
Question 4 The statements in Segment 14.4 that add an entry to the end of a chain invoke
the method getNodeAt . Suppose that you use these statements repeatedly to create a chain
by adding entries to its end.
a.
How efficient of time is this approach?
b.
Is there a faster way to repeatedly add entries to the end of a chain? Explain.
Question 5 How does getNodeAt 's precondition prevent currentNode from
becoming null ?
Beginning the Implementation
Design Decision: The structure of the chain of linked nodes
Imagine that we have a collection of data from which we will create a list. That is, our data will be
the list's entries. If the data is in the order in which the entries will appear in the list, we create the
list by repeatedly adding the next entry to the end of the list.
 
 
Search WWH ::




Custom Search