Harshit Jindal Feb 15, 2024

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

We will insert our node at position `3`.

### 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;
}
};

void push(Node** head, int x) {
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;
}
}
void append(Node** head, int x) {
Node* temp = new Node(x);
return;
}
while (tail->next != NULL) tail = tail->next;
tail->next = temp;
return;
}

int main() {
cout << "\n";
cout << "\n";
cout << "\n";
cout << "\n";
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.

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.