# Linked List Insertion

- Linked List Insertion Algorithm
- Linked List Insertion Illustration
- Linked List Insertion Implementation
- Linked List Insertion Algorithm Complexity

In this article, we will learn how to insert a node in a linked list. We can see that 4 different scenarios arise.

- We want to insert a node before the head of the linked list. This operation resembles the push operation in the stack.
- We want to insert a node at the end of the linked list i.e. next to the tail node.
- We want to insert a node at the
`i-th`

position of the linked list. - We have the reference of the node, after which we want to insert the new node.

## Linked List Insertion Algorithm

Let the `head`

be the pointer to the first node of the linked list and let `x`

be the data to be inserted into the linked list.

### Insert Node at the Head of the Linked List `push()`

##### Create a new node

`temp`

with data`x`

.##### Set

`temp->next`

to`head`

to insert`temp`

before the`head`

.##### Set

`temp`

as the head of the linked list.

### Insert Node at the End of the Linked List `append()`

##### Create a new node

`temp`

with data`x`

.##### Initialize

`tail`

pointing towards the`head`

.##### If the linked list is empty, set

`temp`

as`head`

of the linked list and return.##### Else iterate towards the end of the linked list, such that

`tail->next`

!=`NULL`

, so that you land at the last element##### Set

`tail->next`

as the`temp`

.

### Insert Node at the `i-th`

Position of the Linked List `insertNpos()`

##### If position

`pos`

<=`0`

, return;##### If

`pos`

==`0`

and the`head`

is empty, create a new node with data as`x`

and set it as the`head`

.##### Else if

`pos`

==`1`

, call`push()`

.##### Else, create a new node

`temp`

with data`x`

.##### Initialize

`curr`

pointing towards the`head`

.##### while

`pos--`

, do the following:If

`pos`

==`1`

,- If
`curr`

is not`NULL`

- Set
`temp->next`

as`curr->next`

to insert`temp`

after`curr`

. - Set
`curr->next`

as the`temp`

to connect`curr`

to`temp`

.

- Set
- Return;

- If
Else set

`curr`

as`curr->next`

.

### Insert Node Next to Reference of Given Node `insertAfter()`

##### if

`prev`

==`NULL`

, return;##### Create a new node

`curr`

with data`x`

.##### Point

`curr->next`

to`prev->next`

to add new node after prev.##### Point

`prev->next`

towards`curr`

to complete the insertion.

## Linked List Insertion Illustration

Assume that we have a node `temp`

with a data value equal to `5`

and we want to insert it in the linked list. Let us consider all `4`

cases and illustrate how the above algorithms work.

### Insert Node at the Head of the Linked List `push()`

##### Set

`temp's`

s pointer towards the`head`

.##### Point

`head`

to`temp`

.

### Insert Node at the End of the Linked List `append()`

##### Point

`curr`

towards the`head`

with data as`2`

.##### Set

`curr`

as`curr->next`

and move it to the node with data`3`

.##### Set

`curr`

as`curr->next`

and move it to the node with data`4`

.##### Exit the while loop and set

`curr->next`

as`temp`

.

### Insert Node at the `i-th`

Position of the Linked List `insertNpos()`

We will insert our node at position `3`

.

##### Point

`curr`

towards`head`

with data as`1`

,`pos`

=`pos-1`

=`2`

.##### Set

`curr`

as`curr->next`

and move it to node with data`3`

,`pos`

=`pos -1`

=`1`

.##### Set

`temp->next`

as`curr->next`

to insert temp after`curr`

.##### Set

`curr->next`

as the`temp`

to complete insertion of`temp`

between`curr`

and`curr->next`

.

### Insert Node Next to Reference of Given Node `insertAfter()`

##### Set

`temp->next`

as`prev->next`

to insert`temp`

between`prev`

and`prev->next`

.##### Set

`prev->next`

as the`temp`

to complete the insertion.

## Linked List Insertion Implementation

```
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
this->data = x;
this->next = NULL;
}
};
void push(Node** head, int x)
{
Node* temp = new Node(x);
temp->next = (*head);
(*head) = temp;
}
void insertAfter(Node* prev, int x)
{
if (prev == NULL) {
return;
}
Node* curr = new Node(x);
curr->next = prev->next;
prev->next = curr;
}
void printList(Node* head)
{
Node*curr = head;
while (curr != NULL) {
cout << curr->data << " ";
curr = curr->next;
}
}
void insertNpos(Node**head, int x, int pos) {
if (pos <= 0) {
return;
}
if (!head && pos == 1) {
*head = new Node(x);
}
else if (pos == 1) {
push(head, x);
}
Node* temp = new Node(x);
Node*curr = *head;
while (pos--) {
if (pos == 1) {
if (curr) {
temp->next = curr->next;
curr->next = temp;
}
return;
}
curr = curr->next;
}
}
void append(Node** head, int x)
{
Node* temp = new Node(x);
Node *tail = *head;
if (*head == NULL)
{
*head = temp;
return;
}
while (tail->next != NULL)
tail = tail->next;
tail->next = temp;
return;
}
int main()
{
Node* head = new Node(1);
head -> next = new Node(2);
printList(head); cout << "\n";
push(&head, 3);
push(&head, 4);
printList(head); cout << "\n";
append(&head, 5);
printList(head); cout << "\n";
insertAfter(head->next->next, 6);
printList(head); cout << "\n";
insertNpos(&head, 24, 2);
printList(head);
return 0;
}
```

## Linked List Insertion Algorithm Complexity

### Time Complexity

- Average Case

To insert a node at the `i-th`

position in the linked list, we have to visit `i`

nodes. So, the time complexity is of the order of `O(i)`

. And we have `n`

nodes in the linked list, so on the average-case time complexity is `O(n/2)`

or `O(n)`

. The time complexity is of the order of `O(n)`

.

- Best Case

The best-case occurs when we want to insert a node at the head of the linked list or we have the reference to the node before the site of insertion. The best-case time complexity is `O(1)`

.

- Worst Case

The worst-case time complexity is `O(n)`

. It is the same average-case time complexity.

### Space Complexity

This insertion algorithm’s space complexity is `O(1)`

as no extra space other than `curr`

pointer is required.