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

1. We want to insert a node before the head of the linked list. This operation resembles the push operation in the stack.
2. We want to insert a node at the end of the linked list i.e. next to the tail node.
3. We want to insert a node at the `i-th` position of the linked list.
4. We have the reference of the node, after which we want to insert the new node.

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 `i-th` Position of the Linked List `insertNpos()`

• ##### 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`.
• Return;
• Else set `curr` as `curr->next`.

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

• ##### Point `prev->next` towards `curr` to complete the insertion.

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()`

• ##### Point `head` to `temp`. ### Insert Node at the End of the Linked List `append()`

• ##### 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`.

• ##### 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 `prev->next` as the `temp` to complete the insertion. ``````#include <bits/stdc++.h>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int x) {
this->data = x;
this->next = NULL;
}
};

{
Node* temp = new Node(x);
}

void insertAfter(Node* prev, int x)
{
if (prev == NULL) {
return;
}
Node* curr = new Node(x);
curr->next = prev->next;
prev->next = curr;
}

{
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) {
}
else if (pos == 1) {
}
Node* temp = new Node(x);
while (pos--) {
if (pos == 1) {
if (curr) {
temp->next = curr->next;
curr->next = temp;
}
return;
}
curr = curr->next;
}
}
{
Node* temp = new Node(x);
{
return;
}
while (tail->next != NULL)
tail = tail->next;
tail->next = temp;
return;
}

int main()
{
head -> next = new Node(2);
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.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.