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 the head.
  • 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 in Circular Linked List
Insertion Time Complexity (AVG)Θ(1)
Insertion Time Complexity (Worst)O(1)
Space ComplexityO(1)

Types of insertion in a singly linked list

Insertion at the head:

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.

Types of insertion in circular 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

Insertin at beginning in singly linked list in C++
void insertAtBeginning(Node** head, int val){
    
    // dynamically create memory for this newNode
    Node* newNode = new Node();
    
    newNode->val = val;
    newNode->next = *head;

    *head = newNode;
    
    cout << newNode->val << " inserted" << endl;
}
void LinkedList:: insertAtBeginning(int val){
    
    // dynamically create memory for this newNode
    Node* newNode = new Node();
    
    newNode->val = val;
    newNode->next = head;

    head = newNode;
    
    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
    if(*head==NULL){
        *head = newNode;
        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;

}
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
    if(head==NULL){
        head = newNode;
        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
Algorithm for insertion in between the nodes in singly linked list in c++
// 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)
{
    int size = getCurrSize(*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
        Node* tempNode = *head; 
        
        // 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 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 Node* tempNode = head; // 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;
};

void insertAtBeginning(Node** head, int val){
    
    // dynamically create memory for this newNode
    Node* newNode = new Node();
    
    newNode->val = val;
    newNode->next = *head;

    *head = newNode;
    
    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 if(*head==NULL){ *head = newNode; 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) { int size = getCurrSize(*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 Node* tempNode = *head; // 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() { Node* head = NULL; insertAtBeginning(&head,12); insertAtBeginning(&head,11); insertAtBeginning(&head,10); display(head); insertAtLast(&head,13); insertAtLast(&head,14); insertAtLast(&head,16); display(head); //Inserts data: 15 after 5th node insertAfterNthNode(5, 15,&head); insertAfterNthNode(0, 9,&head); display(head); 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;
};

class LinkedList
{
    private:
        Node* head;
    public:
        LinkedList() { // constructor
        head = NULL;
    }
        int getCurrSize();
        void insertAtBeginning(int val);
        void insertAtLast(int val);
        void insertAfterNthNode(int pos, int val);
        void display();
};

void LinkedList:: insertAtBeginning(int val){
    
    // dynamically create memory for this newNode
    Node* newNode = new Node();
    
    newNode->val = val;
    newNode->next = head;

    head = newNode;
    
    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 if(head==NULL){ head = newNode; 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 Node* tempNode = head; // 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 LinkedList:: display(){ cout << "\n"; Node* temp = new Node(); temp = head; // as linked list will end when Node is Null while(temp!=NULL){ cout << temp->val << " "; temp = temp->next; } cout << "\n" << endl; }

int main() {

LinkedList* linked_list = new LinkedList();
linked_list->insertAtBeginning(12); linked_list->insertAtBeginning(11); linked_list->insertAtBeginning(10); linked_list->display(); linked_list->insertAtLast(13); linked_list->insertAtLast(14); linked_list->insertAtLast(16); linked_list->display(); //Inserts data: 15 after 5th node linked_list->insertAfterNthNode(5, 15); linked_list->insertAfterNthNode(0, 9); linked_list->display(); 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
Linked Lists in C++ meme

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • 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
  • Linked List Insertion and Deletion –
    C | C++Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++Java
  • Reverse a linked list by changing links between nodes –
    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

Singly Linked List

  • 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