Our instructor has shown has several examples of functions that process linked lists (Show All Items, Delete At, Insert As Head, Insert As Tail..)

Now, in those example I noticed that he was using different approaches of traversal. In some instances he would use

while(head !=0)
{
    head=head->link;
}

In other instances he uses to move from node to node.

while(head->link !=0)
{
    head=head->link;
}

This is confusing to me. Is there a reason to use one over the other for certain operations ?

• c++
• linked-list

The second variant will cause a segfault if head is initially NULL.

Other than that, the first variant will iterate N times (where N is the number of items in the list). The second variant will only iterate N-1 times.

The first variant will leave "head" pointing to a "null" value after traversal. The second variant assumes head must be pointing to a good (non-NULL) head value to start with, and will leave head pointing to an element with a null link. Thus the second variant is useful for finding the final element of the list, and the first variant is useful for counting the number of items in the list.

In the first case, he is covering the case where the list might be initially empty (head = nil). You would normally do any processing internal to the loop before the

 head = head->link 

line.

In the second case, presumably he knows the list is not initially empty. In this case you would normally do any processing after the

 head = head->link 

line, although you could, if there was a reason, do some before as well. Of course it is also possible that this is not a conscious decision, since professors are people too ;-)

The second example has two problems actually. Use the first, always.

The first problem is as Oli Charlesworth said, in that it will cause a null pointer dereference (segmentation fault) if the loop is entered with head being NULL.

The second problem is that any code between the top of the loop and the head=head->link; statement will not occur on the last node in the linked list. So if this update statement is at the end of the loop (that's the usual way of doing things), then the last node will be completely bypassed. So if your code was this:

while(head->link !=0)
{
    dostufftoNode(head);
    head=head->link;
}

Then the dostufftoNode() function would be called for every node EXCEPT the last one.

while(head !=0)
{
    head=head->link;
}

This will

1. check if head is not null
2. set head to head->link
3. go to one

this will iterate a total of n times

while(head->link !=0)
{
    head=head->link;
}

This will

1. check if head->link is not null
2. set head to head->link
3. go to one

this will iterate a total of n-1 times