Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 102

HEAD CURR TAIL

20 23 12 15

(A)

HEAD CURR TAIL

20 23 10 12 15

(B)

Figure4.5 Illustration of a faulty linked-list implementation where curr points
directly to the current node. (a) Linked list prior to inserting element with
value 10. (b) Desired effect of inserting element with value 10.

constructor the same for both variants. Because the linked list class does not need
to declare a fixed-size array when the list is created, this parameter is unnecessary
for linked lists. It is ignored by the implementation.
A key design decision for the linked list implementation is how to represent
the current position. The most reasonable choices appear to be a pointer to the
current element. But there is a big advantage to making curr point to the element
preceding the current element.
Figure 4.5(a) shows the list's curr pointer pointing to the current element. The
vertical line between the nodes containing 23 and 12 indicates the logical position
of the current element. Consider what happens if we wish to insert a new node with
value 10 into the list. The result should be as shown in Figure 4.5(b). However,
there is a problem. To “splice” the list node containing the new element into the
list, the list node storing 23 must have its next pointer changed to point to the new
node. Unfortunately, there is no convenient access to the node preceding the one
pointed to by curr .
There is an easy solution to this problem. If we set curr to point directly to
the preceding element, there is no difficulty in adding a new element after curr .
Figure 4.6 shows how the list looks when pointer variable curr is set to point to the
node preceding the physical current node. See Exercise 4.5 for further discussion
of why making curr point directly to the current element fails.
We encounter a number of potential special cases when the list is empty, or
when the current position is at an end of the list. In particular, when the list is empty
we have no element for head , tail , and curr to point to. Implementing special
cases for insert and remove increases code complexity, making it harder to
understand, and thus increases the chance of introducing a programming bug.
These special cases can be eliminated by implementing linked lists with an
additional header node as the first node of the list.

This header node is a link