Java Reference
In-Depth Information
data
3
next
data
7
next
data
12
next
front
There are many applications in which it can be helpful to have the list point back
to the front in this manner. To manipulate such a list, you use very different code. You
can't test for
null
because there are no
null
links in the list. Instead, you test
whether you have returned to the point at which you started. It is often helpful to use
a
do/while
loop for processing a circular list. For example, the following code prints
the values of the list, one per line:
ListNode current = front;
do {
System.out.println(current.data);
current = current.next;
} while (current != front);
One of the tricky aspects of working with a circular list is dealing with an empty
list. The preceding code, for example, generates a
NullPointerException
if the
variable
list
has the value
null
.
This brings us to our second variation. It is often helpful to have extra nodes in the
list that do not store meaningful elements and that are not considered part of the list.
We refer to such a node as a
dummy node
. For example, in a circular list it is often
convenient to represent the empty list as a single dummy node that points back to
itself. Dummy nodes are useful even with the kind of null-terminated lists we have
been writing. By using a dummy header node, we represent the empty list as having
just the dummy node:
data
0
next
/
front
The
data
field in the preceding list stores
0
, but it doesn't matter what value
we store in the dummy node. The advantage of using a dummy header node is
that we no longer have to write special code to insert a value at the front of the
list. Now the front of the list will always be this dummy header node. For exam-
ple, if we were to insert the values
3
,
7
, and
12
, they would be inserted after the
dummy node:
data
0
next
data
3
next
data
7
next
data
12
next
/
front
Search WWH ::
Custom Search