By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,384 Members | 673 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,384 IT Pros & Developers. It's quick & easy.

Linked Lists and Copy Constructor

P: 3
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:

Expand|Select|Wrap|Line Numbers
  1. template<class T>
  2. class Node
  3. {
  4. public:
  5.      Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
  6.      Node<T>* getLink( ) const { return link; }
  7.      const T getData( ) const { return data; }
  8.      void setData(const T& theData) { data = theData; }
  9.      void setLink(Node<T>* pointer) { link = pointer; }
  10. private:
  11.      T data;
  12.      Node<T> *link;
  13. };
  14.  
  15. template<class T>
  16. class Stack
  17. {
  18. public:
  19.      Stack( );
  20.      //Initializes the object to an empty stack.
  21.  
  22.      Stack(const Stack<T>& aStack);
  23.  
  24.      Stack<T>& operator =(const Stack<T>& rightSide);
  25.  
  26.      virtual ~Stack( );
  27.  
  28.      void push(T stackFrame);
  29.      //Postcondition: stackFrame has been added to the stack.
  30.  
  31.      T pop( );
  32.      //Precondition: The stack is not empty.
  33.      //Returns the top stack frame and removes that top
  34.      //stack frame from the stack.
  35.  
  36.      bool isEmpty( ) const;
  37.      //Returns true if the stack is empty. Returns false otherwise.
  38. private:
  39.      Node<T> *top;
  40. };
  41.  
The definition given for the copy constructor:

Expand|Select|Wrap|Line Numbers
  1. template<class T>
  2. Stack<T>::Stack(const Stack<T>& aStack)
  3. {
  4.     if (aStack.isEmpty( ))
  5.         top = NULL;
  6.     else
  7.     {
  8.         Node<T> *temp = aStack.top; //temp moves
  9.              //through the nodes from top to bottom of aStack.
  10.         Node<T> *end;//Points to end of the new stack.
  11.  
  12.         end = new Node<T>(temp->getData( ), NULL);
  13.         top = end;
  14.          //First node created and filled with data.
  15.          //New nodes are now added AFTER this first node.
  16.  
  17.         temp = temp->getLink( ); //move temp to second node
  18.                      //or NULL if there is no second node.
  19.  
  20.         while (temp != NULL)
  21.         {
  22.              end->setLink(
  23.                        new Node<T>(temp->getData( ), NULL));
  24.              temp = temp->getLink( );
  25.              end = end->getLink( );
  26.         }
  27.          //end->link == NULL;
  28.     }
  29. }
  30.  
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 the node end is pointing to 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 the node top is pointing to 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 the copy of aStack.top, will not top->getLink( ) return NULL after the list has been copied with the above code rather than point to the second node?

In brief, why doesn't top change as end changes if it's pointing to the same node end is pointing to?

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.
Jan 13 '07 #1
Share this Question
Share on Google+
4 Replies


Ganon11
Expert 2.5K+
P: 3,652
Expand|Select|Wrap|Line Numbers
  1. template<class T>
  2. Stack<T>::Stack(const Stack<T>& aStack)
  3. {
  4.     if (aStack.isEmpty( ))
  5.         top = NULL;
  6.     else
  7.     {
  8.         Node<T> *temp = aStack.top; //temp moves
  9.              //through the nodes from top to bottom of aStack.
  10.         Node<T> *end;//Points to end of the new stack.
  11.  
  12.         end = new Node<T>(temp->getData( ), NULL);
  13.         top = end;
  14.          //First node created and filled with data.
  15.          //New nodes are now added AFTER this first node.
  16.  
  17.         temp = temp->getLink( ); //move temp to second node
  18.                      //or NULL if there is no second node.
  19.  
  20.         while (temp != NULL)
  21.         {
  22.              end->setLink(
  23.                        new Node<T>(temp->getData( ), NULL));
  24.              temp = temp->getLink( );
  25.              end = end->getLink( );
  26.         }
  27.          //end->link == NULL;
  28.     }
  29. }
  30.  
In brief, why doesn't top change as end changes if it's pointing to the same node end is pointing to?
At first, the pointer top is set to end, because end and top are the same Node (there is only one Node in the Stack). But then you are essentially assigning new values to end. top is not changed because you never change the address top holds.

I can understand where your confusion is coming from - however, let me try to explain using a simpler example.

Expand|Select|Wrap|Line Numbers
  1. int *p, *q;
  2. int x = 25, y = 36;
  3. p = &x;
  4. q = p; // q and p both point to same information
  5. cout << *p << " " << *q << endl; // prints 25 25
  6. *q = 49;
  7. cout << *p << " " << *q << endl; // prints 49 49
  8. p = &y;
  9. cout << *p << " " << *q << endl; // prints 36 49
When I changed *p or *q, I changed the value that p or q pointed to. p and q, themselves, did not change at all. Remember that pointers hold addresses of other variables. Changing the value of those variables does not change the pointer itself.

When I set q = p, they both point to the same space in memory. Thus, if I change that memory by using one pointer, the other pointer points to the new value, too. But what if I change the value of q, or p? I'm not changing the values these pointers point to - I'm changing the addresses they contain!

The same happens in your example. You are changing the address that end holds, not the data itself. end and top are two different pointers, each with their own address held inside. You use that address to initialize end, but afterwards, end and top have no connection. Changing the data held in end (the address of the last Node added) will never change the data held in top (the address of the first Node added).
Jan 13 '07 #2

P: 3
Please disregard this post. It turns out I was confusing the values of the pointers and the values of the nodes they are pointing to. The example makes sense now.
Jan 13 '07 #3

Ganon11
Expert 2.5K+
P: 3,652
D'oh, and just after I had typed a nice lengthy response.

Glad to see you got it on your own!
Jan 13 '07 #4

P: 3
top is not changed because you never change the address top holds.
Yeah, that's where I was confused. Thanks for the response!
Jan 13 '07 #5

Post your reply

Sign in to post your reply or Sign up for a free account.