|
|
|
|
|
|
|
A new InternalNode is created for the new Data object. The new node will point to the current InternalNode object, and the new InternalNode's address is returned from the InternalNode::Insert() method to the HeadNode. Thus, the new node, whose object's value is smaller than the current node's object's value, is inserted into the list, and the list now looks like Figure 19.4. |
|
|
|
|
|
|
|
|
FIGURE 19.4
The linked list after the second node is inserted. |
|
|
|
|
|
|
|
|
In the third invocation of the loop, the customer adds the value 8. This is larger than 3 but smaller than 15, and so should be inserted between the two existing nodes. Progress will be exactly like the previous example except that when the node whose object's value is 3 does the compare, rather than returning kIsLarger, it will return kIsSmaller (meaning that the object whose value is 3 is smaller than the new object, whose value is 8). |
|
|
|
|
|
|
|
|
This will cause the InternalNode::Insert() method to branch to line 117. Rather than creating a new node and inserting it, the InternalNode will just pass the new data on to the Insert method of whatever its myNext pointer happens to be pointing to. In this case, it will invoke InsertNode on the InternalNode whose Data object's value is 15. |
|
|
|
|
|
|
|
|
The comparison will be done again, and a new InternalNode will be created. This new InternalNode will point to the InternalNode whose Data object's value is 15, and its address will be passed back to the InternalNode whose Data object's value is 3, as shown on line 117. |
|
|
|
|
|
|
|
|
The net effect is that the new node will be inserted into the list at the right location. |
|
|
|
|
|
|
|
|
If at all possible, you'll want to step through the insertion of a number of nodes in your debugger. You should be able to watch these methods invoke one another, and the pointers be properly adjusted. |
|
|
|
|
|
