# Linked List Insertion in C++

## Insertion in Singly linked in C++

Singly Linked List Insertion in C++, in general words can be understood as insertion of a new node in a singly linked list that is already created. We can perform three different types of insertion operations on a singly linked list –

• Insertion at tail
• Insertion at the specific position.

In this article, we will discuss what is the difference between these types of insertion and how to perform them over a singly linked list. Insertion Time Complexity (AVG) Θ(1) Insertion Time Complexity (Worst) O(1) Space Complexity O(1)

## Types of insertion in a singly linked list

In this type of insertion in a singly linked list, a new node is added before the head of the list i.e. before the first node of the list.

#### Insertion at specific position:

Here we insert a new node at a specific position by traversing to the desired position and inserting a new node there.

#### Insertion at the tail:

We insert a new node after the last node i.e. after the tail node in the insertion at the end singly linked list. ## How to perform insertion at beginning in Singly Linked List in C++?

To perform insertion at the beginning in a singly linked list we will use the following steps:-

1. Create the memory for new Node
2. Assign the data value
3. Assign the newNode’s next as the current head
4. Change the head to this newNode

If it was the first node in the Linked List then next would null for this newNode ```void insertAtBeginning(Node** head, int val){

// dynamically create memory for this newNode
Node* newNode = new Node();

newNode->val = val;

cout << newNode->val << " inserted" << endl;
}```
```void LinkedList:: insertAtBeginning(int val){

// dynamically create memory for this newNode
Node* newNode = new Node();

newNode->val = val;

cout << newNode->val << " inserted" << endl;
}```

## How to perform insertion at end in singly linked list?

To perform insertion at the end in the singly linked list we will use the following steps:-

1. Create the memory and assign data value call this newNode
2. Traverse to the current end node of the list.
3. Assign this current end node’s next to newNode
4. Since this will be the last node assign next to NULL ```void insertAtLast(Node** head, int val){

Node* newNode = new Node();

newNode->val = val;
// Last node always pointst to NULL
newNode->next = NULL;

// If Linked List was empty
cout << newNode->val << " inserted" << endl;
return;
}

// reach to the last node of Linked List
while(tempNode->next!=NULL)
tempNode = tempNode->next;

// assign last node's next to this newNode
tempNode->next = newNode;
cout << newNode->val << " inserted" << endl;

}```
```void LinkedList:: insertAtLast(int val){

Node* newNode = new Node();

newNode->val = val;
// Last node always pointst to NULL
newNode->next = NULL;

// If Linked List was empty
cout << newNode->val << " inserted" << endl;         return;     }     Node* tempNode = head;     // reach to the last node of Linked List     while(tempNode->next!=NULL)
tempNode = tempNode->next;

// assign last node's next to this newNode
tempNode->next = newNode;
cout << newNode->val << " inserted" << endl;

}```

## How to perform insertion After specific position in singly linked list?

To perform insertion after specific position in singly linked list we will use the following steps:-
1. Create the memory and assign data value
2. Check if the position user asked us to Insert After is valid or not (Should not be negative and should not be greater than size)
3. Traverse till the nth node
4. Assign this new Node’s next to the nth node’s next that is the (n+1)th node
5. Assign nth node’s next to this new Node ```// required for insertAfterNthNode
int getCurrSize(Node* node){
int size=0;

while(node!=NULL){
node = node->next;
size++;
}
return size;
}

void insertAfterNthNode(int n, int val, Node** head)
{

// Negative Position Insertions not possible
// Can't insert if position to insert is greater than size of Linked List
if(n < 0 || n > size)
cout << "Invalid position to insert";

if(n == 0){
}
else {
Node* newNode = new Node();

newNode->val = val;
newNode->next = NULL;

// tempNode used to traverse the Linked List

// traverse till the nth node
while(--n)
tempNode = tempNode->next;

// assign newNode's next to nth node's next
newNode->next= tempNode->next;
// assign nth node's next to this new node
tempNode->next = newNode;
// newNode inserted

cout << newNode->val << " inserted" << endl;
}
}
```
```// required for insertAfterNthNode
int size=0;

Node* node = new Node();

while(node!=NULL){
node = node->next;
size++;
}
return size;
}

void LinkedList:: insertAfterNthNode(int n, int val)
{
int size = getCurrSize();

// Negative Position Insertions not possible
// Can't insert if position to insert is greater than size of Linked List
if(n < 0 || n > size)
cout << "Invalid position to insert";     if(n == 0){         insertAtBeginning(val);     } else {         Node* newNode = new Node();         newNode->val = val;
newNode->next = NULL;

// tempNode used to traverse the Linked List

// traverse till the nth node
while(--n)
tempNode = tempNode->next;

// assign newNode's next to nth node's next
newNode->next= tempNode->next;
// assign nth node's next to this new node
tempNode->next = newNode;
// newNode inserted

cout << newNode->val << " inserted" << endl;
}
}```

## Complete Program for Insertion in a Linked List in C++

Let us have a look at the program –

```// Complete Program for Insertion in a Linked List in C++
#include<iostream>
using namespace std;

class Node
{
public:
int val;
Node *next;
};

// dynamically create memory for this newNode
Node* newNode = new Node();

newNode->val = val;

cout << newNode->val << " inserted" << endl; } void insertAtLast(Node** head, int val){     Node* newNode = new Node();     newNode->val = val;
// Last node always pointst to NULL
newNode->next = NULL;

// If Linked List was empty
cout << newNode->val << " inserted" << endl;         return;     }     Node* tempNode = *head;     // reach to the last node of Linked List     while(tempNode->next!=NULL)
tempNode = tempNode->next;

// assign last node's next to this newNode
tempNode->next = newNode;
cout << newNode->val << " inserted" << endl; } // required for insertAfterNthNode int getCurrSize(Node* node){     int size=0;     while(node!=NULL){         node = node->next;
size++;
}
return size;
}

void insertAfterNthNode(int n, int val, Node** head)
{

// Negative Position Insertions not possible
// Can't insert if position to insert is greater than size of Linked List
if(n < 0 || n > size)
cout << "Invalid position to insert";     if(n == 0){         insertAtBeginning(head, val);     }     else {         Node* newNode = new Node();         newNode->val = val;
newNode->next = NULL;

// tempNode used to traverse the Linked List

// traverse till the nth node
while(--n)
tempNode = tempNode->next;

// assign newNode's next to nth node's next
newNode->next= tempNode->next;
// assign nth node's next to this new node
tempNode->next = newNode;
// newNode inserted

cout << newNode->val << " inserted" << endl;
}
}

void display(Node* node){
cout << "\n";

// as linked list will end when Node is Null
while(node!=NULL){
cout << node->val << " "; node = node->next;
}
cout << "\n" << endl;
}

int main()
{

//Inserts data: 15 after 5th node

return 0;
}```
```12 inserted
11 inserted
10 inserted

10 11 12

13 inserted
14 inserted
16 inserted

10 11 12 13 14 16

15 inserted
9 inserted

9 10 11 12 13 14 15 16 ```
```// Complete Program for Insertion in a Linked List in C++
#include<iostream>
using namespace std;

class Node
{
public:
int val;
Node *next;
};

{
private:
public:
}
int getCurrSize();
void insertAtBeginning(int val);
void insertAtLast(int val);
void insertAfterNthNode(int pos, int val);
void display();
};

// dynamically create memory for this newNode
Node* newNode = new Node();

newNode->val = val;

cout << newNode->val << " inserted" << endl; } void LinkedList:: insertAtLast(int val){     Node* newNode = new Node();     newNode->val = val;
// Last node always points to NULL
newNode->next = NULL;

// If Linked List was empty
cout << newNode->val << " inserted" << endl;         return;     }     Node* tempNode = head;     // reach to the last node of Linked List     while(tempNode->next!=NULL)
tempNode = tempNode->next;

// assign last node's next to this newNode
tempNode->next = newNode;
cout << newNode->val << " inserted" << endl; } // required for insertAfterNthNode int LinkedList:: getCurrSize(){     int size=0;     Node* node = new Node();     node = head;     while(node!=NULL){         node = node->next;
size++;
}
return size;
}

void LinkedList:: insertAfterNthNode(int n, int val)
{
int size = getCurrSize();

// Negative Position Insertions not possible
// Can't insert if position to insert is greater than size of Linked List
if(n < 0 || n > size)
cout << "Invalid position to insert";     if(n == 0){         insertAtBeginning(val);     }     else {         Node* newNode = new Node();         newNode->val = val;
newNode->next = NULL;

// tempNode used to traverse the Linked List

// traverse till the nth node
while(--n)
tempNode = tempNode->next;

// assign newNode's next to nth node's next
newNode->next= tempNode->next;
// assign nth node's next to this new node
tempNode->next = newNode;
// newNode inserted

cout << newNode->val << " inserted" << endl;
}
}

cout << "\n";

Node* temp = new Node();
// as linked list will end when Node is Null
while(temp!=NULL){
cout << temp->val << " "; temp = temp->next;
}

//Inserts data: 15 after 5th node

return 0;
}```
```12 inserted
11 inserted
10 inserted

10 11 12

13 inserted
14 inserted
16 inserted

10 11 12 13 14 16

15 inserted
9 inserted

9 10 11 12 13 14 15 16``` • Introduction to Linked List in Data Structure
C | C++ | Java
• Singly Linked List in –
C | C++ | Java
• Insertion in singly Linked List –
C | C++ | Java
• Insertion at beginning in singly Linked List  –
C | C++Java
• Insertion at nth position in singly Linked List  –
C | C++Java
• Insertion at end in singly Linked List  –
C | C++Java
• Deletion in singly Linked List  –
C | C++Java
• Deletion from beginning in singly linked list :
C | C++ | Java
• Deletion from nth position in singly linked list :
C | C++ | Java
• Deletion from end in singly linked list :
C | C++ | Java
• Linked List Insertion and Deletion –
C | C++Java
• Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++Java
C | C++Java
• Print reverse of a linked list without actually reversing –
C |C++Java
• Print reverse of a linked list without actually reversing –
C |C++Java
• Insertion in the middle Singly Linked List –
C | C++Java
• Insertion in a Sorted Linked List –
C | C++Java
• Delete alternate nodes of a Linked List –
C | C++Java
• Find middle of the linked list –
C | C++Java
• Reverse a linked list in groups of given size –
C | C++Java
• Find kth node from end of the linked list –
C | C++Java
• Append the last n nodes of a linked list to the beginning of the list –
C | C++Java
• Check whether linked list is palindrome or not –
C | C++Java
• Fold a Linked List –
C | C++Java
• Insert at given Position –
C | C++Java
• Deletion at given Position –
C | C++Java

• Introduction to Linked List in Data Structure
• Linked List in – C | C++ | Java
• Singly Linked List in – C | C++ | Java
• Insertion in singly Linked List – C | C++ | Java
• Insertion at beginning in singly Linked List  – C | C++Java
• Insertion at nth position in singly Linked List  – C | C++Java
• Insertion at end in singly Linked List  – C | C++Java
• Deletion in singly Linked List  – C | C++Java
• Deletion from beginning in singly linked list : C | C++ | Java
• Deletion from nth position in singly linked list : C | C++ | Java
• Deletion from end in singly linked list : C | C++ | Java
• Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
• Linked List Insertion and Deletion – C | C++Java
• Reverse a linked list by changing links between nodes – C | C++Java
• Linked List insertion in the middle – C | C++Java
• Print reverse of a linked list without actually reversing – C |C++Java
• Search an element in a linked list – C | C++Java
• Insertion in a Sorted Linked List – C | C++Java
• Delete alternate nodes of a Linked List – C | C++Java
• Find middle of the linked list – C | C++Java
• Reverse a linked list in groups of given size – C | C++Java
• Find kth node from end of the linked list – C | C++Java
• Append the last n nodes of a linked list to the beginning of the list – C | C++Java
• Check whether linked list is palindrome or not – C | C++Java
• Fold a Linked List – C | C++Java
• Insert at a given position – C | C++Java
• Delete at a given position – C | C++Java