|
|
|
|
|
|
|
Set newNodePtr = new NodeType
Set component member of *newNodePtr = item
Set prevPtr = NULL
Set currPtr = head
WHILE item > component member of *currPtr
Set prevPtr = currPtr
Set currPtr = link member of *currPtr
Insert *newNodePtr between *prevPtr and *currPtr |
|
|
|
|
|
|
|
|
|
This algorithm is basically sound, but there are problems with it in special cases. If the new component is larger than all other components in the list, the event that stops the loop (finding a node whose component is larger than the one being inserted) does not occur. When the end of the list is reached, the While condition tries to dereference currPtr, which now contains NULL. On some systems, the program will crash. We can take care of this case by using the following expression to control the While loop: |
|
|
|
|
|
|
|
|
currPtr isn't NULL AND item > component member of *currPtr |
|
|
|
|
|
|
|
|
This expression keeps us from dereferencing the null pointer because C++ uses short-circuit evaluation of logical expressions. If the first part evaluates to FALSE-that is, if currPtr equals NULL-the second part of the expression, which dereferences currPtr, is not evaluated. |
|
|
|
|
|
|
|
|
There is one more point to consider in our algorithm: the special case when the list is empty or the new value is less than the first component in the list. Variable prevPtr remains NULL in this case, and *newNodePtr must be inserted at the top instead of between *prevPtr and *currPtr. |
|
|
|
|
|
|
|
|
The following function implements our algorithm with these changes incorporated. |
|
|
|
|
|
|
|
|
void OrdList::Insert( /* in */ ComponentType item )
// Precondition:
// component members of list nodes are in ascending order
// && item is assigned
// Postcondition:
// New node containing item is inserted into its proper place
// in linked list
// && component members of list nodes are in ascending order
{ |
|
|
|
|
|