Java Reference
In-Depth Information
The following pseudocode establishes a new node for the given data—referenced by
newEntry
—and inserts it into the empty chain:
newNode
references a new instance of
Node
Place
newEntry
in
newNode
firstNode =
address of
newNode
Figure 14-1b shows the result of this operation. In Java, these steps appear as follows, where
newEntry
references the entry to be added to the list:
Node newNode =
new
Node(newEntry);
firstNode = newNode;
Notice that in Figure 14-1b,
firstNode
and
newNode
reference the same node. After the insertion of
the new node is complete, only
firstNode
should reference it. We could set
newNode
to
null
, but
as you will see,
newNode
will be a local variable of the method
add
. As such,
newNode
will not exist
after
add
ends its execution.
14.2
Case 2: Adding a node to the beginning of a chain.
This case should be familiar to you, as well.
The following pseudocode describes the steps needed to add a node to the beginning of a chain:
newNode
references a new instance of
Node
Place
newEntry
in
newNode
Set
newNode
's link to
firstNode
Set
firstNode
to
newNode
The new node is now the first node. Figure 14-2 illustrates these steps, and the following Java state-
ments implement them:
Node newNode =
new
Node(newEntry);
newNode.setNextNode(firstNode);
firstNode = newNode;
To simplify the figure, we have omitted the actual entries in the list. These entries are objects that
the nodes reference.
FIGURE 14-2
A chain of nodes (a) just prior to adding a node at the beginning;
(b) just after adding a node at the beginning
(a)
(b)
firstNode
firstNode
newNode
newNode
Note:
Recall that adding a node to an empty chain, as Figure 14-1 depicts, is actually the
same as adding a node to the beginning of a chain.
14.3
Case 3: Adding a node between adjacent nodes of a chain.
Because the ADT list allows addi-
tions between two existing entries, we must be able to add a node to a chain between two existing,
consecutive nodes. The necessary steps for this task are described by the following pseudocode:
newNode
references the new node
Place
newEntry
in
newNode
