# Linked List Insertion

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

How To Insert Items In Python List ...
How To Insert Items In Python List | Python Tutorial | Python List Insert Method
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.

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

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

• ##### 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. ## 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);
}

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) {
*head = new Node(x);
}
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);
Node *tail = *head;
if (*head == NULL)
{
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";
printList(head); cout << "\n";
printList(head); cout << "\n";
printList(head); 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.

## Related Article - Data Structure

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion
• ## Related Article - Linked List

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion