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

Question 2 The code that we developed in Segment 14.3 to add a node between two adja-
cent nodes of a chain is

Node newNode = new Node(newEntry);
Node nodeBefore = getNodeAt(newPosition - 1);
Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);
Is it possible to use this code instead of the following code, which we just developed, to add a
node to the end of a chain? Explain your answer.

Node newNode = new Node(newEntry);
Node lastNode = getNodeAt(numberOfNodes);
lastNode.setNextNode(newNode);

Question 3 Adding a node to an empty chain could be thought of as adding a node to the
end of a chain that is empty. Can you use the statements in Segment 14.4 instead of

Node newNode = new Node(newEntry);
firstNode = newNode;
which we developed in Segment 14.1 to add a node to an empty chain? Why or why not?

Removing a Node from Various Positions
To remove a node at a specified position within a nonempty chain, we must consider two cases:

• Case 1: Removing the first node

•

Case 2: Removing a node other than the first one

14.5

Case 1: Removing the first node. This case should be familiar to you, as we removed the first
node in the linked implementations of the ADTs bag, stack, queue, deque, and priority queue. The
steps to take are
Set firstNode to the link in the first node.
Since references to the first node no longer exist, the system automatically recycles its
memory.

Figure 14-5 illustrates these steps, and the following Java statement implements them:
firstNode = firstNode.getNextNode();

FIGURE 14-5

A chain of nodes (a) just prior to removing the first node;
(b) just after removing the first node

(a)

firstNode

(b)

firstNode