Hello,

I'm still very new to C++ and have encountered some trouble in understanding how exactly the copy constructor for a stack class (given as an example in the book I've been learning from) using a linked list works.

The interface for the classes:

template<class T>
class Node
{
public:
     Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
     Node<T>* getLink( ) const { return link; }
     const T getData( ) const { return data; }
     void setData(const T& theData) { data = theData; }
     void setLink(Node<T>* pointer) { link = pointer; }
private:
     T data;
     Node<T> *link;
};

template<class T>
class Stack
{
public:
     Stack( );
     //Initializes the object to an empty stack.
    
     Stack(const Stack<T>& aStack);
    
     Stack<T>& operator =(const Stack<T>& rightSide);
    
     virtual ~Stack( );

     void push(T stackFrame);
     //Postcondition: stackFrame has been added to the stack.

     T pop( );
     //Precondition: The stack is not empty.
     //Returns the top stack frame and removes that top
     //stack frame from the stack.
   
     bool isEmpty( ) const;
     //Returns true if the stack is empty. Returns false otherwise.
private:
     Node<T> *top;
};

The definition given for the copy constructor:

template<class T>
Stack<T>::Stack(const Stack<T>& aStack)
{
    if (aStack.isEmpty( ))
        top = NULL;
    else
    {
        Node<T> *temp = aStack.top; //temp moves
             //through the nodes from top to bottom of aStack.
        Node<T> *end;//Points to end of the new stack.
       
        end = new Node<T>(temp->getData( ), NULL);
        top = end;
         //First node created and filled with data.
         //New nodes are now added AFTER this first node.
       
        temp = temp->getLink( ); //move temp to second node
                     //or NULL if there is no second node.

        while (temp != NULL)
        {
             end->setLink(
                       new Node<T>(temp->getData( ), NULL));
             temp = temp->getLink( );
             end = end->getLink( );
        }
         //end->link == NULL;
    }
}

Here is how I'm looking at it: temp is used to traverse the list being copied and end points to each node as it's copied, treating each as the current end of the list, but changing the link from NULL to the next node in the list if that node exists. After changing the link from NULL to the next node, end is then set to point to the node that was just copied, and the cycle is repeated until the end of the list is reached. Before the old list is traversed, the top of the new list is set to point to the copy of the node at the top of the old list with top = end; .

What I don't understand is this: As the link in end changes as well as the node end is pointing to changes while the old list is being copied, does this not also change the link in top as well as the node that top is pointing to? If top is meant to represent the top of the new list and point to a copy of aStack.top , will not top->getLink( ) return the same as end->link (that is, NULL ) rather than return the pointer to the second node after the list has been copied with the above code?

Forgive me if this seems very obvious; I'm still a novice. I'm not looking for alternate methods of defining the copy constructor. I really just want to understand how this example works and can't seem to grasp what's going on here.

Hello

Hi! :)

What I don't understand is this: As the link in end changes as well as the node end is pointing to changes while the old list is being copied, does this not also change the link in top as well as the node that top is pointing to? If top is meant to represent the top of the new list and point to a copy of aStack.top , will not top->getLink( ) return the same as end->link (that is, NULL ) rather than return the pointer to the second node after the list has been copied with the above code?

Think of end as a reference to a node rather than an actual node. The process of the copying goes like this.

temp
 |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL

top
end
 |
NULL



temp
 |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL

top
end
 |
[0] -> NULL



       temp
        |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL

top    end
 |      |
[0] -> [1] -> NULL



              temp
               |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL

top           end
 |             |
[0] -> [1] -> [2] -> NULL



                     temp
                      |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL

top                  end
 |                    |
[0] -> [1] -> [2] -> [3] -> NULL



                            temp
                             |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL

top                         end
 |                           |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL



DONE!
                                   temp
                                    |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL

top                         end
 |                           |
[0] -> [1] -> [2] -> [3] -> [4] -> NULL

Just remember that new nodes are constantly being added to end and end keeps getting shifted to the newly added node and you'll be fine. :)

Thanks for the response.

Just remember that new nodes are constantly being added to end and end keeps getting shifted to the newly added node and you'll be fine.

I understand that end is only a reference to the node and that it's being shifted as the nodes are copied, but what I don't understand is why top stays pointing to the first node after end shifts. With top = end; , this means that top is pointing to the same thing end is and would change whenever end changes, wouldn't it?

Thanks for the response.

My pleasure! :)

With top = end; , this means that top is pointing to the same thing end is and would change whenever end changes, wouldn't it?

This is that reference thing again. top and end are two different references to the same node. If you change the node, the changes will be mirrored by both references, but if you change one of the references to another node, the other reference will not be affected.

In situations like this, nothing beats a test. :)

#include <iostream>

int main()
{
  using namespace std;

  // mem represents two nodes
  int mem[2];
  // pa represents end and pb represents top
  int *pa = mem;
  int *pb = pa;

  cout << "   pa\t\t   pb\n";
  cout << pa << '\t' << pb << '\n';

  // Change end with top referring to the same node
  pa = &mem[1];

  cout << "\n   pa\t\t   pb\n";
  cout << pa << '\t' << pb << '\n';

  return 0;
}

When it comes to pointers, you have two attributes to think about. The first attribute is the value of the pointer. The value of any pointer is a memory address. Assigning to a pointer such as with top = end; modifies the value of the pointer. When working with values, pointers are no different than any other data type. No indirection occurs at this point, and if multiple pointers have the same address as their value and one has that address reassigned, the other pointers will not change. The effect is the same as if you were using integers.

int a = 10;
int b = a;

a = 15; // b is still 10

The second attribute of a pointer is the indirect value. This is the value stored at the address stored by a pointer. This is where indirection takes place and if multiple pointers have the same address as their value, any changes to the indirect value will be mirrored by all of the pointers. No doubt you know that the * operator lets you see the indirect value.

int a = 10;
int *pa = &a;
int *pb = pa;

++(*pa); // *pb is now 11 too

I think these multiple values are what make pointers so confusing. It only gets worse as you add levels of indirection, but once you understand the basic concept everything gets easier. Pointers are very consistent even when you add more indirect values.

This is that reference thing again. top and end are two different references to the same node. If you change the node, the changes will be mirrored by both references, but if you change one of the references to another node, the other reference will not be affected.

Ah ha, that's where I was confused. So, when end and top are both referencing node 1, that's the only time when a change to the node affects both pointers. end then shifts to the next node, and top remains pointing to node 1. The example makes perfect sense now.

So I was just confusing changes made in the values being pointed to with changes to the values of the pointers themselves.

It looks like I need more practice with pointers, but this clears things up a lot.

Thank you so much!

This article has been dead for over six months. Start a new discussion instead.