|
|
|
|
|
|
|
NodePtr currPtr; // Moving pointer
NodePtr prevPtr; // Pointer to node before *currPtr
NodePtr newNodePtr; // Pointer to new node
// Set up node to be inserted
newNodePtr = new NodeType;
newNodePtr->component = item;
// Find previous insertion point
prevPtr = NULL;
currPtr = head;
while (currPtr != NULL && item > currPtr->component)
{
// Invariant (prior to test):
// item > component member of each list node
// before *currPtr
// && currPtr points to a list node or == NULL
// && prevPtr points to node before *currPtr or == NULL
prevPtr = currPtr;
currPtr = currPtr->link;
}
// Insert new node
newNodePtr->link = currPtr;
if (prevPtr == NULL)
head = newNodePtr;
else
prevPtr->link = newNodePtr;
} |
|
|
|
|
|
|
|
|
Let's go through this code for each of the three cases: inserting at the top (item is 20), inserting in the middle (item is 60), and inserting at the end (item is 100). Each insertion begins with the list below. |
|
|
|
|
|
