Skip to content

How do you create a node in a linked list?

Traverse a singly linked list

In this article, you’ll learn how to create a node in a linked list in C/C++, along with that you’ll also see the algorithm to create a node in a linked list.

So, Let’s get started!

What is a node in linked list?

Each and every element of a linked list is called a node.

A node is basically a collection of two sub-elements or parts or you can say a node in a linked list has two component (element) fields: one to store the relevant information (i.e., the data); and one to store the address of the next node, called the link of the next node in the list.

The address (link) of the first node in the list is stored in a separate location, called the head or first or start.

The address field of the last node contains pointer to the NULL.

Or,

You can say that the link field of the last node points to NULL.

create a node in a linked list
Image: Linked list

What does creating a node means in linked list?

Creating a node simply means, Defining a structure which we will called as node, allocating memory to that structure and also initializing values to its member variables.

Didn’t understand clearly?

Don’t worry! Just hold my hand, all will be very clear till the end of this article.

So, Let’s move further…

Algorithm to create a node in a linked list:

  • Step 01: Start
  • Step 02: Define a new user-defined data type called “node” with the help of structure.
    • Step 03: Declare a variable named “data” of int/char/float/double... type.
    • Step 04: Declare a pointer named “link” of node type.
  • Step 05: Declare a pointer named “start” whose type would be node and initialize it with NULL.
  • Step 06: Define a function “CreateNode()” whose return type would be a pointer of node type.
    • Step 07: Declare a pointer “n” of node type.
    • Step 08: Assign the return value of the malloc function to “n”.
  • Step 09: Return n.
  • Step 10: Stop

So as you can see in the above image of the linked list, a node is nothing but the combination or collection of two different element fields or parts. Right?

The first one to store the relevant data and it may be of any predefined (built-in) type like int, float, char, bool or any other built-in type.

For the sake of simplicity, Let’s say here I’m taking this field as of type “int” whose name is “data”.

And, the second one (i.e., the second field) to store the address of the next node, and it would be of node type.

Hey! wait, wait…

I know you might be wondering, why the second field would be of node type? Right?

Don’t worry!

I’ll explain this also but some times later. Be some patient…

So, let’s get to the point.

Since the second field containing the address of the next node so it must be a pointer.

Because, as we already know, a pointer is a special type of variable which contains the address of other similar type of variable.

Let’s say the name of the pointer here I’m taking is “link”.

And, since “link” is a pointer so we are using asterisk (*) symbol before it.

The asterisk (*) symbol indicates that the variable is a pointer.

So now let me answer your last question.

That is why the second field (i.e., the address/link field) would be of node type. Right?

It’s simply because, as we know a special thing about pointer, a pointer always contains the address of a variable of the same type as the pointer is.

So far we have seen that there are two different data types inside a node.

Which shows that this node is not a built-in data type. Because a built-in data type always stores values ​​of the same type.

Since node is not a built-in type so, we have to create or define a user-defined data type which will be of node type.

Then, what we have to do is…

We have to define a new data type which consists of two different types.

And, as you have already studied about structure in C language that, If we want to combine two or more than two different data types to make a single data type, then we have to define a structure.

So, we can use “structure”. Right?

A structure is used to create user defined data type in C/C++.

A structure basically creates a data type that can be used to group elements of possibly different types into a single type. 

So, let’s see how to define a node data type.

// Defining a node (data type)
#include<stdio.h>

struct node
{
    int data;
    struct node *link;
};


In the above code snippet I’m defining a structure using the keyword struct followed by the name of the structure which is node here.

And, Inside the body of the structure I’m declaring the “data” and the “link” pointer.

If you observe carefully, you’ll find that the link pointer also has the type node.

And, whenever a structure which contains a pointer which is pointing to the structure of same type then it is called as self-refrential structure.

If you will see in the above code snippet, you’ll find that before writing the name “node” in the declaration of link pointer we are adding a keyword named “struct”. Which indicates that the node data type is made with the help of structure.

? Note: Whenever we create a data type with the help of structure, we must have to write the struct keyword before the name of the data type. Here, the data type is “node”.

So that’s it. I just created a new data type whose name is node here.

But, Node is not created yet. We have only declared/defined it.

Because until we will not allocate memory to this created node, where will we store the data and the address of the next node. Right?

So, we will have to allocate memory for this node. Creating a structure is not sufficient.

So let’s see how we can allocate memory to this node structure.

// Create a node in a linked list
#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *link;
};
struct node *start = NULL;

struct node *  CreateNode()
{
    struct node *n;
    n = (struct node *)malloc(sizeof(struct node));
    return(n);
}


Now, we have to create a pointer named start.

Or, you can give any name to the this pointer such as head or first. It’s upon you.

I’m taking start here.

Now, your question would be why do we need to create this pointer. Right?

Answer: We are creating this pointer only because, this is pointer to the first node of the list which we will create later.

Means, The start pointer will keep the address of the first node of the list.

Now, what will be the type of this pointer?

This pointer will also be of the same type as the node variable. Isn’t it.

Because, It stores the address of a node type of variable.

So I created another pointer of node type named start and initially stores NULL in it.

Well, why store null in it.

It’s only because, Initially when your program starts, it will not point to any node.

And, till now we have not created any node. And since we have not created any node yet, then the data i.e., info (value) has not come in any node.

Unless a node has a value, no node will ever be created.

If no node has been created, then whose address will be inside it.

And if you don’t assign NULL then it will store garbage value inside it.

And if there is garbage value then what will it mean?

It would simply mean that it is pointing at some node.

So, we would think that start is pointing to a node. Means, any node is present in the list.

But, now NULL is kept inside start, so it is understood that start is not pointing to any node.

So there is no list yet.

Whenever start value is null it means list is empty and if start value is not null then it means list is not empty.

So we have two things ready. First, we understood how to define the node structure, secondly we understood how we would create a pointer named start.

Now we will create a function, Whose job will be to create a new node.

So, what will be the return type of this function?

This will return address of node type. So, I’ve to write struct node *.

And here we are giving the name of the function as CreateNode().

And now let’s define this function…

First of all, I’ll declare a pointer variable whose name will be n.

And, I’ll assign the return value of the malloc function to “n”.

We know that if we want to create a memory block dynamically, we take the help of malloc function.

And, we also know that malloc function takes the size of the data type as parameter (argument) , the size of the memory block we need here is the size of the node.

We have already defined with the help of a node data type that, what will be in the node and what will be its size.

We said that inside the node there will be a variable named data and a variable named link.

If you count the total memory, then it should be 8 bytes. Right?

4 bytes for the info and 4 bytes for the link.

As we already know, link is a pointer varible here. And, it will take 4 bytes according to a 32 bit architecture computer and for a 64 bit architecture computer the pointer size will be 8 bytes. So for a specific architecture pointer size will be fixed.

So, we could also write 8 instead of sizeof(struct node).

But instead of calculating the size myself, I gave the responsibility to the sizeof operator to calculate the size of the node.

Because, whenever the type of “data” will change then we have to manually calculate the size of the node each time.

But, If we gave the responsibility to the sizeof operator to calculate the size of the node then it will be easy for us to because, the sizeof operator will automatically calculate the size of the node each time.

So 4 is basically getting passed in malloc().

So a block of 4 bytes will be formed.

But we know one thing that the return type of malloc is a pointer to void type.

So we should typecast it so that the warning does not come, so we would write (struct node *).

So let’s understand once again what we have done so far.

First we create a new memory block with the help of malloc function which will be the size of the node, i.e., 8 bytes. And, its address is returned by malloc.

After that we simply typecasted it and made the address of node type.

And then we contain the address in a pointer of type node.

So, now we have created a new node and we are returning it.

And, this has become a function through which we can create a new node.


Share this Post

Leave a Reply

Your email address will not be published. Required fields are marked *