deep copying with singly linked list

[aegis]

I've produced a small program to demonstrate what I'm after.
I'd like to implement deep copying of a singly linked list such
that the list class' copy constructor automatically(and recursively)
copies the entire list. This was my attempt:

node.cpp:
#include "object.h"
#include "node.h"
#include <iostream>

Node::Node() : next(NULL)
{
}

Node::Node(const Object& obj)
: obj(obj), next(NULL)
{
}

Node::Node(const Node& rhs) : obj(rhs.obj)
{
next = rhs.next;
}

const Node& Node:perator=(const Node& n)
{
obj = n.obj;
if(n.next != NULL)
next = new Node(n);
else
next = NULL;

return *this;
}

node.h:
#ifndef HAVE_NODE_H
#define HAVE_NODE_H

#include "object.h"

class Node {
friend class myList;
public:
Node();
Node(const Object& obj);
Node(const Node& n);
const Node& operator=(const Node& rhs);
private:
Object obj;
Node *next;
};
#endif



list.cpp:
#include "list.h"
#include "node.h"
#include "object.h"
#include <iostream>

myList::myList()
: front(NULL), last(NULL)
{
}

myList::myList(Object& obj)
{
front = new Node(obj);
last = front;
}

void myList:rint() const
{
Node *walk = front;
while(walk) {
cout << "a: " << walk->obj.getA() << " - "
<< "b: " << walk->obj.getB() << endl;
walk = walk->next;
}
}

void myList:rintAddresses() const
{
Node *walk = front;
while(walk) {
cout << "Node: " << walk << endl;
walk = walk->next;
}
}


list.h:
#ifndef HAVE_LIST_H
#define HAVE_LIST_H

#include "node.h"

class myList {
public:
myList();
myList(Object& obj);
myList(const myList& rhs);
void print() const;
void printAddresses() const;
void add(Object &obj);
private:
Node *front;
Node *last;
};

#endif


object.cpp:
#include "object.h"

Object::Object(int a, int b)
: a(a), b(b)
{
}


object.h:
#ifndef HAVE_OBJECT_H
#define HAVE_OBJECT_H

class Object {
public:
Object(int a=10, int b = 100);
int getA() const { return a; }
int getB() const { return b; }
private:
int a;
int b;
};
#endif

#include <iostream>
#include "list.h"
#include "object.h"

int main(void)
{
Object a(1,2);
Object b(3,4);
Object c(5,6);

myList x(a);
x.add(b);
x.add(c);
myList y(x);

cout << "Values: " << endl;
x.print();
cout << endl;
y.print();
cout << endl;
cout << "Addresses: " << endl;
x.printAddresses();
cout << endl;
y.printAddresses();
return 0;
}

My expectation was that y.printAddresses() would
give different pointer values than what x.printAddresses
gave but that was not the case.

Any recommendations on how I should do this?

 

[Pavel]

I've produced a small program to demonstrate what I'm after.
I'd like to implement deep copying of a singly linked list such
that the list class' copy constructor automatically(and recursively)
copies the entire list. This was my attempt:

node.cpp:
#include "object.h"
#include "node.h"
#include <iostream>

Node::Node() : next(NULL)
{
}

Node::Node(const Object& obj)
: obj(obj), next(NULL)
{
}

Node::Node(const Node& rhs) : obj(rhs.obj)
{
next = rhs.next;
}

const Node& Node:perator=(const Node& n)
{
obj = n.obj;
if(n.next != NULL)
next = new Node(n);
else
next = NULL;

return *this;
}

node.h:
#ifndef HAVE_NODE_H
#define HAVE_NODE_H

#include "object.h"

class Node {
friend class myList;
public:
Node();
Node(const Object& obj);
Node(const Node& n);
const Node& operator=(const Node& rhs);
private:
Object obj;
Node *next;
};
#endif



list.cpp:
#include "list.h"
#include "node.h"
#include "object.h"
#include <iostream>

myList::myList()
: front(NULL), last(NULL)
{
}

myList::myList(Object& obj)
{
front = new Node(obj);
last = front;
}

void myList:rint() const
{
Node *walk = front;
while(walk) {
cout << "a: " << walk->obj.getA() << " - "
<< "b: " << walk->obj.getB() << endl;
walk = walk->next;
}
}

void myList:rintAddresses() const
{
Node *walk = front;
while(walk) {
cout << "Node: " << walk << endl;
walk = walk->next;
}
}


list.h:
#ifndef HAVE_LIST_H
#define HAVE_LIST_H

#include "node.h"

class myList {
public:
myList();
myList(Object& obj);
myList(const myList& rhs);
void print() const;
void printAddresses() const;
void add(Object &obj);
private:
Node *front;
Node *last;
};

#endif


object.cpp:
#include "object.h"

Object::Object(int a, int b)
: a(a), b(b)
{
}


object.h:
#ifndef HAVE_OBJECT_H
#define HAVE_OBJECT_H

class Object {
public:
Object(int a=10, int b = 100);
int getA() const { return a; }
int getB() const { return b; }
private:
int a;
int b;
};
#endif

#include <iostream>
#include "list.h"
#include "object.h"

int main(void)
{
Object a(1,2);
Object b(3,4);
Object c(5,6);

myList x(a);
x.add(b);
x.add(c);
myList y(x);

cout << "Values: " << endl;
x.print();
cout << endl;
y.print();
cout << endl;
cout << "Addresses: " << endl;
x.printAddresses();
cout << endl;
y.printAddresses();
return 0;
}

My expectation was that y.printAddresses() would
give different pointer values than what x.printAddresses
gave but that was not the case.

Any recommendations on how I should do this?

It's true you need to post your "Node(const Node& n)" definition for us
to be able to answer your actual question, but, regardless, I would not
do Node() constructor recursive. Use iterations to both save stack space
(which is often at premium and may get exhausted before other memory)
and optimize jumps.

Also, think if you really need "last" for your single-linked list --
there is not much you can really do with it in such list. With no
"last", you could also dump one of "myList" or "Node" classes.

Hope this will help.

-Pavel

 

[Pavel]

It's true you need to post your "Node(const Node& n)" definition for us
to be able to answer your actual question,

Sorry, I meant myList(const myList& rhs)


-Pavel

 

[James Kanze]

I've produced a small program to demonstrate what I'm after.
I'd like to implement deep copying of a singly linked list
such that the list class' copy constructor automatically(and
recursively) copies the entire list. This was my attempt:

node.cpp:
#include "object.h"
#include "node.h"
#include <iostream>

Node::Node() : next(NULL)
{
}

Node::Node(const Object& obj)
: obj(obj), next(NULL)
{
}

Node::Node(const Node& rhs) : obj(rhs.obj)
{
next = rhs.next;
}

In addition to what others have mentionned, not that this does
not do a deep copy of Node. In practice, I'd probably make
"Node" a simple struct, private member of the list, rather than
an externally accessible class, and manipulate it in the list
code itself. But if you want to do a deep copy, this has to be:

Node::Node( Node const& other )
: obj( next == NULL ? NULL : new Node( *next ) )
{
}