Answers to Self-Test Exercises

1. 1.

      Sally
      Sally
      18
      18
   

   Note that (*head).name and head->name mean the same thing. Similarly, (*head).number and head->number mean the same thing

2. 2.

   The best answer is
   head->next = NULL;
   

   However, the following is also correct:

   (*head).next = NULL;
   

3. 3.

   delete head;
   

4. 4.

   head->item = "Wilbur's brother Orville";

5. 5.

   struct NodeType
   {
       char data;
       NodeType *link;
   };
   typedef NodeType* PointerType;
   

6. 6. The pointer value NULL is used to indicate an empty list.

7. 7. p1 = p1-> next;

8. 8.

   Pointer discard;
   discard = p2->next;
   //discard now points to the node to be deleted.
   p2->next = discard->next;
   

   This is sufficient to delete the node from the linked list. However, if you are not using this node for something else, you should destroy the node with a call to delete as follows:

   delete discard;
   

9. 9.

   1. Inserting a new item at a known location into a large linked list is more efficient than inserting into a large array. If you are inserting into a list, you have about five operations, most of which are pointer assignments, regardless of the list size. If you insert into an array, on the average you have to move about half the array entries to insert a data item.

   For small lists, the answer is (c), about the same.

10. 10.

    //Uses cstddef:
    void Stack::push(char theSymbol)
    {
        StackFramePtr tempPtr;
        tempPtr = new StackFrame;
        tempPtr->data = theSymbol;
        tempPtr->link = top;
        top = tempPtr;
    }
    

11. 11.

    //Uses cstddef:
    Stack::Stack(const Stack& aStack)
    {
        if (aStack.top == NULL)
            top = NULL;
        else
        {
            StackFramePtr temp = aStack.top;//temp moves
                //through the nodes from top to bottom of
                //aStack.
            StackFramePtr end;//Points to end of the new stack.
            end = new StackFrame;
            end->data = temp->data;
            top = end;
            //First node created and filled with data.
            //New nodes are now added AFTER this first node.
            temp = temp->link;
            while (temp != NULL)
            {
                end->link = new StackFrame;
                end = end->link;
                end->data = temp->data;
                temp = temp->link;
            }
            end->link = NULL;
        }
    }
    

12. 12.

    //Uses cstddef:
    Queue::Queue(const Queue&aQueue)
    {
        if (aQueue.empty( ))
            front = back = NULL;
        else
        {
            QueueNodePtr tempPtrOld = aQueue.front;
            //tempPtrOld moves through the nodes
            //from front to back of aQueue.
            QueueNodePtr tempPtrNew;
            //tempPtrNew is used to create new nodes.
            back = new QueueNode;
            back->data = tempPtrOld->data;
            back->link = NULL;
            front = back;
            //First node created and filled with data.
            //New nodes are now added AFTER this first node.
            tempPtrOld = tempPtrOld->link;
            //tempPtrOld now points to second
            //node or NULL if there is no second node.
            while (tempPtrOld != NULL)
            {
                tempPtrNew = new QueueNode;
                tempPtrNew->data = tempPtrOld->data;
                tempPtrNew->link = NULL;
                back->link = tempPtrNew;
                back = tempPtrNew;
                tempPtrOld = tempPtrOld->link;
            }
        }
    }
    

13. 13.

    Queue::~Queue( )
    {
        char next;
        while (! empty( ))
            next = remove( );//remove calls delete.
    }