# Linked List - Insert a new node at the given position

In this method, a new element is inserted at the specified position in the linked list. For example - if the given list is 10->20->30 and a new element 100 is added at position 2, the list becomes 10->100->20->30.

First, a new node with given element is created. If the insert position is 1, then the new node is made to head. Otherwise, traverse to the node that is previous to the insert position and check if it is null or not. In case of null, the specified position does not exist. In other case, assign next of the new node as next of the previous node and next of previous node as new node. The below figure describes the process, if the insert node is other than the head node.

The function push_at is created for this purpose. It is a 6-step process.

```void push_at(int newElement, int position) {

//1. allocate node to new element
Node* newNode = new Node();
newNode->data = newElement;
newNode->next = NULL;

//2. check if the position is > 0
if(position < 1) {
cout<<"\nposition should be >= 1.";
} else if (position == 1) {

//3. if the position is 1, make next of the
} else {

//4. Else, make a temp node and traverse to the
//   node previous to the position
for(int i = 1; i < position-1; i++) {
if(temp != NULL) {
temp = temp->next;
}
}

//5. If the previous node is not null, make
//   newNode next as temp next and temp next
//   as newNode.
if(temp != NULL) {
newNode->next = temp->next;
temp->next = newNode;
} else {

//6. When the previous node is null
cout<<"\nThe previous node is null.";
}
}
}
```
```void push_at(struct Node** head_ref, int newElement, int position) {

//1. allocate node to new element
struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newElement;
newNode->next = NULL;

//2. check if the position is > 0
if(position < 1) {
printf("\nposition should be >= 1.");
} else if (position == 1) {

//3. if the position is 1, make next of the
} else {

//4. Else, make a temp node and traverse to the
//   node previous to the position
for(int i = 1; i < position-1; i++) {
if(temp != NULL) {
temp = temp->next;
}
}

//5. If the previous node is not null, make
//   newNode next as temp next and temp next
//   as newNode.
if(temp != NULL) {
newNode->next = temp->next;
temp->next = newNode;
} else {

//6. When the previous node is null
printf("\nThe previous node is null.");
}
}
}
```
```def push_at(self, newElement, position):

#1. allocate node to new element
newNode = Node(newElement)

#2. check if the position is > 0
if(position < 1):
print("\nposition should be >= 1.")
elif (position == 1):

#3. if the position is 1, make next of the
else:

#4. Else, make a temp node and traverse to the
#   node previous to the position
for i in range(1, position-1):
if(temp != None):
temp = temp.next

#5. If the previous node is not null, make
#   newNode next as temp next and temp next
#   as newNode.
if(temp != None):
newNode.next = temp.next
temp.next = newNode
else:

#6. When the previous node is null
print("\nThe previous node is null.")
```
```void push_at(int newElement, int position) {

//1. allocate node to new element
Node newNode = new Node();
newNode.data = newElement;
newNode.next = null;

//2. check if the position is > 0
if(position < 1) {
System.out.print("\nposition should be >= 1.");
} else if (position == 1) {

//3. if the position is 1, make next of the
} else {

//4. Else, make a temp node and traverse to the
//   node previous to the position
Node temp = new Node();
for(int i = 1; i < position-1; i++) {
if(temp != null) {
temp = temp.next;
}
}

//5. If the previous node is not null, make
//   newNode next as temp next and temp next
//   as newNode.
if(temp != null) {
newNode.next = temp.next;
temp.next = newNode;
} else {

//6. When the previous node is null
System.out.print("\nThe previous node is null.");
}
}
}
```
```public void push_at(int newElement, int position) {

//1. allocate node to new element
Node newNode = new Node();
newNode.data = newElement;
newNode.next = null;

//2. check if the position is > 0
if(position < 1) {
Console.Write("\nposition should be >= 1.");
} else if (position == 1) {

//3. if the position is 1, make next of the
} else {

//4. Else, make a temp node and traverse to the
//   node previous to the position
Node temp = new Node();
for(int i = 1; i < position-1; i++) {
if(temp != null) {
temp = temp.next;
}
}

//5. If the previous node is not null, make
//   newNode next as temp next and temp next
//   as newNode.
if(temp != null) {
newNode.next = temp.next;
temp.next = newNode;
} else {

//6. When the previous node is null
Console.Write("\nThe previous node is null.");
}
}
}
```
```public function push_at(\$newElement, \$position) {

//1. allocate node to new element
\$newNode = new Node();
\$newNode->data = \$newElement;
\$newNode->next = null;

//2. check if the position is > 0
if(\$position < 1) {
echo "\nposition should be >= 1.";
} else if (\$position == 1) {

//3. if the position is 1, make next of the
} else {

//4. Else, make a temp node and traverse to the
//   node previous to the position
\$temp = new Node();
for(\$i = 1; \$i < \$position-1; \$i++) {
if(\$temp != null) {
\$temp = \$temp->next;
}
}

//5. If the previous node is not null, make
//   newNode next as temp next and temp next
//   as newNode.
if(\$temp != null) {
\$newNode->next = \$temp->next;
\$temp->next = \$newNode;
} else {

//6. When the previous node is null
echo "\nThe previous node is null.";
}
}
}
```

The below is a complete program that uses above discussed concept to insert new node at a given position in the linked list.

```#include <iostream>
using namespace std;

//node structure
struct Node {
int data;
Node* next;
};

private:
public:
}

//Add new element at the end of the list
void push_back(int newElement) {
Node* newNode = new Node();
newNode->data = newElement;
newNode->next = NULL;
} else {
while(temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
}

//Inserts a new element at the given position
void push_at(int newElement, int position) {
Node* newNode = new Node();
newNode->data = newElement;
newNode->next = NULL;

if(position < 1) {
cout<<"\nposition should be >= 1.";
} else if (position == 1) {
} else {

for(int i = 1; i < position-1; i++) {
if(temp != NULL) {
temp = temp->next;
}
}

if(temp != NULL) {
newNode->next = temp->next;
temp->next = newNode;
} else {
cout<<"\nThe previous node is null.";
}
}
}

//display the content of the list
void PrintList() {
if(temp != NULL) {
cout<<"The list contains: ";
while(temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<"\n";
} else {
cout<<"The list is empty.\n";
}
}
};

// test the code
int main() {

//Add three elements in the list.
MyList.push_back(10);
MyList.push_back(20);
MyList.push_back(30);
MyList.PrintList();

//Insert an element at position 2
MyList.push_at(100, 2);
MyList.PrintList();

//Insert an element at position 1
MyList.push_at(200, 1);
MyList.PrintList();

return 0;
}
```

The above code will give the following output:

```The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30
```
```#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
int data;
struct Node* next;
};

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {
struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newElement;
newNode->next = NULL;
} else {
while(temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}

//Inserts a new element at the given position
void push_at(struct Node** head_ref, int newElement, int position) {
struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newElement;
newNode->next = NULL;

if(position < 1) {
printf("\nposition should be >= 1.");
} else if (position == 1) {
} else {

for(int i = 1; i < position-1; i++) {
if(temp != NULL) {
temp = temp->next;
}
}

if(temp != NULL) {
newNode->next = temp->next;
temp->next = newNode;
} else {
printf("\nThe previous node is null.");
}
}
}

//display the content of the list
printf("The list contains: ");
while (temp != NULL) {
printf("%i ",temp->data);
temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}

// test the code
int main() {
struct Node* MyList = NULL;

//Add three elements in the list.
push_back(&MyList, 10);
push_back(&MyList, 20);
push_back(&MyList, 30);
PrintList(MyList);

//Insert an element at position 2
push_at(&MyList, 100, 2);
PrintList(MyList);

//Insert an element at position 1
push_at(&MyList, 200, 1);
PrintList(MyList);

return 0;
}
```

The above code will give the following output:

```The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30
```
```# node structure
class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

#Add new element at the end of the list
def push_back(self, newElement):
newNode = Node(newElement)
return
else:
while(temp.next != None):
temp = temp.next
temp.next = newNode

#Inserts a new element at the given position
def push_at(self, newElement, position):
newNode = Node(newElement)
if(position < 1):
print("\nposition should be >= 1.")
elif (position == 1):
else:
for i in range(1, position-1):
if(temp != None):
temp = temp.next
if(temp != None):
newNode.next = temp.next
temp.next = newNode
else:
print("\nThe previous node is null.")

#display the content of the list
def PrintList(self):
if(temp != None):
print("The list contains:", end=" ")
while (temp != None):
print(temp.data, end=" ")
temp = temp.next
print()
else:
print("The list is empty.")

# test the code

#Add three elements in the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.PrintList()

#Insert an element at position 2
MyList.push_at(100, 2)
MyList.PrintList()

#Insert an element at position 1
MyList.push_at(200, 1)
MyList.PrintList()
```

The above code will give the following output:

```The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30
```
```//node structure
class Node {
int data;
Node next;
};

}

//Add new element at the end of the list
void push_back(int newElement) {
Node newNode = new Node();
newNode.data = newElement;
newNode.next = null;
} else {
Node temp = new Node();
while(temp.next != null)
temp = temp.next;
temp.next = newNode;
}
}

//Inserts a new element at the given position
void push_at(int newElement, int position) {
Node newNode = new Node();
newNode.data = newElement;
newNode.next = null;

if(position < 1) {
System.out.print("\nposition should be >= 1.");
} else if (position == 1) {
} else {

Node temp = new Node();
for(int i = 1; i < position-1; i++) {
if(temp != null) {
temp = temp.next;
}
}

if(temp != null) {
newNode.next = temp.next;
temp.next = newNode;
} else {
System.out.print("\nThe previous node is null.");
}
}
}

//display the content of the list
void PrintList() {
Node temp = new Node();
if(temp != null) {
System.out.print("The list contains: ");
while(temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
} else {
System.out.println("The list is empty.");
}
}
};

// test the code
public class Implementation {
public static void main(String[] args) {

//Add three elements in the list.
MyList.push_back(10);
MyList.push_back(20);
MyList.push_back(30);
MyList.PrintList();

//Insert an element at position 2
MyList.push_at(100, 2);
MyList.PrintList();

//Insert an element at position 1
MyList.push_at(200, 1);
MyList.PrintList();
}
}
```

The above code will give the following output:

```The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30
```
```using System;

//node structure
class Node {
public int data;
public Node next;
};

}

//Add new element at the end of the list
public void push_back(int newElement) {
Node newNode = new Node();
newNode.data = newElement;
newNode.next = null;
} else {
Node temp = new Node();
while(temp.next != null)
temp = temp.next;
temp.next = newNode;
}
}

//Inserts a new element at the given position
public void push_at(int newElement, int position) {
Node newNode = new Node();
newNode.data = newElement;
newNode.next = null;

if(position < 1) {
Console.Write("\nposition should be >= 1.");
} else if (position == 1) {
} else {

Node temp = new Node();
for(int i = 1; i < position-1; i++) {
if(temp != null) {
temp = temp.next;
}
}

if(temp != null) {
newNode.next = temp.next;
temp.next = newNode;
} else {
Console.Write("\nThe previous node is null.");
}
}
}

//display the content of the list
public void PrintList() {
Node temp = new Node();
if(temp != null) {
Console.Write("The list contains: ");
while(temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
Console.WriteLine();
} else {
Console.WriteLine("The list is empty.");
}
}
};

// test the code
class Implementation {
static void Main(string[] args) {

//Add three elements in the list.
MyList.push_back(10);
MyList.push_back(20);
MyList.push_back(30);
MyList.PrintList();

//Insert an element at position 2
MyList.push_at(100, 2);
MyList.PrintList();

//Insert an element at position 1
MyList.push_at(200, 1);
MyList.PrintList();
}
}
```

The above code will give the following output:

```The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30
```
```<?php
//node structure
class Node {
public \$data;
public \$next;
}

public function __construct(){
}

//Add new element at the end of the list
public function push_back(\$newElement) {
\$newNode = new Node();
\$newNode->data = \$newElement;
\$newNode->next = null;
} else {
\$temp = new Node();
while(\$temp->next != null) {
\$temp = \$temp->next;
}
\$temp->next = \$newNode;
}
}

//Inserts a new element at the given position
public function push_at(\$newElement, \$position) {
\$newNode = new Node();
\$newNode->data = \$newElement;
\$newNode->next = null;

if(\$position < 1) {
echo "\nposition should be >= 1.";
} else if (\$position == 1) {
} else {

\$temp = new Node();
for(\$i = 1; \$i < \$position-1; \$i++) {
if(\$temp != null) {
\$temp = \$temp->next;
}
}

if(\$temp != null) {
\$newNode->next = \$temp->next;
\$temp->next = \$newNode;
} else {
echo "\nThe previous node is null.";
}
}
}

//display the content of the list
public function PrintList() {
\$temp = new Node();
if(\$temp != null) {
echo "The list contains: ";
while(\$temp != null) {
echo \$temp->data." ";
\$temp = \$temp->next;
}
echo "\n";
} else {
echo "The list is empty.\n";
}
}
};

// test the code

//Add three elements in the list.
\$MyList->push_back(10);
\$MyList->push_back(20);
\$MyList->push_back(30);
\$MyList->PrintList();

//Insert an element at position 2
\$MyList->push_at(100, 2);
\$MyList->PrintList();

//Insert an element at position 1
\$MyList->push_at(200, 1);
\$MyList->PrintList();
?>
```

The above code will give the following output:

```The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30
```

5