MVNU Computer Science II - Lab 6: Deep Copies and Destructors

Spring 2010


In this lab you are going to look at some of the issues that arise from using dynamic memory. The first relates to copying an existing object that has attributes in dynamic memory. This issue relates to both C++ and Java. The second issue concerns cleaning up allocated dynamic memory when it is no longer needed, this is something that is done automatically for you by Java.


Deep and Shallow Copies

A shallow copy of an object is one where only the addresses of data created in dynamic memory have been copied, rather than the data themselves. A deep copy of an object is one where new dynamic memory has been allocated to create copies of any dynamically allocated data (rather than just copies of the pointers to those data).

The consequence of creating a shallow copy is that any dynamically created data is not actually copied, so that changes to one version are reflected in changes to the other.


Part 1 - Experiment

Create a new project with a .cpp file with a main method.

Create new LinkedList and Node classes and copy the .h and a .cpp files below into them. I've also provided you with a simple test function that:

  • Creates a new linked list
  • Inserts some data into it
  • Uses the copy constructor to create a second list
  • Makes changes to the original linked list
  • Prints both lists
Call this test function in your main method and satisfy yourself that the copy constructor is making a shallow copy, and that there is, in fact, only one list.

Test Function

#include <string>
#include <iostream>
#include "linkedlist.h"
using namespace std;
void main(){
   LinkedList ls1;
   ls1.add(1);
   ls1.add(2);
   ls1.add(3);
   cout << "Print first list: {1,2,3}" << endl;
   ls1.printList();

   cout << endl << "Make a copy of the list" << endl;
   LinkedList ls2(ls1);
   ls1.add(4);
   ls1.add(5);
   ls1.add(6);

   cout << endl << "Add items and print first list: {1,2,3,4,5,6}" << endl;
   ls1.printList();
   cout << endl << endl << "Print second list, if it was deep copied should be: {1,2,3}" << endl;
   ls2.printList();
   cout << endl << endl;
}

Part 2 - Deep Copy

Change the copy constructor so that it creates a deep copy of the list. Use your test program from Part 1 to satisfy yourself that the copy constructor is making a deep copy (i.e. that changes made in one of the lists are not reflected in the other list).


Destructors

Every class that uses dynamic memory (like this one) requires a destructor to de-allocate the dynamic memory when it is no longer needed. The destructor is not called directly but it is invoked whenever an object is deleted (using delete), and on various system events (such as the program terminating). If dynamic memory is not de-allocated it cannot be re-used (until the application terminates) which results in what is known as a memory leak.

The destructor should destroy (using delete) all dynamically created objects (that is, all objects created using new).

Part 3 - Destructor

Write the destructor for the linked list class. The destructor should traverse the list using delete to delete each node in turn. Note that you never directly call a destructor, it is called for you if you call delete, or automatically on objects when the program terminates.

Testing Your Destructor

Seeing the the distructor works can be a little tricky. How do you know if you correctly deallocated the space?

For this LAB, modify the destructor to display each node as it is deleted.

Linked List Class

This is a simple linked list class allows nodes to be added to the end of the list, and allows the list to be printed. The copy constructor performs a shallow copy and the destructor has not been implemented.

Header file

#pragma once

// LinkedList.h
// Header file for linked list class
#include "Node.h"

class LinkedList{
public:
   // Constructors and Destructors
   /* Generally every class should have at least two construtors, a
    * default constructor and a copy constructor that creates a copy
    * of the given object*/
   LinkedList(); //default construtor
   LinkedList(const LinkedList& lst); //copy constructor
   /* Every class should have a destructor, which is responsible for
    * cleaning  up any dynamic memory allocation performed by the class.
    * Note the special syntax for the destructor */
   ~LinkedList();//destructor
   
   // PRE:
   // POST: A new node containing the given data is inserted at the front
   //       of the list
   // PARAM: data is the data to be stored
   void add(int data);

   // PRE:
   // POST: Prints the contents of the list to the screen, in order
   // PARAM:
   void printList();

private:

   Node *head; //Pointer to the first node in the list
}; 

Implementation file

// LinkedList.cpp
// Implementation of the LinkedList class

#include "LinkedList.h"
#include <string>
#include <iostream>

using namespace std; //needed for cout, cin to be recognized

// Default constructor
LinkedList::LinkedList(){
   head = NULL;
}

/* Copy constructor to copy an existing list.  Note that the compiler
 * will generate a copy constructor automatically.  However, this
 * constructor only creates a SHALLOW COPY (so would only copy the
 * size and head variables).  In this case this would NOT CREATE A
 * NEW LIST, just a new reference to one list.  It is therefore
 * necessary to write a constructor that makes a DEEP COPY.*/

/* Also note the parameter.  C++ functions use pass-by-value by
 * default.  This means that the functions make copies of the given
 * arguments.  This is inefficient (particularly for large objects).
 * Therefore it is normal to pass the address (using &) of the parameter,
 * but, if the parameter should not be changed, it is good practice to 
 * make it const, which prevents it from being changed.*/
LinkedList::LinkedList(const LinkedList& lst){
   head = lst.head; //shallow copy - *you need to fix this!*
}

/* The destructor is responsible for deleting any memory that was dynamically
 * allocated by an object.  If there is no such memory no destructor needs to
 * be created (the compiler automatically creates one).  Because this class
 * uses pointers to create new Nodes it is necessary to write a destructor.
 * Destructors are identified by the '~' preceding the class name.  There can
 * be only one destructor for a class, and it cannot have parameters. */
LinkedList::~LinkedList(){
   // *You need to write this!*

}

/**************************************************************************/
// LinkedList Operations
// Adds a node to the end of the list
void LinkedList::add(int x){
   Node *newNode = new Node(x); //new node with x
   // Check to see if list is empty
   if (head == NULL){
      // Make new node the new head
      head = newNode;
   }else{
      // Move to the end of the list
      Node* p = head;
      while (p->next != NULL){
         p = p->next;
      }
      p->next = newNode;
   }   
}

// Prints the entire list (head first) to the screen.
/* Note that there is some debate about whether or not this type of
 * method belongs in a class.  The argument (briefly) is that a class
 * shouldn't be responsible for its own display as it cannot foresee
 * how it is to be displayed. */
void LinkedList::printList(){
   Node *p = head;
   cout  "{"; //Nice format!
   // Traverse the list
   while (p != NULL){
      cout << p -> data; // Print data
      p = p -> next; // Go to next node
      if (p != NULL){
         cout << ","; // Print a comma unless at the end of the list
      }
   }
   cout << "}"; // Don't print a newline - it might not be wanted
}

Node.h File

#pragma once

class Node
{
public:
   // Constructors and destructor
   Node();
   Node::Node(int x);
   Node(int x, Node* nd);
   ~Node();

   // Public attributes
   int data;
   Node* next;
};

Node.cpp File

#include iostream>
#include "Node.h"

Node::Node()
{
   data = 0;
   next = NULL;
}

Node::Node(int x)
{
   data = x;
   next = NULL;
}

Node::Node(int x, Node* nd)
{
   data = x;
   next = nd;
}

Node::~Node()
{
}


*Adapted from CMPT 225 Lab 3

-- JimSkon - 2010-04-08

Topic revision: r5 - 2011-04-20 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback