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.
Insertion in singly linked list in C++

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.

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;
}

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;

}

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;
    }
}

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

Let us have a look at the program –

Run
#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;
}

Output

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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

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