Linked Data Structures - Java - page 785

position reference subsequent nodes in the list. As indicated in Display 15.19, the
node at location position is deleted by the following two lines of code:

previous.link = position.link;
position = position.link;

In Display 15.19, next( ) has been invoked twice, so position is referencing the
node with " shoes " and previous is referencing the node with "socks" .
To delete the node referenced by position , the link from the previous node is set to
position s link. As shown in Display 15.19, this removes the linked list's reference to that
node. The variable position is then set to the next node in the list to remove any references
to the deleted node. As far as the linked list is concerned, the old node is no longer on the
linked list. But the node is still in the computer's memory. If there are no longer any references
to the deleted node, then the storage that it occupies should be made available for other uses.
In many programming languages, you, the programmer, must keep track of items such as
deleted nodes and must give explicit commands to return their memory for recycling. This is
called garbage collecting or explicit memory management . In Java, this is done for you
automatically, or, as it is ordinarily phrased, Java has automatic garbage collection.
Note that there are special cases that must be handled for deletion. First, if the list is
empty, then nothing can be deleted and the delete( ) method throws an exception. Sec-
ond, if the node to delete is the head of the list, then there is no previous node to update.
Instead, head is set to head.link to bypass the first node in the list and set a new head node.
Display 15.20 shows the technique for adding a node. We want to add a new node
between the nodes named by previous and position . In Display 15.20, previous and
position are variables of type Node , and each contains a reference to a node indicated
with an arrow. Thus, the new node goes between the two nodes referenced by
previous and position . In Display 15.20, the method next( ) has been invoked
twice to advance previous to "orange juice" and position to "shoes" .
A constructor for the class Node does a lot of the work for us: It creates the new
node, adds the data, and sets the link field of the new node to reference the node
named by position . All this is done with the following:

garbage
collecting
explicit
memory
management

new Node(newData, position)

So that we can recognize the node with newData in it when we study Display 15.20,
let's assume that newData holds the string "socks" . The following gets us from the first
to the second picture:

temp = new Node(newData, position);

To finish the job, all we need to do is link the previous node to the new node. We
want to move the arrow to the node named by temp . The following finishes our job:

previous.link = temp;

The new node is inserted in the desired place, but the picture is not too clear. The
fourth picture is the same as the third one; we have simply redrawn it to make it neater.