Insertion in Singly Linked List in C++

• Adding a node at the beginning of the list.
• Adding a node after a given position in the list.
• Adding a node at the end of the list.

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

1. Adding a node at the beginning of the Linked List.

• Create a new node and store the data value in the first part of the node and the second part is initially pointing to NULL. 

//create a new node and initialize data value using constructor
Node *new_node = new Node(data);

• Point the next pointer of the newly created node to the existing first node whose address is present inside the head pointer. 

new_node->next = head;

• Update the value of the head pointer with the address of our new node as the head always points to the first node of the list. 

head = new_node;

• Traverse the given list and reach the position-1 node and mark that node as current.
• Create a new node with the given data value and the next pointer initially pointing to NULL.
• Point the next pointer of the new node to the next of the current node.
• Point the next pointer of the current node to the newly created node. 

• Traverse a given list using a temp pointer till you reach the end of the list. 
• Create a new node with the given data value and the next pointer of the new node pointing to NULL.
• Point the next pointer of the temp node to the new node and the next pointer of the new node is already pointing to NULL. 

//C++ Example of Insertion in Singly Linked List
#include<iostream>
using namespace std;

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

//Add a node to the front of list
Node *insertFront(Node *head, int data){

    Node *new_node = new Node(data);
    //add a new node when list is empty
    if(head == NULL)
      head = new_node;
    //adding new node at the front of the list  
    else{
        new_node->next = head;
        head = new_node;
    }
    return head;  
}
//Add a node after the position
Node *insertPos(Node *head, int pos, int data){
    int count = 0;
    Node *current = head;

    //Adding a node in empty list
    if(current == NULL){
        Node *new_node = new Node(data);
        head = new_node;
    }
    //Adding a node after given position
    else{
        while (count != pos-1)
        {
            current = current->next;
            count++;
        }
        Node *new_node = new Node(data);
        new_node->next = current->next;
        current->next = new_node;
    }
    return head;
}
//Adding node at the end of the list
Node *insertEnd(Node *head, int data){
    //create a new node
    Node *new_node = new Node(data);
    Node *temp = head;
    //when list is empty
    if(temp == NULL){
        head = new_node;
    }
    else{
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = new_node;
    }
    return head;
}

//Traversing Linked List
void display(Node *head){
    Node *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}

int main(){
    Node *head = NULL;
    head = insertFront(head, 10);
    head = insertFront(head, 13);
    head = insertEnd(head, 22);
    head = insertEnd(head, 23);
    head = insertFront(head, 33);
    head = insertPos(head, 3, 32);

    cout<<"Singly Linked List: ";
    display(head);
    return 0;    
}

Singly Linked List: 33 13 10 32 22 23

• Time Complexity: Adding a node at the front of the list takes O(1) time whereas adding a node at the end or in between the list takes O(n) time in worst cases. 
• Space Complexity: No extra space is required to perform any insertion operation so space complexity will be O(1).