What is the function of node in linked list?

Question

I am creating a linked list from scratch. Here is the code. at first, I have defined node *root=NULL;

that means root node has no element. But when I append the first element I have to create root=new node();

is not it that node *root=NULL; has created a root node? then why I have to use root=new node();.

actually i am confused among node *root=NULL; & root=new node(); & root==NULL'. would you please make me understand?

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int roll;
    node *next;

};

node *root=NULL;

void append(int roll)
{
    if( root==NULL)
    {
        root=new node();
        root->roll=roll;
        root->next=NULL;

    }
    else
    {
        node *current_node=root;


        while(current_node->next!=NULL)

        {
            current_node=current_node->next;

        }
        node *newnode=NULL;
        newnode=new node();
        newnode->roll=roll;
        newnode->next=NULL;
        current_node->next=newnode;


    }
}

[Why should I not #include ?](https://stackoverflow.com/q/31816095/5910058) — Jesper Juhl, May 28 '20 at 19:27

score 1 · Answer 1 · answered May 28 '20 at 06:48

Your linked list will be a, well, list of nodes that are connected by pointers.

If you assign node *root = nullptr;, you will not be able to access any member of root. After all, root does not point to a node but to nullprt. root = new Node() creates a new Node element using the default constructor. You will now be able to access the members of this element. This is why root->rool and root->next will work now.

node *root: Declares that root is a pointer to a node.

root = NULL: Seems old fashioned to me, but will assign the pointer to a nullprt.

root = new node(): Assigns root to an instance of node that was created using the default constructor.

root == nullprt: True if root is a nullptr.

score 1 · Accepted Answer · answered May 28 '20 at 06:54

First of you have to understand what pointers are. Basicall they hold memory adresses.

is not it that node *root=NULL; has created a root node?

No. root is no node, but a pointer to a node. It is initialized with NULL (in C++ nullptr should be preferred), so it doesn't point to any object yet.

then why I have to use root=new node();

new node() will allocate and initialize a new object of type node on the heap and return a pointer to this object. This pointer is then assigned to root - now root points to an actual object of type node.

actually i am confused among node *root=NULL; & root=new node(); & root==NULL.

I hope the first two are clear by now. root == NULL simply checks if the value of root is NULL, this is if root points to an actual object. Again, nullptr should be preferred here.

@imtinan No. This would mean "take the object `root` is pointing to (`*root`) and check if this object is equal to `NULL`". But you can't compare a `node` to a number. — Lukas-T, May 28 '20 at 08:12

score 0 · Answer 3 · 2020-05-28T06:49:09.427

The reason lies in the else.

You are looking for the end of the current list, and you append an element. To achieve this, you change the next pointer of the current last node (which is NULL as it's the last) to point to the new node.

But what happens if there is no node at all in the list? There is no next pointer to modify, and you can't append: you have to create a first node, which will not be the next of any other node. This case is not dealt with in the else clause, it's the root=new node(); that annoys you.

A remark. Usually one does not append, because you then have to scan the whole list.

If you really want to append, it's better to keep track of the pointer to the last element. You have two pointers then: the root and the last. The root is still necessary to be able to scan the list.

And if you don't keep track of the last pointer, the best is to always prepend (if you wish, you can pretend the last element of the list is the root node). It's what is usually done for a FIFO stack.

Incidentally, when you prepend, you don't have to deal with the initially NULL root: this NULL will become the next pointer of the first node, and there is nothing else to do.

What is the function of node in linked list?

3 Answers3