linked list implementation fail without malloc

Question

The first example is the example of a linked list without dynamic memory allocation. But in this example when we run it, it will only display 10 and then will provide runtime error. Please help me finding what is wrong.

#include<bits/stdc++.h>

using namespace std;

struct Node{
    int data;
    struct Node* next;
}Node;

struct Node* head;

void Insert(int x)
{
    struct Node* temp;
    temp=head;

    struct Node* newnode;
    newnode->data=x;
    newnode->next=NULL;

    if(head==NULL)
    {
        head=newnode;
        return;
    }

    while(temp->next!=NULL)
    {
        temp=temp->next;
    }

    temp->next=newnode;

}

void print()
{
    struct Node* temp;
    temp=head;

    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}

int main()
{
    head=NULL;
    Insert(10);
    Insert(20);
    Insert(30);
    print();
}

In the below example, I have just used malloc to provide dynamic memory to the variables. It works perfectly as expected. Why is there such a difference between the two?

#include<bits/stdc++.h>

using namespace std;

struct Node{
    int data;
    struct Node* next;
}Node;

struct Node* head;

void Insert(int x)
{
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    temp=head;

    struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
    newnode->data=x;
    newnode->next=NULL;
    cout<<"Reached here"<<endl;

    if(head==NULL)
    {
        head=newnode;
        return;
    }

    while(temp->next!=NULL)
    {
        temp=temp->next;
    }

    temp->next=newnode;

}

void print()
{
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    temp=head;

    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}

int main()
{
    head=NULL;
    Insert(10);
    cout<<"Inserted 10"<<endl;
    Insert(20);
    cout<<"2nd"<<endl;
    Insert(30);
    cout<<"3rd"<<endl;
    print();
}

you are creating a pointer and trying to access its fields without initializing it. what else did you expect? — mangusta, Jul 16 '20 at 05:36
[Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Evg, Jul 16 '20 at 05:59
Check your reading materials. It looks like they're teaching an uncomfortable combination of C and C++ that you'll have to train yourself out of. I'm not hopping on the"Just use `std::list` bandwagon here (but seriously, use `std::list` when it comes time for real work in C++), but each language does things differently and you should take advantage of each one's strengths. — user4581301, Jul 16 '20 at 06:02

Support Ukraine · Accepted Answer · 2020-07-16T06:39:02.357

In your example without malloc this is simply illegal code:

struct Node* newnode;
newnode->data=x;
newnode->next=NULL;

newnode is not pointing to any legal memory so writing to memory using newnode is undefined behavior.

If you want a linked list without using malloc you must reserve memory for the nodes up front. For instance, you can make a pool of 1000 nodes at program start and then use these node during program execution.

Like:

 static struct node nodePool[1000];

 struct node* getNode()
 {
     // Add code to find an unused node and return a pointer to the node
     // This will require some extra data object to track which nodes are free
 }

 void freeNode(struct node* p)
 {
     // Add code to mark the node as unused
     // This will require some extra data object to track which nodes are free
 }

void Insert(int x)
{
    ...

    struct Node* newnode = getNode();
    if (newnode == NULL)
    {
        // No more nodes
        add error handling
        return something or exit(1);
    }
    newnode->data=x;
    newnode->next=NULL;

    ...
}

Note: Using a flat array for a node-pool is doable but it's not good for performance. Get/fre node will be O(n) which is bad for program performance. Programs using pools have more advanced pool implementations that allows for O(1) operations. One (pretty simple) method is to implement the pools control-data as a linked list with both head and tail pointers. That will allow for O(1) complexicity for both getNode and freeNode.

Note: I just noticed that the question is marked with both C++ and C. This answer was written with C in mind. For C++ code there is no (aka seldom any) reason to implement your own linked list - simply use std::list

john · Answer 2 · 2020-07-16T06:22:43.453

Both your examples are wrong but for different reasons. Pointer variables need to be given values, just like regular variables. So your first example is wrong because the pointer variable newnode is uninitialised. See the coments I've added to your code

struct Node* temp; // temp has no value
temp=head;         // now temp is given a value

struct Node* newnode; // newnode has no value
newnode->data=x;      // ERROR, newnode is used before it's been given a value
newnode->next=NULL;

You wouldn't use a regular variable before you'd given it a value. It's no different with pointer variables.

Your second example has the opposite error, you give the temp pointer a value twice! Again see the comments added

struct Node* temp=(struct Node*)malloc(sizeof(struct Node)); // temp is given a value
temp=head;                         // now temp is given a different value,
                                   // the first value is discarded

struct Node* newnode=(struct Node*)malloc(sizeof(struct Node)); // newnode is given a value
newnode->data=x;                                       // newnode is being used correctly
newnode->next=NULL;

You can give a pointer a different value in two ways, you can create a new node for it to point to, that's what temp=(struct Node*)malloc(sizeof(struct Node)); does, or you can make it point at an already existing node, that's what temp=head; does. There's not much point in doing both. In your second example the node you create with temp=(struct Node*)malloc(sizeof(struct Node)); is never used, it is created and then discarded when you make temp point at the head node instead. This is called a memory leak. If the leak gets large enough your program will run out of memory. At best it's wasteful.

Again think about how you would use regular variables, you'd never write code like this int x = 10; x = 20; it doesn't make sense to give a variable one value, and then on the very next line throw that value away and give the variable a different value. But that's exactly what you did with the temp variable. Again pointers aren't special, the same rules that apply to regular variables also apply to pointer variables.

linked list implementation fail without malloc

2 Answers2