Linked List Node Insertion a Node at nth Position

In this guide we will focus on how to insert a node in a linked list. We will look at three different scenarios where insertion is possible in a linked list. These include inserting a node at the beginning, inserting the node at the end and inserting the node at the i-th position.

In our introductory article regarding Linked List, we showed you how to create a simple list consisting of five nodes and how to traverse it. We will follow up from there and include inserting a node at different positions now.

Link List Node Insertion at the beginning

To insert an element in the beginning will only create a new node and adjust the head pointer and the link of this new node. The time taken will not depend upon the size of the list. It will be constant. In terms of Big O notation, it will be O(1).

C program

In C language, we define a node as a structure. There will be two fields in this node. The first one is integer which will store the data. The second is Node* which is the pointer to the node. It will store the address of the next node in the list.

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

Now to create a linked list we will have to create a variable that will be a pointer to the node. It will store the address of the HEAD node.

``struct Node* head``

We have declared this variable as a global variable as it is not declared inside any function.

main()

Inside the main() function, we will first make sure that the pointer variable that we declared above, the head points nowhere thus we are setting it as NULL. This means that the linked list is empty. The head variable which is of type pointer to node has the value NULL.

``head= NULL;``

The user will be prompted to enter the number of elements in the linked list. This will get saved in the integer variable ‘n’.

``````printf("Enter the number of elements in the list:\n")
int n;
scanf("%d",&n);``````

We will define another variable ‘i’ to run the loop. The for() loop will print and collect the input from the user regarding the numbers to be filled in the linked list. These will be saved in the variable ‘x’.

``````int i;
int x;
for(i=0;i<n;i++){
printf("Enter the number \n");
scanf("%d",&x);
}
``````

This particular number ‘x’ will be inserted into the linked list by making a call to the method insert(). Each time we insert we will print the value of all the nodes in the linked list using the Print() method. Both of these are user defined functions.

``````insert(x);
Print();``````

Definitions of these two functions are:

``````void insert(int x);
void Print();``````

Let us show you the implementations of these two functions.

insert function

The insert function will insert a node at the beginning of the linked list. Inside the insert function we will first create a node. This will be achieved using the malloc() function which will return a pointer to the starting address of the memory block. Malloc returns a void pointer. We require a pointer to the node . Therefore, we are typecasting.

``Node* temp = (Node*)malloc(sizeof(struct Node));``

Then we will dereference using * sign this will enable us to access the two fields of the nodes. The data part is ‘x’. Note that temp->data is the same as writing *temp.data

``````temp->data=x;
temp->next=NULL;``````

We are creating a node where the address is saved in the temp variable. Additionally we will set the pointer to the next node to NULL initially.

Point to Note: temp is a pointer variable that we are dereferencing in order to change the value of the node.

When inserting a node at the beginning of the linked list there can be two scenarios: either the linked list is empty or the list already has some nodes.

• In case, the list is empty we will just have to point the HEAD node to the newly created node. This way the pointer variable will now point to the newly created node.
``````void insert(int x)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data=x;
}
``````
• In the case, where the linked list consists of some nodes and we want to insert a particular node at the beginning then we will set the link of the newly created node to the previous HEAD.
``````void insert(int x)
{
struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
temp->data=x;
temp->next=NULL;

}``````

Print function

To implement the print function we will first create a local variable called ‘temp.’ This will be a pointer to the node. Additionally, this will be set to the address of the HEAD. Then we will traverse the linked list to display it. This will require a while loop. While the temp is not equal to NULL we will keep on moving to the next node and print the value of the data.

``````void Print()
{
while(temp!=NULL)
{
printf("%d",temp->data);
temp=temp->next;
}
printf("\n");
}``````

The complete C Code is given below:

``````#include <stdio.h>
#include <stdlib.h>

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

void insert(int x)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data=x;
}

void Print()
{
while(temp!=NULL)
{
printf(" %d",temp->data);
temp=temp->next;
}
printf("\n");
}

int main()
{
printf("Enter the number of elements in the list:\n");
int n;
scanf("%d",&n);
int i;
int x;
for(i=0;i<n;i++){
printf("Enter the number \n");
scanf("%d",&x);
insert(x);
Print();
}

}

``````

Code Output

Now let’s see the code output. After the compilation of the above code, you will get this output.

First the user will be prompted to enter the total numbers in the linked list. We have provided 4 numbers. Next we will enter the numbers one by one and they get inserted at the beginning if the list. The list gets displayed at each step.

Link List Node Insertion at the End

If we want to insert a node at the end of the linked list then we will first create a node separately which will get allocated at some memory location. Then to adjust the link, we will have to set the address segment as NULL because this is going to the last node.

Link List Node Insertion at the n-th position

Now we will discuss how to insert a node at any position in the linked list that is specified. Our aim will be to create an insert function that will take in two parameters. The first parameter will be the data to be inserted in the node and the second parameter will be the position we want to insert the particular node at. This particular insert function will be able to handle all kinds of situations where either element to be inserted can be at the beginning, at the end, at an invalid positions or basically anywhere.

First create a node and set the data field to the data specified by the user. Then to insert the node at the n-th position given, we will traverse the list and go to the node right before it meaning at (n-1) position. Next, we will set the link field of the newly created node equal to this particular link i.e. link of (n-1). After the link is built, we will break off the link of the (n-1) position node.

C program

Let us understand how to develop this C program successfully.

main function

After defining the Node and setting a global variable as ‘head’ we will move to the main() function. Inside this function, first we are setting the head variable as NULL. This shows that the linked list is empty at present. Then we will call the insert() function and pass the data as well as the position for it to be inserted. For example we specify insert(3,1). This means that I want to insert number ‘3’ at the first position of the linked list. Again calling the insert(5,2) function inserts the number ‘5’ at the second position in the list. Then we will call the print() method to display the linked list as the output.

``````int main()
{
insert(3,1);
insert(5,2);
Print();
}
``````

insert function

Let us look at the implementation of the insert function. Inside the insert function, we will first create a node and call it ‘temp.’ Then we will create the two fields of the node. The data field will be set and the link field will be set to NULL.

`````` struct Node* temp= (struct Node*)malloc(sizeof(struct Node*));
temp->data=data;
temp->next=NULL;``````

Now we will cater the case if the node is to be inserted at the beginning i.e. n will be equal to 1. If n is equal to 1 then the pointer to the next node will be set to HEAD. The variable will be adjusted in such a manner that it will point to the newly created node i.e. the HEAD.

``````if (n==1) {
return;
}``````

However for the rest of the scenarios we will have to move to the (n-1) position. We will have to create another pointer to the node now. Let us call it ‘temp2.’ The for() loop will traverse the list to the (n-1) position. The link of the newly created node will now be set equal to that of the node present at the (n-1) position. After that the link of the (n-1) position node will be altered in order for it to point to the newly created node.

``````void insert(int data, int n)
{
struct Node* temp= (struct Node*)malloc(sizeof(struct Node*));
temp->data=data;
temp->next=NULL;
if (n==1) {
return;
}
for(int i=0; i<n-2; i++){
temp2=temp2->next;
}
temp->next=temp2->next;
temp2->next=temp;
}

``````

Print function

To implement the print function we will first create a local variable called ‘temp.’ This will be a pointer to the node. Additionally, this will be set to the address of the HEAD. Then we will traverse the linked list to display it. This will require a while loop. While the temp is not equal to NULL we will keep on moving to the next node and print the value of the data.

``````void Print()
{
while(temp!=NULL)
{
printf("%d",temp->data);
temp=temp->next;
}
printf("\n");
}``````

Complete C Code

Below you can find the complete C program for inserting a node at any given position.

``````#include <stdio.h>
#include <stdlib.h>

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

void insert(int data, int n)
{
struct Node* temp= (struct Node*)malloc(sizeof(struct Node*));
temp->data=data;
temp->next=NULL;
if (n==1) {
return;
}

for(int i=0; i<n-2; i++){
temp2=temp2->next;
}
temp->next=temp2->next;
temp2->next=temp;
}

void Print()
{
while(temp!=NULL)
{
printf(" %d",temp->data);
temp=temp->next;
}
printf("\n");
}

int main()
{
insert(3,1);
insert(5,2);
insert(9,3);
insert(6,4);
insert(7,5);
Print();
}``````

Code Output

Now let’s see the code output. After the compilation of the above code, you will get this output.

Lets run once again and call the following parameters instead:

``````int main()
{