Linked Lists - Building Java Programs: A Back to Basics Approach - page 933

The value null is used to represent the empty list. There are three nodes floating
around from the work we did earlier, but those are like helium balloons that have
floated away because their strings were let go. They will eventually be recycled by
the garbage collector.
You have to be careful about manipulating an empty list. For example, if the vari-
able list is null , and you execute code that refers to list.data , Java will halt
your program by throwing a NullPointerException . You will quickly discover that
NullPointerException is one of the most common problems that you run into as
you try to debug your linked list code. Just keep in mind that Java throws that excep-
tion when you attempt to dereference a null value. In other words, it occurs when
you ask for ptr.fieldName where ptr has the value null . When Java throws the
exception, it will show you the exact line number where it occurred. Look at that line
of code carefully to find all occurrences of the dot notation, because one of them
involves a null value.

Manipulating Nodes
In the next section we will explore how to use loops to write more generalized code,
but first it is useful to practice basic node manipulation. A good way to practice is to
make up an exercise that involves a “before” picture and an “after” picture. The chal-
lenge is to write code that gets you from the first state to the second state.
As an example, suppose that you have two variables of type ListNode called p
and q and that the following is the “before” situation:

data
2

next data

4

next
/ p

data
3

next data

9

next
/

q

Suppose that you want to get to the following “after” situation:

data
2

next data

4

next data

3

next
/

p

data
9

next
/ q

In order to accomplish this, you will have to rearrange the links of these two lists.
As a starting point, think about how many variables of type ListNode there are. You
might say two because there are two named variables, p and q . Or you might say four
because you notice that each of the four nodes has a field of type ListNode .
Actually, there are six different variables of type ListNode . The following diagram
numbers each of the six variables: