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 exists in 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.
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.
Download this zip file and save and unzip it in your lab3 directory. This zipfile contains .h and .cpp files for LinkedList and Node classes (copies of code below). It also contains a stub of a driver program test.cpp, and a makefile for building a program named "test."
I've also provided you with a simple test function (listTest(), below) that:
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.
void listTest(){
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;
}
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).
If you have successfully completed the deep copy, please ask a TA to take a look at this output, and receive your 1 mark for this lab.
You should also complete the rest of this lab below, but this can be done as homework if you do not have time to complete it in your lab time slot.
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).
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.
We will use a program called valgrind to check for memory leaks. Run your exectuable called test through valgrind:
uname@hostname: ~$ valgrind -q --leak-check=full testor
uname@hostname: ~$ valgrind -q --leak-check=full ./test(./ depends on environment configuration, either you need it or not)
If your destructor has been implemented correctly you won't see anything unusual in the console, if you have a memory leak you will see something like this:
uname@hostname: ~$ valgrind -q --leak-check=full test
Print first list: {1,2,3}
{1,2,3}
Make a copy of the list
Add items and print first list: {1,2,3,4,5,6}
{1,2,3,4,5,6}
Print second list, if it was deep copied should be: {1,2,3}
{1,2,3}
==26216== 48 (16 direct, 32 indirect) bytes in 1 blocks are definitely lost in loss record 7 of 10
==26216== at 0x100011D7B: operator new(unsigned long) (vg_replace_malloc.c:261)
==26216== by 0x1000013CA: LinkedList::LinkedList(LinkedList const&) (in ./test)
==26216== by 0x100000FAF: listTest() (in ./test)
==26216== by 0x1000010D9: main (in ./test)
==26216==
==26216== 96 (16 direct, 80 indirect) bytes in 1 blocks are definitely lost in loss record 9 of 10
==26216== at 0x100011D7B: operator new(unsigned long) (vg_replace_malloc.c:261)
==26216== by 0x100001309: LinkedList::add(int) (in ./test)
==26216== by 0x100000F2A: listTest() (in ./test)
==26216== by 0x1000010D9: main (in ./test)
==26216==
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.
#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
};
// 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 = 0;
}
/* 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 == 0){
// Make new node the new head
head = newNode;
}else{
// Move to the end of the list
Node* p = head;
while (p->next != 0){
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 != 0){
cout << p -> data; // Print data
p = p -> next; // Go to next node
if (p != 0){
cout << ","; // Print a comma unless at the end of the list
}
}
cout << "}"; // Don't print a newline - it might not be wanted
}
#pragma once
class Node
{
public:
// Constructors and destructor
Node();
Node(int x);
Node(int x, Node* nd);
~Node();
// Public attributes
int data;
Node* next;
};
#include "node.h"
Node::Node()
{
data = 0;
next = 0;
}
Node::Node(int x)
{
data = x;
next = 0;
}
Node::Node(int x, Node* nd)
{
data = x;
next = nd;
}
Node::~Node()
{
}