Saturday, 12 October 2013

Linked Lists - copy constructor, depth(), reverse()

What a busy week with tests, assignments, and co-op interviews... Anyway, here is my
solution to the copy constructor, depth(), and reverse() function for Fardad's challenge
of the week. Each week things are getting a little bit more interesting. 


/* 
  copy constructor
  
  1. Create temporary node pointer (for cycling) and copy top 
     node pointer of source
  2. Create temporary node pointer (for cycling) for destination 
     and create new Node with source data (this will be the top node)
  3. Mark down the top node
  4. Cycle through the nodes in a way that makes dest 
     become the pointer for the next new node as the data copies over.    
*/


Stack::Stack(const Stack& S)
{
    Node* src = S._top;
    Node* dest = new Node(src->_data);
    _top = dest;

    while (src->_next != 0) {
      src = src->_next;
      dest->_next = new Node(src->_data);
      dest = dest->_next;
    }
}

----------------------------------------------------------------

/* 
  depth()
  
  1. Create temporary variable to mark the level of depth
  2. Create a temporary node pointer to cycle through the nodes
  3. Cycle through the nodes while marking down the depth
  4. Return the depth level   
*/


unsigned int Stack::depth()
{
    unsigned int lvl = 0;
    Node* top = _top;

    while (top) {
      lvl++;
      top = top->_next;
    }
    return lvl;
}

----------------------------------------------------------------

/* 
  reverse()
  
  1. Create temporary node pointer to a new node and pop the 
     first node while retrieving data (this is your new bottom node)
  2. Cycle through all the nodes, popping all the previous nodes 
     and creating new nodes with their data and using a pointer
     to the current instance and immediately assigning it to a
     new instance(this will reverse the order and destroy the 
     previous nodes)
  3. Copy the pointer to the top of your new reversed list
*/


void Stack::reverse()
{
    Node* temp = new Node(pop());

    while (!isEmpty()) {
      temp = new Node(pop(), temp);
    }
    _top = temp;
}

6 comments:

Dimple Amin said...

Where you call copy constructor?Can you please tell??
--Dimple

wongbsn said...

The copy constructor is called when you try to instantiate an object by using the attribute values of another object of similar type.

Stack A;
Stack B = A;

Hope that helps.

Dimple Amin said...

So basically we need to implement equal operator too,don't we?

wongbsn said...

Not for the above example. The copy constructor is used to instantiate a new instance with an old (already existing) instance of an object. In the above example, Stack B is in the process of being created. The operator= is used to change an already existing instance of an object.

Stack A;
Stack B = A; // Calls copy constructor, B does not exist yet
B = A; // Calls overloaded operator=, B exists, another way of writing it is B.operator=(A)

For the that last line, yes you would want to code operator=.

Dimple Amin said...
This comment has been removed by the author.
Dimple Amin said...

That makes sense. Thank you so much

Post a Comment