473,326 Members | 2,182 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Linked Lists and Copy Constructor

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
4 5089
Ganon11
3,652 Expert 2GB
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
Beow
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
3,652 Expert 2GB
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
Beow
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

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

Similar topics

7
by: Chris Ritchey | last post by:
Hmmm I might scare people away from this one just by the title, or draw people in with a chalange :) I'm writting this program in c++, however I'm using char* instead of the string class, I am...
2
by: Dave | last post by:
Hello all, I am creating a linked list implementation which will be used in a number of contexts. As a result, I am defining its value node as type (void *). I hope to pass something in to its...
1
by: Booser | last post by:
// Merge sort using circular linked list // By Jason Hall <booser108@yahoo.com> #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> //#define debug
3
by: s_subbarayan | last post by:
Dear all, 1)In one of our implementation for an application we are supposed to collate two linked lists.The actual problem is like this: There are two singularly linked lists, the final output...
6
by: paudirac | last post by:
Hi, I need to maintain N linked lists where N is determined at runtime. The linked lists are defined as follows, struct linked_list { int data; struct linked_list next; }
4
by: MJ | last post by:
Hi I have written a prog for reversing a linked list I have used globle pointer Can any one tell me how I can modify this prog so that I dont have to use extra pointer Head1. When I reverse a LL...
13
by: B. Williams | last post by:
I have written some code to accept input and place this input at the beginning or end of a list, but I need assistance including a class so that it will allow input of a phone number that is...
51
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort...
10
by: AZRebelCowgirl73 | last post by:
This is what I have so far: My program! import java.util.*; import java.lang.*; import java.io.*; import ch06.lists.*; public class UIandDB {
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.