linked list not working (c++)

Question

I am trying to make a copy constructor so that I can copy a vector. Its not working I suspect because nodes are being deleted twice because the copy constructor is not copying new nodes but simply copying pointers to them. I'm not sure what is wrong with my copy constructor. Any help is appreciated.

#include <iostream>

using namespace std;

struct node{
public:
    node(int n){
        node* ptr = this;
        data = 0;

        for (int t=0; t<n-1; t++){
            ptr -> next = new node(1);
            ptr = ptr -> next;
            ptr -> data = 0;
        }

        ptr -> next = NULL;
    }
    node(node &obj){
        delete next;
        node* ptr = this;
        node* optr = &obj;
        while (true){
            ptr -> data = optr -> data;
            optr = optr -> next;
            if (optr == NULL) break;
            ptr -> next = new node(1);
            ptr = ptr -> next;
        }
    }
    ~node(){
        if (next != NULL) delete next;
    }


private:
    double data;
    node* next;
};

void func(node a){
    node b(1);
    b = a;
}


int main(){
    node v(3);
    func(v);
}

Thanks

In the copy constructor: `delete next;` `next` has yet to be assigned, so Crom only knows what was just deleted. Ka-BOOM! — user4581301, Sep 13 '16 at 20:33
The copy constructor constructs a *new* object, so `next` is uninitialised when you `delete` it. (But it's not just copying pointers.) And you need an assignment operator. — molbdnilo, Sep 13 '16 at 20:34
`if (next != NULL) delete next;` That `if` is redundant, `delete` checks anyways. That aside, why do students still have to write linked lists? That's one of the least useful exercises I can imagine, at least for beginners. — Baum mit Augen, Sep 13 '16 at 20:35
Useful, no. But it is a great pointer mind. That said, there are more useful pointer minds we could be teaching. — user4581301, Sep 13 '16 at 20:36
Be really careful with that destructor, by the way. Make absolutely certain that `next` is nulled after removing a `node` from the list or your list just got obliterated. — user4581301, Sep 13 '16 at 20:39
Do you want the list to be copy of the information or another container of the same information? The difference is important with raw pointers. The way it's setup here if you delete any list of `node` you kill all "copies". I would suggest looking at the copy swap idiom http://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom — Matt, Sep 13 '16 at 20:42

score 0 · Answer 1 · edited May 23 '17 at 12:08

A few things jump out:

First, you could see what's going on and fix it a lot faster if you ran this bit of test code in your development environment's debugger. Debugger use is an essential skill to the productive programmer, so the sooner you learn it, the better.

Second is an ideological point, so ignore me if you disagree. The node cannot have the information that the linked list can have about the status of the list, so the node should not link itself, unlink itself, or delete linked nodes without being instructed to do so by the linked list. While self-managing behaviour is useful, it won't always be the correct behaviour for the list. I find it best to keep a node really dumb.

Third, in a constructor, none of the variables are initialized until you initialize them. You can't count on them having a useful or predictable value, so

node(node &obj){
    delete next;

enters into the realm of Undefined Behaviour. The value of next has not been assigned so it's unknown and it's impossible to accurately predict what will happen if you attempt to delete it.

Solution: Don't delete it.

node(node &obj)
{
    node* ptr = this;
    node* optr = &obj;
    while (true)
    {
        ptr->data = optr->data;
        optr = optr->next;
        if (optr == NULL)
            break;
        ptr->next = new node(1);
        ptr = ptr->next;
    }
}

There are a few improvement that can be made in there, but that's outside the scope of the question.

A side note:

void func(node a)

passes a by value. This triggers the copy constructor possibly a bit earlier than you would expect. You may want to pass by reference here:

void func(node &a)

Finally,

node b(1);
b = a;

Does not trigger the copy constructor.

node b(1);

constructs b with no additional links.

b = a;

uses the assignment operator, operator=, to copy a into b.

But no operator= has been defined. This violates the Rule of Three. What is The Rule of Three? Read the link and find out.

To you this means the next pointer, and not the next node, is copied. You now have two nodes pointing to the linked node, in other words the same list, and that's bad. Delete one and you delete the contents of the other, leaving the other invalid.

node & operator=(node other) // pass by value copies the node
{
    delete next; // prevent leak of additional nodes. The smart destructor helps here.
    data = other.data; // copy data
    next = other.next; // steal remaining links from other. to save further copying
    other.next = nullptr; // prevent destruction of the remaining links when 
                          // other goes out of scope
    return *this;
}

Rather than duplicate the work done copying in the copy constructor, we use the copy constructor by passing by reference.

As a useful side note,

node b = a;

will call the copy constructor for you and initialize b with a without constructing a "temporary" b beforehand.

Any further problems I do not care about as they cannot be tested with the provided framework.

linked list not working (c++)

1 Answers1