Java Reference
In-Depth Information
FIGURE 3-10
A chain of nodes (a) just prior to removing the first node;
(b) just after removing the first node
(a)
firstNode
(b)
firstNode
Notice how we implement these steps in the following Java definition of remove :
public T remove()
{
T result = null ;
if (firstNode != null )
{
result = firstNode.data;
firstNode = firstNode.next; // remove first node from chain
numberOfEntries--;
} // end if
return result;
} // end remove
We first check whether the chain is empty by comparing firstNode with null . Note that we could
have called isEmpty instead. While accessing the data in the first node and decrementing the num-
ber of entries have straightforward expressions in Java, the entire effect of the statement
firstNode = firstNode.next;
might not be obvious. It should be clear by now that this statement makes firstNode reference the
second node in the chain, if such a node exists. But what if it doesn't? That is, what happens when
the chain contains only one node? In that case, firstNode.next is null , so the statement sets
firstNode to null , as required.
3.22
Removing a given entry. As the interface in Listing 1-1 of Chapter 1 specifies, a second method
remove removes a given entry and returns true or false according to the success of the operation:
/** Removes one occurrence of a given entry from this bag, if possible.
@param anEntry the entry to be removed
@return true if the removal was successful, or false otherwise */
public boolean remove(T anEntry)
If the bag is empty before the method executes, or if anEntry is not in the bag, the method returns false.
To remove a specific entry that is in a chain of linked nodes, we first must locate the entry. That
is, we must traverse the chain and examine the entries in the nodes. Suppose that we find the desired
entry in node N . From our previous discussion in Segment 3.20 about a classroom, we can see that if
node N is not first in the chain, we can remove its entry by taking the following steps:
1.
Replace the entry in node N with the entry in the first node.
2.
Remove the first node from the chain.
Search WWH ::




Custom Search