Sams Teach Yourself C++ in 21 Days

A Look at Linked Lists 885

E

The comparison is done again, and a new InternalNodeis created. This new

InternalNodepoints to the InternalNodewhose Dataobject’s value is 15 , and its

address is passed back to the InternalNodewhose Dataobject’s value is 3 , as shown on

line 119.

The net effect is that the new node is 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 point-

ers be properly adjusted.

What Have You Learned?

In a well-designed object-oriented program, no oneis in charge. Each object does its own little

job, and the net effect is a well-running machine.

The linked list has the single job of maintaining the head node. The head node immediately

passes new data to whatever it points to, without regard to what that might be.

The tail node creates a new node and inserts it whenever it is handed data. It knows only one

thing: If this came to me, it gets inserted right before me.

Internal nodes are marginally more complicated; they ask their existing object to compare itself

with the new object. Depending on the result, they then insert or they just pass it along.

Note that the internal node (InternalNodein the preceding listing) has no ideahow to do the

comparison; that is properly left to the object itself. All the internal node knows is to ask the

objects to compare themselves and to expect one of three possible answers. Given one answer,

it inserts; otherwise, it just passes it along, not knowing or caring where it will end up.

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