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

We begin with the first add method. This method adds a new entry to the end of the list. Like
the statements in Segment 14.4, the following statements make this addition:
Node newNode = new Node(newEntry);
Node lastNode = getNodeAt(numberOfEntries);
lastNode.setNextNode(newNode);

Assuming that we have the private method getNodeAt , we can complete the method add as follows:
public void add(T newEntry)
{

Node newNode = new Node(newEntry);
if (isEmpty())
firstNode = newNode;
else

// add to end of nonempty list

{

Node lastNode = getNodeAt(numberOfEntries);
lastNode.setNextNode(newNode); // make last node reference new node
} // end if
numberOfEntries++;
} // end add

This method first creates a new node for the new entry. If the list is empty, it adds the new node
by making firstNode reference it. If the list is not empty, however, we must locate the end of the
list. Because we have a reference only to the first node, we must traverse the list until we locate the
last node and obtain a reference to it. We will call the private method getNodeAt , which we defined
in Segment 14.7, to accomplish this task. Since the data field numberOfEntries contains the size of
the list, and since we identify list entries by their positions within the list beginning with 1, the last
node is at position numberOfEntries . We need to pass this value to getNodeAt . Once getNodeAt
gives us a reference to the last node, we can set the last node's link to reference the new node.
Note that we must define isEmpty , since add calls it, and so we add it to our core group of
methods that we define first.

Adding at a Given Position Within the List
14.10

The second add method adds a new entry at a specified position within the list. After creating a new
node that newNode references, we see whether the existing list is empty. If it is, we add the new
node to the list by writing firstNode = newNode , as we did in the first add method. If the list is not
empty, we must consider two cases:
•

Case 1: Adding the entry to the beginning of the list

•

Case 2: Adding the entry at a position other than the beginning of the list
Segment 14.2 lists the following statements for an addition to the beginning of a list:

Node newNode = new Node(newEntry);
newNode.setNextNode(firstNode);
firstNode = newNode;
Recall that these statements apply whether the list is empty or not. Additions anywhere else are per-
formed by the statements shown in Segment 14.3:

Node newNode = new Node(newEntry);
Node nodeBefore = getNodeAt(newPosition - 1);
Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);