Sams Teach Yourself C++ in 21 Days

After inserting the first node, program control resumes at line 214. Once again, the value

is evaluated. For illustration purposes, assume that the value 3 is entered. This causes a

new Dataobject to be created on line 218 and to be inserted into the list on line 219.

Once again, on line 200, the list passes the data to its HeadNode. The

HeadNode::Insert()method, in turn, passes the new value to whatever its myNexthap-

pens to be pointing to. As you know, it is now pointing to the node that contains the Data

object whose value is 15. This invokes the InternalNode::Insert()method on line 99.

On line 103, the InternalNodeuses its myDatapointer to tell its Dataobject (the one

whose value is 15 ) to call its Compare()method, passing in the new Dataobject (whose

value is 3 ). This invokes the Compare()method shown on line 43.

The two values are compared, and, because myValuewill be 15 and

theOtherData.myValuewill be 3 , the returned value will be kIsLarger. This causes pro-

gram flow to jump to the kIsLargercase on line 110.

A new InternalNodeis created for the new Dataobject. The new node points to the cur-

rent InternalNodeobject, 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 E.4.

884 Appendix E

FIGUREE.4

The linked list after the

second node is

inserted.

Data

Linked List

Head Node Tail Node

myHead myNext

Internal Node

myNext

myData Data

Internal Node

myNext

myData

In the third invocation of the loop, the customer adds the value 8. This is larger than 3 but

smaller than 15 , and so it should be inserted between the two existing nodes. Progress is

like the previous example, except that when the node whose object’s value is 3 does the

compare, rather than returning kIsLarger, it returns kIsSmaller(meaning that the object

whose value is 3 is smaller than the new object, whose value is 8 ). This causes the

InternalNode::Insert()method to branch to the kIsSmallercase on line 118. Rather

than creating a new node and inserting it, the InternalNodejust passes the new data on to

the Insertmethod of whatever its myNextpointer happens to be pointing to. In this case,

it invokes InsertNodeon the InternalNodewhose Dataobject’s value is 15.

33 0672327112_app_e.qxd 11/19/04 12:30 PM Page 884