w3resource

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>

using namespace std;

struct  Node
{   
    int num;
    Node *next;
 }; //node constructed

  int size = 0;
  void insert(Node** head, int num){
    Node* new_Node = new Node();
    new_Node->num = num;
    new_Node->next = *head;
    *head = new_Node;    
     size++;
}


// method to insert at a given position
void insert_Position(int pos, int data, Node** head)
{
    Node* new_node = new Node();
    new_node->num = data;
    new_node->next = NULL;
    
    // Invalid positions
    if(pos < 1 || pos > size + 1) 
        printf("Invalid\n"); 
        
    // inserting first node
    else if(pos == 1){
        new_node->next = *head; 
        *head = new_node;
        size++;
    }
    
    else 
    {
        Node* temp = *head; 
        
        // traverse till the current (pos-1)th node
        while(--pos > 1){
            temp = temp->next;
        }
        new_node->next= temp->next;
        temp->next = new_node;
        size++;
    }
}

  //Display all nodes
  void display_all_nodes(Node* node)
    { 
      while(node!=NULL){
        cout << node->num << " "; 
        node = node->next; 
    } 
}

int main()
{
    Node* head = NULL;
    insert(&head,1);
    insert(&head,3);
    insert(&head,5);
    insert(&head,7);
    cout << "Original list:\n";
    display_all_nodes(head); 
    int pos = 1, value = 12;
    cout << "\n\nPosition: " << pos << ", Value: " << value;
    insert_Position(pos, value, &head);
    cout << "\nUpdated list:\n";
    display_all_nodes(head); 
    pos = 4, value = 14;
	cout << "\n\nPosition: " << pos << ", Value: " << value;
    insert_Position(pos, value, &head);
    cout << "\nUpdated list:\n";
    display_all_nodes(head); 
    pos = 7, value = 18;
	cout << "\n\nPosition: " << pos << ", Value: " << value;
    insert_Position(pos, value, &head);
    cout << "\nUpdated list:\n";
    display_all_nodes(head); 
    cout<<endl;
    return 0;
}

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:

Flowchart: Insert a node at any position of a Singly Linked List.
Flowchart:Insert a node at any position of a Singly Linked List.

CPP Code Editor:

Contribute your code and comments through Disqus.

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

What is the difficulty level of this exercise?



Share this Tutorial / Exercise on : Facebook and Twitter

C++ Programming: Tips of the Day

How to replace all occurrences of a character in string?

std::string doesn't contain such function but you could use stand-alone replace function from algorithm header.

#include <algorithm>
#include <string>

void some_func() {
  std::string s = "example string";
  std::replace( s.begin(), s.end(), 'x', 'y'); // replace all 'x' to 'y'
}

Ref: https://bit.ly/3niU71x