Sams Teach Yourself C++ in 21 Days

A Look at Linked Lists 883

E

TailNode::Insertknows that the object it has been handed must be inserted immedi-

ately before itself—that is, the new object will be in the list right before the tail node.

Therefore, on line 144 it creates a new InternalNodeobject, passing in the data and a

pointer to itself. This invokes the constructor for the InternalNodeobject, shown on

line 90.

The InternalNodeconstructor does nothing more than initialize its Datapointer with the

address of the Dataobject it was passed and its myNextpointer with the node’s address it

was passed. In this case, the node it points to is the tail node (remember, the tail node

passed in its own thispointer).

Now that the InternalNodehas been created, the address of that internal node is

assigned to the pointer dataNodeon line 144, and that address is in turn returned from

the TailNode::Insert()method. This returns us to HeadNode::Insert(), where the

address of the InternalNodeis assigned to the HeadNode’s myNextpointer (on line 172).

Finally, the HeadNode’s address is returned to the linked list where, on line 200, it is

thrown away (nothing is done with it because the linked list already knows the address of

the head node).

Why bother returning the address if it is not used? Insertis declared in the base class,

Node. The return value is needed by the other implementations. If you change the return

value of HeadNode::Insert(), you receive a compiler error; it is simpler just to return

the HeadNodeand let the linked list throw its address on the floor.

So what happened? The data was inserted into the list. The list passed it to the head. The

head, blindly, passed the data to whatever the head happened to be pointing to. In this

(first) case, the head was pointing to the tail. The tail immediately created a new internal

node, initializing the new node to point to the tail. The tail then returned the address of

the new node to the head, which reassigned its myNextpointer to point to the new node.

Hey! Presto! The data is in the list in the right place, as illustrated in Figure E.3.

FIGUREE.3

The linked list after the

first node is inserted.

Linked List

Head Node Tail Node

myHead myNext

Internal Node

myNext

myData Data

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