C++ Linked List Exercises: Insert a node at any position of a Singly Linked List

C++ Linked List: Exercise-9 with Solution

Write a C++ program to insert a new node at any position of a Singly Linked List.

Test Data:
Original list:
7 5 3 1
Position: 1, Value: 12
Updated list:
12 7 5 3 1
Position: 4, Value: 14
Updated list:
12 7 5 14 3 1
Position: 7, Value: 18
Updated list:
12 7 5 14 3 1 18

Sample Solution:

C++ Code:

#include <iostream> // Including input-output stream header file

using namespace std; // Using standard namespace

// Structure for defining a Node
struct Node {
    int num; // Data field to store a number
    Node *next; // Pointer to the next node
}; // Node constructed

int sizen = 0; // Initializing variable to keep track of the size of the linked list

// Function to insert a node at the beginning of the linked list
void insert(Node** head, int num) {
    Node* new_Node = new Node(); // Creating a new node
    new_Node->num = num; // Assigning data to the new node
    new_Node->next = *head; // Pointing the new node to the current head
    *head = new_Node; // Making the new node as the head
    sizen++; // Increasing the size of the linked list
}

// Function to insert a node at a given position in the linked list
void insert_Position(int pos, int data, Node** head) {
    Node* new_node = new Node(); // Creating a new node
    new_node->num = data; // Assigning data to the new node
    new_node->next = NULL; // Initializing next pointer to NULL

    // Invalid positions
    if (pos < 1 || pos > sizen + 1) {
        cout << "Invalid\n";
    } else if (pos == 1) { // Inserting at the beginning
        new_node->next = *head; 
        *head = new_node;
        sizen++;
    } else {
        Node* temp = *head; 
        // Traverse till the (pos-1)th node
        while (--pos > 1) {
            temp = temp->next;
        }
        new_node->next = temp->next;
        temp->next = new_node;
        sizen++;
    }
}

// Display all nodes in the linked list
void display_all_nodes(Node* node) {
    while (node != NULL) {
        cout << node->num << " "; // Displaying the data in the current node
        node = node->next; // Move to the next node
    } 
}

int main() {
    Node* head = NULL; // Initializing the head of the linked list as NULL

    insert(&head, 1); // Inserting a node with value 1
    insert(&head, 3); // Inserting a node with value 3
    insert(&head, 5); // Inserting a node with value 5
    insert(&head, 7); // Inserting a node with value 7

    cout << "Original list:\n"; // Displaying message for the original list
    display_all_nodes(head); // Displaying all nodes in the original list

    int pos = 1, value = 12;
    cout << "\n\nPosition: " << pos << ", Value: " << value;
    insert_Position(pos, value, &head); // Inserting a node at a specific position
    cout << "\nUpdated list:\n";
    display_all_nodes(head); // Displaying all nodes in the updated list

    pos = 4, value = 14;
    cout << "\n\nPosition: " << pos << ", Value: " << value;
    insert_Position(pos, value, &head); // Inserting a node at a specific position
    cout << "\nUpdated list:\n";
    display_all_nodes(head); // Displaying all nodes in the updated list

    pos = 7, value = 18;
    cout << "\n\nPosition: " << pos << ", Value: " << value;
    insert_Position(pos, value, &head); // Inserting a node at a specific position
    cout << "\nUpdated list:\n";
    display_all_nodes(head); // Displaying all nodes in the updated list

    cout << endl; // Displaying newline
    return 0; // Returning from the main function
}

Sample Output:

Original list:
7 5 3 1

Position: 1, Value: 12
Updated list:
12 7 5 3 1

Position: 4, Value: 14
Updated list:
12 7 5 14 3 1

Position: 7, Value: 18
Updated list:
12 7 5 14 3 1 18

Flowchart:

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Get N^th node in a Singly Linked List.
Next C++ Exercise: Delete first node of a Singly Linked List.