Singly Linked List - C++ - Unexplainable run-time error

Question

I wrote the following code, to just create and insert nodes (integer data) into an SLL, in C++.

#include <stdio.h>

class Node
{
    public:
        int data;
        Node * next;
        Node * first;
        Node() {}

        void insert(int dat)
        {
            Node * newnode = new Node();
            newnode->data=dat;
            newnode->next=NULL;
            if(first==NULL)
            {
                first=newnode;
            }
            else
            {
                Node *temp=first;
                while(temp->next!=NULL)
                { temp=temp->next; }
                temp->next=newnode;
            }
        }
};

int main()    
{
    Node * a=new Node();
    a->insert(12);
    return 0;
}

At first, I tried overriding the Node constructor to Node(int dat) and in that I tried doing initialization of every new node (data=dat, next=NULL) that I create in insert. Insert would be called with a "dat" value from main and it would call the overloaded Node constructor to initialize data to dat and next to NULL. That led to my program crashing.

So I took out both default and overloaded constructor and did the initialization of each new element in the insert itself. My program works fine. However, even adding the default constructor (as shown in Line 10 of the code) my program crashes. Can anyone tell me why this is happening in both cases?

Thanks.

The code above doesn't crash for me. Is that the code that is giving you problems? — Paul Draper
– Paul Draper, Commented Oct 28, 2013 at 6:31
Paul Draper - Yes, I copy-pasted it. I am using Dev-C++ 4.9.9.2. If I just remove line 10, the constructor, it works. — user2881037
– user2881037, Commented Oct 28, 2013 at 6:33
Do you really want to have a first pointer in every node? Normally first is a member of the singly-linked list but not of the node. Besides that you never initialize first and the comparison (first == NULL) might trigger or might not. — Mehrwolf
– Mehrwolf, Commented Oct 28, 2013 at 6:35
Well, if it makes you feel any better, it works just fine with g++ 4.6.3 :/ — Paul Draper
– Paul Draper, Commented Oct 28, 2013 at 6:36

Benjamin Lindley · Accepted Answer · 2013-10-28 06:48:58Z

1

Your default constructor leaves the data members uninitialized. So this line:

Node * a=new Node();

creates a Node with uninitialized members, leading to problems when you try to add a node. When you remove your default constructor, the above line (due to the parenteses in new Node() combined with the fact that the class has no user defined constructors) results in a value initialization of all the members, so the pointers get initialized to NULL, and you get the expected behavior.

If you had left the parentheses out:

Node * a = new Node;

The data members would be uninitialized, just as when you had a do nothing default constructor.

The correct solution is to fix your default constructor to explicitly initialize all members.

Node() :data(0), next(nullptr), first(nullptr) {}

edited Oct 28, 2013 at 6:48

answered Oct 28, 2013 at 6:37

Benjamin Lindley

104k11 gold badges210 silver badges285 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Tony Delroy · Accepted Answer · 2013-10-28 06:38:36Z

0

Node * a=new Node();

Creates a new node, running its default constructor...

Node() {}

...which doesn't do much - not even initialise data, next or first.

Consequently, when you call...

a->insert(12);

...and it tries...

if(first==NULL)

...it's reading from uninitialised memory, resulting in undefined behaviour. On one run the newly-created object might happen to have a 0 in there, another time it might not, some other time it might just crash trying to read the value. You go on to do other worse things with the uninitialised data.

More generally, when you have such problems I recommend you put std::cerr << xyz << '\n'; statements in to dump out some relevant variables, or trace through in the debugger - you might have seen that the variables had garbage values, then could have started to investigate why, which might have yielded a more focused question here, or perhaps led you to an existing answer....

answered Oct 28, 2013 at 6:38

Tony Delroy

107k16 gold badges188 silver badges265 bronze badges

2 Comments

user2881037 Over a year ago

I understand what you are saying, but shouldn't the same thing happen if I remove the constructor? I just have the declaration without initialization of first and I am checking if(first==NULL).

Tony Delroy Over a year ago

@user2881037: Benjamin had already addressed that aspect, so I didn't add an explanation here. In the wikipedia page he links, note this aspect of value initialisation: "If T is an non-union class type without any user-provided constructors, then the object is zero-initialized and then the implicitly-declared default constructor is called (unless it's trivial)." So, zero-initialised pointers happen to be NULL on your system (and indeed, almost all systems).

kunal · Accepted Answer · 2013-10-28 07:28:13Z

0

initialize member variables in constructor like this

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

answered Oct 28, 2013 at 7:28

kunal

9669 silver badges16 bronze badges

1 Comment

Skalli Over a year ago

Initializing lists would be the smarter way to go here. Node() : data(0), next(nullptr), first(nullptr) {}

Collectives™ on Stack Overflow

Singly Linked List - C++ - Unexplainable run-time error

3 Answers 3

Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related