Java Reference
In-Depth Information
A header node
holds no data but
serves to satisfy the
requirement that
every node have a
previous node. A
header node allows
us to avoid special
cases such as
insertion of a new
first element and
removal of the first
element.
previous node in the list. The header node for the list a , b , c is shown in
Figure 17.4. Note that a is no longer a special case. It can be deleted just
like any other node by having current reference the node before it. We can
also add a new first element to the list by setting current equal to the header
node and calling the insertion routine. By using the header node, we greatly
simplify the code—with a negligible space penalty. In more complex appli-
cations, header nodes not only simplify the code but also improve speed
because, after all, fewer tests mean less time.
The use of a header node is somewhat controversial. Some argue that
avoiding special cases is not sufficient justification for adding fictitious
cells; they view the use of header nodes as little more than old-style hack-
ing. Even so, we use them here precisely because they allow us to demon-
strate the basic link manipulations without obscuring the code with special
cases. Whether a header should be used is a matter of personal preference.
Furthermore, in a class implementation, its use would be completely trans-
parent to the user. However, we must be careful: The printing routine must
skip over the header node, as must all searching routines. Moving to the
front now means setting the current position to header.next , and so on. Fur-
thermore, as Figure 17.5 shows, with a dummy header node, a list is empty
if header.next is null .
17.1.2 iterator classes
The typical primitive strategy identifies a linked list by a reference to the
header node. Each individual item in the list can then be accessed by provid-
ing a reference to the node that stores it. The problem with that strategy is that
figure 17.4
Using a header node
for the linked list
a
b
c
header
figure 17.5
Empty list when a
header node is used
header
 
 
Search WWH ::




Custom Search