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

14.6

Case 2: Removing a node other than the first one. In the second case, we remove a node at a
position other than the beginning of the chain. Here are the steps to take:
Let nodeBefore reference the node before the one to be removed.
Set nodeToRemove to nodeBefore 's link; nodeToRemove now references the node to be
removed.
Set nodeAfter to nodeToRemove 's link; nodeAfter now references the node after the one to be
removed.
Set nodeBefore 's link to nodeAfter . ( nodeToRemove is now disconnected from the chain.)
Set nodeToRemove to null .
Since references to the disconnected node no longer exist, the system automatically recycles
its memory.

The following Java statements implement these steps, assuming that the node to remove is at posi-
tion givenPosition :

Node nodeBefore = getNodeAt(givenPosition - 1);
Node nodeToRemove = nodeBefore.getNextNode();
Node nodeAfter = nodeToRemove.getNextNode();
nodeBefore.setNextNode(nodeAfter);
nodeToRemove = null ;
Figure 14-6a illustrates the chain after the first three statements execute, and Figure 14-6b
shows it after the node is removed.

FIGURE 14-6

A chain of nodes (a) just prior to removing an interior node;
(b) just after removing an interior node

(a)

nodeBefore nodeToRemove nodeAfter

(b)

nodeBefore nodeToRemove

nodeAfter

The Private Method getNodeAt
14.7

The previous operations on a chain depended on the method getNodeAt , which returns a reference
to the node at a given position within the chain. Recall the specifications for this method:

// Returns a reference to the node at a given position.
// Precondition: The chain is not empty;
// 1 <= givenPosition <= numberOfNodes
private Node getNodeAt( int givenPosition)