|
|
|
|
|
|
|
Thus, by the simple act of allocating a linked list on the stack the list is created, a head and a tail node are created, and their relationship is established, as illustrated in Figure 19.2. |
|
|
|
|
|
|
|
|
FIGURE 19.2
The linked list after it is created. |
|
|
|
|
|
|
|
|
Line 210 begins an infinite loop. The user will be prompted for values to add to the linked list. He can add as many values as he likes, entering 0 when he is finished. The code on line 214 evaluates the value entered; if it is 0, it breaks out of the loop. |
|
|
|
|
|
|
|
|
If the value is not 0 a new Data object is created on line 216, and that is inserted into the list on line 217. For illustration purposes, assume the user enters the value 15. This invokes the Insert method on line 196. |
|
|
|
|
|
|
|
|
The linked list immediately delegates responsibility for inserting the object to its head node. This invokes the method Insert on line 168. The head node immediately passes the responsibility to whatever node its myNext is pointing to. In this (first) case, it is pointing to the tail node. (Remember, when the head node was born, it created a link to a tail node). This therefore invokes the method Insert on line 140. |
|
|
|
|
|
|
|
|
TailNode::Insert knows that the object it has been handed must be inserted immediately before itselfthat is, the new object will be in the list right before the tail node. Therefore, on line 142 it creates a new InternalNode object, passing in the data and a pointer to itself. This invokes the constructor for the InternalNode object, shown on line 88. |
|
|
|
|
|
|
|
|
The InternalNode constructor does nothing more than initialize its Data pointer with the address of the Data object it was passed and its myNext pointer with the node's address it was passed. In this case, the node it will point to is the tail node. (Remember, the tail node passed in its own this pointer.) |
|
|
|
|
|
|
|
|
Now that the InternalNode has been created, the address of that internal node is assigned to the pointer dataNode on line 142, and that address is in turn returned from the TailNode::Insert() method. This returns us to HeadNode::Insert(), where the address of the InternalNode is assigned to the HeadNode's myNext pointer (on line 170). Finally, the HeadNode's address is returned to the linked list where, on line 198, it is thrown away (nothing is done with it because the linked list already knows the address of the head node). |
|
|
|
|
|
