# Insert a node at a specific position in a linked list

## Introduction

In this blog, we will discuss a linked list problem that has been asked frequently in Interviews.

The problem is to **Insert a node at a specific position in a linked list.**

Let's start with a discussion on what linked lists are. A linked list is an ordered set of elements, each holding data and link containing the address to the next element.

To know more about the linked list, refer to this __blog__.

Now, coming to the question.

We are given N elements in a linked list, and we are asked to insert an element at a given specified position.

For example: here at position 2, we are asked to insert 2.

After inserting,

## Approach

Now we will discuss the** approach** to Insert a node at a specific position in a linked list.

Declare the structure of the Node and write the function to create and return the node.

⬇

Now for inserting the Node, check if the required position is valid or not.

⬇

Create a new Node.

⬇

Traverse till the position asked.

⬇

Update the link.

1)New Node should point the old Node at the same position.

2) Change the pointer of the Node previous to the old Node to point to the new Node

Time Complexity = O(n)

Since in the worst case, only one traversal is needed.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

And solve some related problems on the linked list.

__Some Commonly Asked Problems On Linked List__

If you could not solve how to Insert a node at a specific position in a linked list, don’t be sad. This is part of the learning process.

Please have a look at the algorithm, and then again, you must give it a try.

### PseudoCode

**Algorithm**

___________________________________________________________________

**procedure** insert( ):

___________________________________________________________________

**1.** If n==1:

temp1->next=head

head=temp1

return

**2. **Node* temp2 = head

**3.** Traverse till the required position and then go its link.

**4.** After traversing, update the link.

temp1->next=temp2->next;

temp2->next=temp1;

**end procedure**

___________________________________________________________________

Let's take a quick look at a video to have a visual idea of how to insert a node at a specific position in a linked list.

## CODE IN C++

```
// Insert a node at a specific position in a linked list
#include <bits/stdc++.h>
using namespace std;
// Declaration of node of a linked list
struct Node {
int data;
struct Node* next;
};
struct Node* head;
// function to insert a Node at the mentioned position
void insert(int data, int n)
{
Node* temp1 = new Node();
temp1->data = data;
temp1->next = NULL;
// function to insert node at position 1.
if(n==1){
temp1->next=head;
head=temp1;
return;
}
//inserting at the given position
Node* temp2 = head;
//traversing
for(int i=0; i<n-2; i++){
temp2=temp2->next;
}
//updating the link
temp1->next=temp2->next;
temp2->next=temp1;
}
//function to display the node
void print(){
Node* temp=head;
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->next;
}
printf("\n");
}
// Driver Code
int main()
{
// Creating the list 1->3->5->7
head = NULL;
insert(1,1);
insert(3,2);
insert(5,3);
insert(7,4);
//adding 2 at position 2.
insert(2,2);
print();
return 0;
}
```

**Output**

```
Input: 1 3 5 7
Output: 1 2 3 5 7
```

### Complexity Analysis

**Time Complexity:** **O(n).**

**Analyzing Time Complexity:**

In the worst case, all elements are to be traversed once.

∴n.

**Space complexity**: O(1) since no extra variable is used.

## Frequently Asked Questions

**Can we access a node directly in a linked list?****Answer)**Unlike an array, this is not possible in a linked list.

**What things should we keep in mind for such a problem?****Answer)**Ensure that you are not de-attaching all the nodes in a single time. Make sure that the nodes exist in the problem.

**Is it necessary to initialise the last node address as null?****Answer)**Yes, as elements are not stored in a contiguous manner, pointers are used, so sometimes it may take the garbage value.

**Why do sometimes I get a segmentation fault?****Answer)**This is most likely if we try to access NULL or out of bounds memory.

## Key Takeaways

This article taught us how to Insert a node at a specific position in a linked list. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analysing problems by walking over the execution of the examples and finding out the recursive pattern followed in most linked list problems.

Now, we recommend you practice problem sets based on the linked list to master your fundamentals. You can get a wide range of questions similar to this on __CodeStudio__.

Comments

## No comments yet

## Be the first to share what you think