3.3.2 Special Cases

It is evident that this code is correct for insertion into the interior of the list or at its end. Special cases must always be sniffed out and dealt with. By definition, a special case means a situation requiring code different from the current solution.The existing solution must be modified to handle special cases. The special case here, shown in Figure 3.6(b), represents insertion at the front of the list. Obviously there is no predecessor record, so the solution cannot properly handle this case. It is reasonable to assume that this special condition is represented by a null value for predecessor. Then it is the value of head that must be copied into the link field of the new record. Also, it is the head itself that must receive the copy of newpointer and end up pointing to the new record. The correct function to handle all situations is as follows:

>Comment

insert(phead,predecessor,newpointer)

/* Inserts, in list head, the record pointed to

by newpointer as the successor of the

record pointed to by predecessor.

*/

listpointer *phead,predecessor,newpointer;

{

listpointer setnull(),next();

if(predecessor == setnull())

{

>Comment

setlink(newpointer,*phead);

*phead = newpointer;

}

else

{

>Comment

setlink(newpointer,next(predecessor));

setlink(predecessor,newpointer);

}

}

Note: listpointer is a type which is explained in Sections 3.6.1 and 3.6.2.

where setnull returns the null value. What is used for the null value is determined by the list implementation (Section 3.6). When insert is invoked, its actual first parameter, corresponding to phead, must be a pointer to the head of the list. Thus to have insert work on a list l, the call would be insert (&1,predecessor,newpointer). Whenever a parameter of a function must return a value (be modified by the function) the convention in this text is to prefix the name of the parameter in the function definition with a p. Thus, since the value of the pointer to head in insert must be changed, it is referred to as phead. Notice that the code for insert refers to *phead. Think of *phead as another name for head. We say that head has been passed to insert by pointer.

This version of insert is independent of how the list is actually implemented. In practice, insert might be made to execute more efficiently by writing it so that its code does depend on the list implementation. Insert might then be the level at which the list implementation is hidden instead of in setnull, setlink, and next. However, the version above is clearer and can be readily modified if desired.