A List Implementation That Links Data - Data Structures and Abstractions with Java - page 338

Let nodeBefore reference the node that will be before the new node
Set nodeAfter to nodeBefore 's link
Set newNode 's link to nodeAfter
Set nodeBefore 's link to newNode

To indicate where in the chain the new node should be inserted, let's number the nodes, begin-
ning with 1. We need to locate the node at a given position within the chain and get a reference to it.
Suppose that the method getNodeAt performs this task for us. Since the method returns a reference
to a node, and the class Node will be an inner class of a class of lists, getNodeAt is an implementa-
tion detail that we would not want a client to use. Thus, getNodeAt should be a private method.
Let's specify getNodeAt as follows:
// Returns a reference to the node at a given position.
// Precondition: The chain is not empty;
// 1 <= givenPosition <= numberOfNodes
private Node getNodeAt( int givenPosition)

We can define the method later.
In the meantime, knowing only what getNodeAt does, and not how it does it, we can use it in
the implementation of the previous pseudocode. If newPosition is the number of the new node
after its insertion, the following Java statements add the new node to the chain:
Node newNode = new Node(newEntry);
Node nodeBefore = getNodeAt(newPosition - 1);
Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);

Figure 14-3a shows the chain after the first three statements execute, and Figure 14-3b shows
it after the node has been added. In this figure, newPosition is 3.

FIGURE 14-3

A chain of nodes (a) just prior to adding a node between two adjacent nodes;
(b) just after adding a node between two adjacent nodes

(a)

firstNode

nodeBefore

nodeAfter

newNode

(b)

firstNode

nodeBefore nodeAfter

newNode