Creating a Copy Constructor/function for a linked list in c++

Question

I am writing a copy function for linked lists (called OLList) which contain a structure called Node. Node has an integer (renamed ListItem) called item, and a pointer of type Node called Next.

I am getting strange results. Any ideas as to what is wrong?

Here a simple class for the linked list without getters/setters

struct Node {
  ListItem item;
  Node *next;
};

class OLList {
private:
  Node *headM;
};

here is the function


void OLList::copy(const OLList& source)
{    
    if(source.headM==0)
        return;

    Node *after=source.headM->next;
    Node *temp=new Node;
    int *data_1=new ListItem;
    if(temp==NULL || data_1==NULL)
        exit(1);

    data_1=&source.headM->item;
    temp->item=*data_1;

    Node *ret=temp;

    while(after!=0){
        temp=temp->next;
        temp=new Node;
        int *data=new ListItem;

        if(temp==NULL || data==NULL)
            exit(1);

        data=&after->item;
        temp->item=*data;

        after=after->next;
    }   
    temp->next=0;   
    headM=ret;
    delete temp;
}

I have a control link list called the_list:

[ 99, 110, 120, 220, 330, 440, 550 ]

and I copy the linked list TWICE in two different ways. I should mention that this function is called by the assignment operator.

OLList other_list;
other_list = the_list;

OLList third_list = the_list;

The assignment operator (cannot be changed, b/c it was assigned to me):

OLList& OLList::operator =(const OLList& rhs)
{
    if (this != &rhs) {
        destroy();  //this is to prevent self copy
        copy(rhs);  //function is called here
    }
    return *this;
}

I get the following outputs respectively:

testing for copying lists ...
other_list as a copy of the_list: expected to be [ 99, 110, 120, 220, 330, 440, 550 ]
[ 99 ]
third_list as a copy of the_list: expected to be: [ 99, 110, 120, 220, 330, 440, 550 ]
[ 99, -2144292712, -2144292728, -2144292744, -2144292760, 0 ]

so the first one copies just the first element, and the second one copies who knows what... I am still new to programming so please ELI5! Thank you.

if(source.headM==0) return; after copying from an empty list I would expect that both are empty. Anyhow, please provide a minimal reproducible example — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Nov 21, 2019 at 9:02
@formerlyknownas_463035818 that line is checking to make sure the SOURCE is not pointing to NULL. — John
– John, Commented Nov 21, 2019 at 9:08
source is a reference, it cannot point to NULL, and again: If i copy from a list that has nothing inside, I would expect that afterwards both lists contain the same — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Nov 21, 2019 at 9:09
Im confused. In the code you provided copy is never called. — TomBombadil
– TomBombadil, Commented Nov 21, 2019 at 9:09
That is an assignment operator, not a copy constructor (en.cppreference.com/w/cpp/language/copy_constructor vs en.cppreference.com/w/cpp/language/copy_assignment) — eike
– eike, Commented Nov 21, 2019 at 9:23

Yuri Kovalenko · Accepted Answer · 2019-11-21 10:44:56Z

Unfortunately, your code has several problems:

int *data_1=new ListItem; // here you allocate a ListItem (strange, why you store it in a int* ?)
// ...
data_1=&source.headM->item; // and a couple of LoC you replace it with another pointer; thats a memory leak
temp->item = *data_1; // overcomplicated way to copy

Maybe you wanted just to copy the value?

temp->item = source.head->item; // we can throw that data_1 ptr out

The same situation with int * data.

Another strange moment:

temp=temp->next;
temp=new Node;

Two assignments in a row without using the first value is an indication of an error. Here you store the next pointer to temp, but immediately rewrite it with another allocated Node, so your first node, ret, never gets a valid next pointer value.

void OLList::copy(const OLList& source)
{    
    if(source.headM==nullptr) // using 0 for indicating empty pointer is bad!
        return;

    Node *after=source.headM->next;
    Node *temp=new Node;
    if(temp==NULL)
        exit(1);

    temp->item=source.headM->item; // just copy the value;

    headM=temp; // store the first node

    while(after!=nullptr){
        temp->next=new Node; // create the next node
        if(temp->next==NULL)
            exit(1);

        temp=temp->next; // move to next node
        temp->item=after->item; // copy the value
        after=after->next; // update after ptr
    }
    temp->next=0; // indicate, that that's the last one
    // don't delete temp, because it is added to list;
}

However, you can simplify even more (from some perspective) with pointers to pointers:

void OLList::copy(const OLList& source) {
    Node ** tmp = &headM; // we'll put the nodes with this ptr
    Node * toCopy = source.headM;
    while (toCopy != nullptr) {
        Node * node = new Node; // create new node
        if (node == nullptr)
            exit(1);

        *tmp = node; // put the node to its place (headM at first, then next member of prev node)
        node->item = toCopy->item; // copy the value
        toCopy = toCopy->next;
        tmp = &(node->next); // update where we'll put the next node
    }
    *tmp = nullptr; // that was the last one
}

Collectives™ on Stack Overflow

Creating a Copy Constructor/function for a linked list in c++

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related